A tabela as seguir apresenta todas as disciplinas com vagas disponíveis para os discentes do Curso de ENGENHARIA COMPUTACIONAL (65B) da Universidade Federal de Juiz de Fora (UFJF) no período letivo atual. Os horários e os docentes responsáveis por cada disciplina podem ser consultados clicando na turma desejada.
Ressalta-se que o Curso de Engenharia Computacional da UFJF é ofertado em período integral, com aulas de segunda a sexta-feira, podendo ocorrer nos turnos matutino (8h às 12h), vespertino (14h às 18h) ou noturno (19h às 23h), conforme estabelecido na grade curricular.
Plano de Ensino
Disciplina: DCC001 - ANALISE E PROJETO DE ALGORITMOS
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Ementa
Fundamentos Matemáticos para Análise de Algoritmos; Análise Assintótica de Algoritmos; Paradigmas de Projeto de Algoritmos; Algoritmos Eficientes para Ordenação, Comparação de Sequências, Problemas em Grafos; Fundamentos de Complexidade Computacional, Redução entre Problemas, Classes P e NP, Problemas NP-Completos.
Conteúdo
1. FUNDAMENTOS MATEMÁTICOS PARA ANÁLISE DE ALGORITMOS: Indução Finita; Crescimento de funções; Notações Assintóticas; Relações de Recorrência; resolução por substituição (indução) e por iteração;
2. ANÁLISE ASSINTÓTICA DE ALGORITMOS: Modelos de computação; Cotas superiores e inferiores; Algoritmos ótimos;
3. PARADIGMAS DE PROJETO DE ALGORITMOS: Projeto por indução; Divisão-e-conquista; Algoritmos gulosos; Programação Dinâmica;
4. ALGORITMOS EFICIENTES: Algoritmos para ordenação: bubble-sort, insertion-sort, merge-sort, heap-sort, quick-sort; Cota inferior para ordenação por comparações; Seleção do k-ésimo e da mediana em tempo linear; Busca binária; Árvore de busca ótima e fatoração ótima para multiplicação de matrizes; Comparação de sequências: maior subsequência comum, algoritmo Knuth-Morris-Pratt para busca de substring; distância de edição; algoritmo Smith-Waterman; Conceito de Análise Amortizada (por exemplo, algoritmo KMP); Algoritmos em Grafos: busca em largura e profundidade; caminho mínimo e algoritmos de Dijkstra e Bellman-Ford; árvore espalhada mínima e algoritmos e Prim e Kruskal; todos os caminhos mínimos e algoritmo de Floyd-Warshall; fluxo máximo e algoritmo de Ford-Fulkerson; Algoritmos geométricos: envoltória convexa: algoritmo da Marcha de Jarvis; ordenação angular e o algoritmo Graham Scan; Cota inferior para envoltória convexa por redução;
5. FUNDAMENTOS DE COMPLEXIDADE COMPUTACIONAL: Redução entre problemas e transferência de cotas; Classe P; Algoritmos não-determinísticos; Verificação polinomial de solução; Classe NP; NP-Completude; Exemplos: SAT, Clique em grafos, Problema da mochila, Soma de subconjuntos, 3-coloração, Caminho e circuito hamiltonianos, Caixeiro viajante, e outros.
2. ANÁLISE ASSINTÓTICA DE ALGORITMOS: Modelos de computação; Cotas superiores e inferiores; Algoritmos ótimos;
3. PARADIGMAS DE PROJETO DE ALGORITMOS: Projeto por indução; Divisão-e-conquista; Algoritmos gulosos; Programação Dinâmica;
4. ALGORITMOS EFICIENTES: Algoritmos para ordenação: bubble-sort, insertion-sort, merge-sort, heap-sort, quick-sort; Cota inferior para ordenação por comparações; Seleção do k-ésimo e da mediana em tempo linear; Busca binária; Árvore de busca ótima e fatoração ótima para multiplicação de matrizes; Comparação de sequências: maior subsequência comum, algoritmo Knuth-Morris-Pratt para busca de substring; distância de edição; algoritmo Smith-Waterman; Conceito de Análise Amortizada (por exemplo, algoritmo KMP); Algoritmos em Grafos: busca em largura e profundidade; caminho mínimo e algoritmos de Dijkstra e Bellman-Ford; árvore espalhada mínima e algoritmos e Prim e Kruskal; todos os caminhos mínimos e algoritmo de Floyd-Warshall; fluxo máximo e algoritmo de Ford-Fulkerson; Algoritmos geométricos: envoltória convexa: algoritmo da Marcha de Jarvis; ordenação angular e o algoritmo Graham Scan; Cota inferior para envoltória convexa por redução;
5. FUNDAMENTOS DE COMPLEXIDADE COMPUTACIONAL: Redução entre problemas e transferência de cotas; Classe P; Algoritmos não-determinísticos; Verificação polinomial de solução; Classe NP; NP-Completude; Exemplos: SAT, Clique em grafos, Problema da mochila, Soma de subconjuntos, 3-coloração, Caminho e circuito hamiltonianos, Caixeiro viajante, e outros.
Bibliografia
AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D. "The Design and Analysis of Computer Algorithms". Addison Wesley Pub. Co.,1974.
TERADA, Routo. "Desenvolvimento de Algoritmos e Estrutura de Dados". Makron Books, 1991.
CORMEN, LEISERSON, RIVEST, STEIN. Algoritmos. Elsevier, 2002.
CAMPELLO, Rui e MACULAN FILHO, Nelson. "Algoritmos e Heurísticas". Editora da UFF, 1994.
TERADA, Routo. "Desenvolvimento de Algoritmos e Estrutura de Dados". Makron Books, 1991.
CORMEN, LEISERSON, RIVEST, STEIN. Algoritmos. Elsevier, 2002.
CAMPELLO, Rui e MACULAN FILHO, Nelson. "Algoritmos e Heurísticas". Editora da UFF, 1994.
Bibliografia(continuação)
Não informado
Bibliografia complementar
Em aberto