Programa
Análise e Síntese de Algoritmos
Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda
Programa
Introdução à análise e síntese de algoritmos; Fundamentos matemáticos para análise de algoritmos; Revisão de algoritmos de ordenação: Mergesort; Heapsort; Quicksort; algoritmos de ordenação não baseados em comparação; Revisão de estruturas de dados: Listas; Pilhas; Filas; Tabelas de dispersão; Árvores de procura binária; Árvores equilibradas; Análise amortizada. Exemplos de aplicação: Amontoados Binomiais; Introdução à Geometria Computacional. Algoritmos em grafos: Algoritmos elementares; Árvores abrangentes de menor custo; Caminhos mais curtos; Fluxos máximos; Introdução à Programação Linear: Algoritmo Simplex; Técnicas de síntese de algoritmos: Programação dinâmica; Algoritmos gananciosos; Algoritmos para emparelhamentos máximos; Introdução à complexidade: Classes P e NP; Problemas NP-completos; Teorema de Cook; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis;
Análise e Síntese de Algoritmos
Licenciatura (5 anos) em Engenharia Informática e de Computadores - Alameda
Programa
Revisão de AED: algoritmos, análise de algoritmos, síntese de algoritmos, notação assimptótica, somatórios e recorrências. O teorema Mestre. Amontoados: definições e operações. O algoritmo HeapSort. Operações sobre amontoados. Algoritmos em grafos: Largura-Primeiro, Profundidade-Primeiro, Componentes fortemente ligados e ordenação topológica. Introdução às estruturas de dados para conjuntos disjuntos. Árvores abrangentes de menor custo: algoritmo genérico, algoritmos de Kruskal, Boruvka e Prim. Caminhos mais curtos: algoritmo de Dijkstra, algoritmo de Bellman-Ford, Caminhos mais curtos em grafos dirigidos aciclicos. Caminhos mais curtos entre todos os pares: definições, solução recursiva, algoritmo de Floyd-Warshall, fecho transitivo e algoritmo de Johnson. Fluxos máximos: definições, método de Ford-Fulkerson, teorema do Fluxo Máximo Corte Mínimo, análise da complexidade do método de Ford-Fulkerson, algoritmo de Edmonds-Karp, complexidade do algoritmo de Edmonds-Karp, emparelhamento bipartido máximo, algoritmos baseados em pré-fluxos, o algoritmo de pré-fluxos genérico, o algoritmo relabel-to-front. O problema dos fluxos de custo mínimo. Introdução à programação linear: definições, as formas standard e slack, a operação de &#39;pivoting&#39;, o algoritmo Simplex, cálculo de uma solução básica inicial exequível, dualidade. Programação dinâmica. Exemplos de aplicação: multiplicação de cadeias de matrizes, o problema da mochila, sub-sequência comum de maior comprimento, realizar trocos. Algoritmos greedy. Exemplos de aplicação: actividades compatíveis, problema da mochila, minimizar tempo no sistema, códigos de Huffman. Algoritmos para emparelhamento de cadeias de caracteres: algoritmo elementar, algoritmo baseado em autómatos finitos, algoritmo de Knuth-Morris-Pratt. Introdução aos problemas NP-Completos: definições, classe P e NP, problemas NP-completos. Exemplos de demonstrações de problemas NP-Completos. Algoritmos de aproximação para problemas NP-difíceis. <br />
Análise e Síntese de Algoritmos
Licenciatura (5 anos) em Ciências Informáticas
Programa
Revisão de AED: algoritmos, análise de algoritmos, síntese de algoritmos, notação assimptótica, somatórios e recorrências. O teorema Mestre. Amontoados: definições e operações. O algoritmo HeapSort. Operações sobre amontoados. Algoritmos em grafos: Largura-Primeiro, Profundidade-Primeiro, Componentes fortemente ligados e ordenação topológica. Introdução às estruturas de dados para conjuntos disjuntos. Árvores abrangentes de menor custo: algoritmo genérico, algoritmos de Kruskal, Boruvka e Prim. Caminhos mais curtos: algoritmo de Dijkstra, algoritmo de Bellman-Ford, Caminhos mais curtos em grafos dirigidos aciclicos. Caminhos mais curtos entre todos os pares: definições, solução recursiva, algoritmo de Floyd-Warshall, fecho transitivo e algoritmo de Johnson. Fluxos máximos: definições, método de Ford-Fulkerson, teorema do Fluxo Máximo Corte Mínimo, análise da complexidade do método de Ford-Fulkerson, algoritmo de Edmonds-Karp, complexidade do algoritmo de Edmonds-Karp, emparelhamento bipartido máximo, algoritmos baseados em pré-fluxos, o algoritmo de pré-fluxos genérico, o algoritmo relabel-to-front. O problema dos fluxos de custo mínimo. Introdução à programação linear: definições, as formas standard e slack, a operação de &#39;pivoting&#39;, o algoritmo Simplex, cálculo de uma solução básica inicial exequível, dualidade. Programação dinâmica. Exemplos de aplicação: multiplicação de cadeias de matrizes, o problema da mochila, sub-sequência comum de maior comprimento, realizar trocos. Algoritmos greedy. Exemplos de aplicação: actividades compatíveis, problema da mochila, minimizar tempo no sistema, códigos de Huffman. Algoritmos para emparelhamento de cadeias de caracteres: algoritmo elementar, algoritmo baseado em autómatos finitos, algoritmo de Knuth-Morris-Pratt. Introdução aos problemas NP-Completos: definições, classe P e NP, problemas NP-completos. Exemplos de demonstrações de problemas NP-Completos. Algoritmos de aproximação para problemas NP-difíceis.