0% acharam este documento útil (0 voto)
4 visualizações2 páginasDesign e Análise de Algoritmos
Este documento descreve os objetivos e as unidades de um curso sobre design e análise de algoritmos. O objetivo é entender várias técnicas de design de algoritmos e como aplicá-las a problemas, além de adquirir uma compreensão do design de algoritmos paralelos e problemas NP-completos. O curso é dividido em 5 unidades que cobrem tópicos como divisão e conquista, algoritmos gananciosos, programação dinâmica, retrocesso, ramificação e limite, correspondência de strings, algoritmos paralelos e algoritmos de aproximação. Cada unidade inclui tanto componentes teóricos quanto práticos para implementar e analisar algoritmos de exemplo.
Traduzido por
ScribdTranslationsDireitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
0% acharam este documento útil (0 voto)
4 visualizações2 páginasDesign e Análise de Algoritmos
Este documento descreve os objetivos e as unidades de um curso sobre design e análise de algoritmos. O objetivo é entender várias técnicas de design de algoritmos e como aplicá-las a problemas, além de adquirir uma compreensão do design de algoritmos paralelos e problemas NP-completos. O curso é dividido em 5 unidades que cobrem tópicos como divisão e conquista, algoritmos gananciosos, programação dinâmica, retrocesso, ramificação e limite, correspondência de strings, algoritmos paralelos e algoritmos de aproximação. Cada unidade inclui tanto componentes teóricos quanto práticos para implementar e analisar algoritmos de exemplo.
Traduzido por
ScribdTranslationsDireitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
DESENHO E ANÁLISE DE ALGORITMOS 3 0 2 4
OBJETIVO
Compreender várias técnicas de design de algoritmos e saber como aplicá-las
essas técnicas para vários problemas. Além disso, fornece uma compreensão de paralelo
design de algoritmos, e fornece a ideia da classe de problemas NP e seu
soluções aproximadas.
UNIDADE - I ANÁLISE E DIVIDA E VENCERÁS 9
Introdução aos Algoritmos – Crescimento de funções – Resolução de equações recursivas:
Método de substituição, Método de iteração e Método mestre - Encontrando o máximo
e Mínimo – Seleção – Multiplicação de Matrizes de Strassen – Convex Hull.
Componente de Laboratório: 6
Implementando alguns algoritmos recursivos e estudando seu tempo teórico vs
tempo empírico - Implementar e analisar o problema de seleção.
UNIDADE – II GULOSO & PROGRAMAÇÃO DINÂMICA 9
Greedy Approach: General Method – Knapsack problem – Minimum cost
árvores geradoras – Problema do caminho mais curto a partir de um único ponto. Programação Dinâmica:
Princípio da optimalidade – Problema do caminho mais curto em todos os pares – Maior comum
subsequência – Problema do vendedor viajante.
Lab Component: 6
Implementar e analisar: problema da árvore geradora mínima e viajante
problema do vendedor
UNIDADE – IIIRETROCESSO E BRANCH-AND-BOUND 9
Retrocesso: Método geral - Problema das 8 Rainhas - Coloração de grafos - Soma de
problema do subconjunto – ciclo hamiltoniano. Ramificação e Limite – problema da mochila –
Problema do caixeiro viajante.
Lab Component: 6
Implemente e analise: Soma de subconjuntos - Implemente baseado em Branch and Bound
problema do vendedor viajante e comparação com programação dinâmica.
UNIDADE - IV CORRESPONDÊNCIA DE STRING E ALGORITMOS PARALELOS 9
Correspondência de strings simples – Algoritmo de correspondência de strings KMP – Boyer Moore String
algoritmo de correspondência. Algoritmos paralelos: modelos PRAM - Cálculo de prefixo -
Classificação de listas – Encontrando o máximo – Ordenação por mesclagem ímpar-par – Ordenação em uma malha
– Ordenação Bitônica.
Componente de Laboratório: 6
Implemente e compare algoritmos simples de correspondência de strings e KMP. Implemente
algoritmo de computação de prefixo usando múltiplas threads ou processos.
UNIDADE – V PROBLEMAS NP E ALGORITMOS DE APROXIMAÇÃO 9
NP-completude – Verificação em tempo polinomial – Teoria da reduziuibilidade – Circuito
satisfiability - NP-completeness proofs – NP-complete problems: Vertex cover,
Ciclo Hamiltoniano e problemas do Caixeiro Viajante – Algoritmos de Aproximação
– Algoritmos de aproximação para os problemas de cobertura de vértices e vendedor viajante.
Lab Component: 6
Implemente problemas de cobertura de vértices e do caixeiro viajante usando aproximação
algoritmo.
TOTAL: 45 + 30 = 75
LIVROS DIDÁTICOS:
1. Ellis Horowitz, Sartaj Sahni e Sanguthevar Rajasekaran, Fundamentos
de Algoritmos de Computador, Segunda Edição, Universities Press, Hyderabad,
2008.
2. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest e Clifford
Stein, Introdução aos Algoritmos, Segunda Edição, Prentice Hall da Índia
Nova Délhi, 2007
REFERENCES:
1. Kenneth A. Berman e Jerome L. Paul, Algoritmos, Cengage Learning
Edição da Índia, Nova Deli, 2002.
2. Sara Baase e Allen Van Gelder, Algoritmos de Computador – Introdução a
Design & Análise, Terceira Edição, Pearson Education, Nova Délhi, 2000.