Computação 2

Oferecimentos

Turma S24 - 2009.1 - Professor Adolfo Neto - Moodle DAINF

Links

• http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
• http://en.wikibooks.org/wiki/Algorithm_implementation/Search/Binary_search
• http://en.wikipedia.org/wiki/Binary_search

Assuntos

• Algoritmos de Busca
• Algoritmos de Ordenação

Plano de Ensino

OBJETIVO Habilitar os alunos ao desenvolvimento de algoritmos avançados, bem como à implementação destes algoritmos utilizando uma linguagem de programação. Ao final do curso, o aluno deverá estar capacitado ao desenvolvimento de algoritmos avançados que servirão de apoio na resolução de problemas em Engenharia e em Ciências Exatas.

EMENTA Fundamentos do desenvolvimento de algoritmos. Noções básicas de complexidade de algoritmos. Algoritmos de Busca. Algoritmos de Ordenação. Estruturas de dados. Algoritmos com Matrizes. Algoritmos com Grafos.

ITEM	EMENTA	CONTEÚDO
1	Fundamentos do desenvolvimento de algoritmos.	Conceitos básicos para a representação e a implementação de algoritmos e estruturas de dados. Exemplos e aplicações.
2	Noções básicas de complexidade de algoritmos.	Contagem de comparações e trocas. Tempo de execução. Análise de pior caso. Análise de caso médio. Notação assintótica. Comparação entre algoritmos.
3	Algoritmos de Busca.	Conceitos em algoritmos de busca. Busca linear. Busca binária. Análise simplificada da complexidade dos algoritmos.
4	Algoritmos de Ordenação.	Conceitos em algoritmos de ordenação. Algoritmos internos básicos: bolha, inserção, seleção, intercalação e “quicksort”. Análise simplificada da complexidade dos algoritmos.
5	Estruturas de dados.	Conceitos de estruturas de dados. Organização dos dados num programa. Principais estruturas de dados (pilhas, filas, listas, árvores e grafos): representação e implementação de operações. Exemplos e aplicações.
6	Algoritmos com Matrizes.	Algoritmos avançados sobre matrizes. Estudos de casos: algoritmos para multiplicação de matrizes, algoritmos para resolução de sistemas de equações lineares, algoritmos para inversão de matrizes.
7	Algoritmos com Grafos.	Algoritmos elementares de grafos. Algoritmos para gerar árvores de amplitude mínima. Algoritmos para encontrar caminhos mais curtos de única origem. Algoritmos para encontrar caminhos mais curtos de todos os pares. Algoritmos para resolver o problema do fluxo máximo.

REFERÊNCIAS

Referências Básicas: FEOFILOFF, Paulo. Algoritmos em Linguagem C. Rio de Janeiro: Campus/Elsevier, 2009. TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe. Estruturas de dados usando C. São Paulo: Pearson Makron Books, 2005. 884 p. SCHILDT, Herbert. C: completo e total. 3. ed., rev. e atual. São Paulo: Makron, 1997.

Referências Complementares: CORMEN, T.H.; LEISERSON, C.E.; RIVEST,R.L.; STEIN, C. Algoritmos: Teoria e Prática. Tradução da segunda edição americana. Rio de Janeiro: Campus, 2002. ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. São Paulo: Thomson, c2007. 621 p. ISBN 8522105251 ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 5. ed. São Paulo: Pioneira, c1999. 267 p. ; (Pioneira Informática) ISBN 85-221-0174-4 WIRTH, Niklaus. Algoritmos e estruturas de dados. Rio de Janeiro: LTC, 1999. 255 p. : ISBN 85-216-1190-0 DROZDEK, Adam. Estrutura de dados e algoritmos em C++. São Paulo: Thomson, c2002. 579 p. ISBN 8522102953 PEREIRA, Silvio do Lago. Estrutura de dados fundamentais: conceitos e aplicações. 12. ed., rev. e atual. São Paulo: Érica, 2008. 264 p. ISBN 9788571943704 LAFORE, Robert (Robert W.) Estruturas de dados & algoritmos em Java. Rio de Janeiro: Ciência Moderna, 2004. 702 p. ISBN 85-7393-375-5 PREISS, Bruno R.. Estruturas de dados e algoritmos: padrões de projetos orientados a objetos com Java. Rio de Janeiro: Campus, c2001 566 p. ISBN 9788535206937 GOODRICH, Michel T.. Estruturas de dados e algoritmos em Java. 4 ed. Porto Alegre, RS: Bookman, 2007. 600 p. ISBN 978-85-60031-50-4 SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: LTC, c1994. 320 p. ISBN 85-216-1014-9 HOROWITZ, Ellis; SAHNI, Sartaj. Fundamentos de estruturas de dados. 3. ed. Rio de Janeiro: Campus, 1987. 494 p. ISBN 85-7001-422-8

Sistema de Avaliação: (descrição do estabelecido no Regulamento Didático-Pedagógico de cada curso)