Disciplina Curricular
Desenho e Análise de Algoritmos DAAlgo
Mestrado Bolonha em Engenharia Informática - 3_MEI 2012/13
Contextos
Grupo: 3_MEI 2012/13 > 2º Ciclo > Parte Escolar > Ramos > Arquitetura, Sistemas e Redes de Computadores > Optativas > 748_1º Ano do Mestrado em Eng. Inf. - GO (ASRC) > 2º Semestre
Período:
Grupo: 3_MEI 2012/13 > 2º Ciclo > Parte Escolar > Ramos > Sistemas de Informação > Optativas > 751_1º Ano do Mestrado em Eng. Inf. - GO (SI) > 2º Semestre
Período:
Grupo: 3_MEI 2012/13 > 2º Ciclo > Parte Escolar > Ramos > Interação e Conhecimento > Optativas > 750_1º Ano do Mestrado em Eng. Inf. - GO (IC) > 2º Semestre
Período:
Grupo: 3_MEI 2012/13 > 2º Ciclo > Parte Escolar > Ramos > Engenharia de Software > Optativas > 749_1º Ano de Mestrado em Eng. Inf. - GO (ES) > 2º Semestre
Período:
Peso
6.0 (para cálculo da média)
Objectivos
Esta unidade curricular objetiva desenvolver um conjunto de competências avançadas para complementar o conhecimento padrão de algoritmos e estruturas de dados. Após conclusão da unidade curricular, os alunos deverão ser conseguir: analisar a complexidade de algoritmos; saber decompor problemas para obter ganhos de desempenho; modelar problemas em diversos paradigmas; aplicar um conjunto de técnicas de desenho e análise para problemas no contexto de aplicações computacionais, como desenhar algoritmos de aproximação polinomiais para tarefas de complexidade exponencial ou desenvolver algoritmos aleatórios para resolução de tarefas.
Programa
Modelação de problemas com grafos. Algoritmos de pesquisa (pesquisa por retrocesso, pesquisa heurística) e de pertença (bloom filters, árvores prefixas, conjuntos disjuntos). Decomposição de Problemas (divide-and-conquer, algoritmos gananciosos, programação dinâmica). Programação com restrições. Algoritmos randomizados (Monte-Carlo, Las-Vegas, algoritmo de Metropolis). Elementos de Teoria da Complexidade. Algoritmos de Aproximação. Programação Probabilística.
Métodos de ensino e avaliação
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios. Avaliação contínua baseada no trabalho realizado nas aulas teórico-práticas, eventualmente completado fora da sala de aula. Projeto de investigação, envolvendo a análise de um problema, e o desenho e implementação de uma solução. Estudo aprofundado e apresentação oral de um tópico relacionado com as matérias lecionadas.