Este documento faz parte da [Proposta 2022 de Thanos][main].

[main]: /HTv-fjHGRseioBgvKYqf0w

--------

[TOC]

--------

# ALGO: Introdução aos Algoritmos

==Este conteudo e a disciplina inteira devem ser revistos junto com o conteúdo e a CH das disciplinas EDB1--2 para esclarecer diferenças e evitar duplicações desnecessárias (sem mudanças essenciais de ponto de vista). As ementas/CH escritas nas disciplinas EDB1--2 cumprem a maioria dos pontos que são normalmente vistos em disciplinas de Algoritmos em cursos universitários.==

## EDBs atualmente

* **EDB1:**
1. Algoritmos de busca
2. Algoritmos de ordenação
3. Complexidade de algoritmos (abordagem experimental)
4. Verificação de corretude e término
5. Vetores dinâmicos
6. Arranjos com sentinelas
7. Listas sequenciais com alocação estática; casos especiais (restrições): filas, pilhas e deques
8. Listas encadeadas com alocação dinâmica
9. Estruturas auto-ajustáveis (listas e conjuntos disjuntos)
0. Tabelas de dispersão.
* **EDB2:**
1. Complexidade assintótica
2. Análise de algoritmos
3. Recorrências e soluções de recorrências.
2. Desempenho de algoritmos recursivos e iterativos
4. Árvores.
5. Listas de Prioridade. Heap.
6. Árvores de busca. Árvores binárias de busca.
7. Árvore balanceadas
8. Árvores digitais
9. Conjuntos disjuntos
9. Estruturas auto-ajustáveis e análise amortizada
10. Casamento de cadeias

## Ementa

1. Notação O e notações relacionadas.
1. Custo de algoritmo: tempo e espaço; análise de pior caso e caso médio
1. Estratégias básicas de desenhar algoritmos: top-down, divisão e conquista, critéria de pior caso e caso médio, custos asintóticos.
1. Relações de recorrências, o teorema Mestre da Análise de Algoritmos.
1. Estruturas de dados apropriadas: arranjos, listas, pilhas, filas, arvores, heaps, filas de prioridade, grafos.
1. Applicações em ordenação e busca, criptografía, algorítmos de matrizes, caminho mais curto e spanning tree.
1. Introdução aos algoritmos de otimização discreta: programação dinâmica, algoritmos gulosos.
1. Algoritmos de grafos: busca em profundidade, busca em largura.
1. Introdução à complexidade computacional.

## Objetivos de aprendizagem

1. Adotar bons princípios de criação de algoritmos.
1. Aprender como analizar algoritmos: achar os worst-case e average-case custos; demonstrar corretude e terminação.
1. Familiarizar com estruturas de dados fundamentais e com as melhores maneiras de implementá-las.
1. Familiarizar com a descrição de algoritmos tanto em estilo procedural quanto em funcional.

## Pointers

* Teoria da complexidade
* Criptografia

## Bibliografia

1. Dasgupta, Papadimitriou, Vazirani: [Algorithms][dpv]
http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf
1. Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms ["CLRS"]

----

[dpv]: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf