MAC0121 Algoritmos e Estruturas de Dados I

Por | Em

Até 2014 se chamou MAC0122 Princípios de Desenvolvimento de Algoritmos.

OBJETIVOS: Introduzir técnicas básicas de programação, estruturas de dados básicas, e noções de projeto e análise de algoritmos, por meio de exemplos.

Introduce basic programming techiques, data structures, and notions of design and analysis of algorithms, through examples.

PROGRAMA RESUMIDO: Noções de correção e desempenho de algoritmos. Noções de tipos abstratos de dados. Vetores e matrizes. Alocação dinâmica de memória. Apontadores. Listas ligadas. Árvores binárias. Pilhas e filas. Noções de filas de prioridade. Recursão. Algoritmos de ordenação. Processamento elementar de texto. Tabelas de símbolos elementares, incluindo árvores binárias de busca. Noções de estratégias algorítmicas.

Notions of correctness and performance of algorithms. Notions of abstract data types. Arrays. Dynamic memory allocation. Pointers. Linked lists. Binary trees. Stacks and queues. Notions of priority queues. Recursion. Sorting algorithms. Elementary text pocessing. Elementary symbol tables, including binary search trees. Notions of algorithmic strategies.

PROGRAMA: Noções informais de prova de correção e medida do desempenho de algoritmos. Noções de tipos abstratos de dados. Vetores e matrizes. Strings (cadeias de caracteres). Alocação dinâmica de memória e redimensionamento de vetores. Apontadores. Listas ligadas. Estruturas ligadas não lineares. Árvores binárias. Pilhas e filas (implementadas com vetores e listas ligadas). Aplicações. Filas de prioridade (implementadas com heaps). Aplicações. Recursão. Aplicações. Algoritmos de ordenação elementares. Algoritmo quicksort. Algoritmo mergesort. Algoritmo heapsort. Algoritmo radixsort (ordenação digital). Ordenação indireta (ordenação de apontadores). Processamento elementar de texto. Aplicações. Tabelas de símbolos elementares: implementações baseadas em vetores, listas ligadas, busca binária, e árvores binárias de busca. Aplicações. As aplicações podem envolver várias estruturas de dados compostas (como vetores de listas ligadas) e várias estratégias algorítmicas (gulosa, divisão e conquista, programação dinâmica, backtracking, busca em largura, etc.).

Informal notions of proof of correctness and evaluation of performance of algorithms. Notions of abstract data types. Arrays. Strings. Dynamic memory allocation and array resizing. Pointers. Linked lists. Non-linear linked structures. Binary trees. Stacks and queues (implemented with arrays an linked lists). Applications. Priority queues (implemented with heaps). Applications. Recursion. Applications. Elementary sorting algorithms. Quicksort. Mergesort. Heapsort. Radixsort. Indirect sorting (pointer sorting). Elementary text processing. Applications. Elementary symbol tables: implementations based on arrays, linked lists, binary search, and binary search trees. Applications. The applications may involve various composite data structures (such as arrays of linked lists) and various algorithmic strategies (greedy, divide-and-conquer, dynamic programming, backtracking, breadth-first-search, etc.).

RESPONSÁVEIS: Arnaldo Mandel, Carlos Eduardo Ferreira, Cristina Gomes Fernandes, Paulo Feofiloff, Yoshiharu Kohayakawa.

PRÉ-REQUISITOS: MAC0110.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA:

P. Feofiloff, Algoritmos em Linguagem C, Elsevier, 2009.
E.S. Roberts, Programming Abstractions in C: a Second Course in Computer Science, Addison-Wesley, 1997.
R. Sedgewick, Algorithms in C, 3rd. ed., Parts 1-4, Addison-Wesley, 1998.
R. Sedgewick, K. Wayne, Introduction to Programming in Java, Addison-Wesley, 2008.
R. Sedgewick, K. Wayne, Algorithms, 4th. ed., Addison-Wesley, 2011.

OBSERVAÇÃO: Disciplina obrigatória nos currículos do BCC.

[Veja dados da disciplina no JúpiterWeb]

Alguns dos oferecimentos da disciplina: 1997/2, 1998/2, 1999/2, 1999/2, 2000/2, 2000/2, 2001/1, 2001/2, 2002/1, 2002/2, 2002/2 2006/2, 2012/2, 2013/2, 2015/2.