MAC0121: Ementa oficial
Esta é a ementa oficial da disciplina
MAC0121 (Algoritmos e Estruturas de Dados I)
para 2015.
(Até recentemente,
a disciplina era conhecida como MAC0122.)
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.
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 (realocação) 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.)
Carga horária semanal e número de créditos
Créditos Aula: 4
Carga Horária Total: 60h
Tipo: Semestral
Ativação: 1/1/2015
Critério de avaliação
Média ponderada de provas e exercícios.
Bibliografia
-
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.
Pré-Requisitos
MAC0110 (Introdução à Computação)
(veja a ementa no
Sistema Júpiter da USP).
Fonte
Confira a ementa de MAC0121 no
catálogo do IME
e no
Sistema Júpiter da USP.
Ementa de MAC0122
A disciplina MAC0122 (Princípios de Desenvolvimento de Algoritmos)
é a versão antiga de MAC0121.
A título de comparação,
eis a ementa de MAC0122:
Objetivos
Estudo, através de exemplos, da correção,
da análise de eficiência e do desenvolvimento de algoritmos
e de suas estruturas de dados básicas.
Programa
-
Alguns exemplos de algoritmos usando pilhas e filas.
-
Introdução aos conceitos de listas ligadas e ponteiros.
-
Algoritmos recursivos.
-
Busca, inserção e remoção em vetores e listas ligadas.
-
Busca binária.
-
Algoritmos de ordenação (inserção, seleção, mergesort,
heapsort, quicksort, etc.).
-
Algoritmos de casamento de padrões.
-
Alguns exemplos de algoritmos de enumeração e otimização sobre seqüências.
-
Prova informal da correção de algoritmos.
-
Estudo empírico da eficiência de algoritmos.
Carga horária semanal e número de créditos
4 horas, 4 créditos-aula.
Critério de avaliação
Média ponderada de provas e exercícios.
Bibliografia
-
N. Wirth,
Algorithms and Data Structures,
Prentice Hall, 1986.
-
R. Sedgewick,
Algorithms in C, 3rd. ed., vol. 1,
Addison-Wesley/Longman, 1998.
-
N. Ziviani,
Projeto de Algoritmos com Implementações em Pascal e C,
Pioneira, 1993.
-
J. Bentley,
Programming Pearls,
Addison-Wesley, 1986.
-
J. Bentley,
More Programming Pearls,
Addison-Wesley, 1988.
-
A.V. Aho, J.D. Ullman,
Foundations of Computer Science,
Computer Science Press, 1992.
Pré-Requisitos
MAC0110 (Introdução à Computação)
Fonte
Confira a ementa de MAC0122 no
catálogo do IME
e no
Sistema Júpiter da USP.