Desenho e Análise de Algoritmos (CC211)

2013/2014

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto



Datas dos testes: consultar a ficha da unidade curricular no Sigarra.



Teste Prático (7 janeiro 2014)

Durante o teste prático os estudantes terão acesso ao ambiente de programação habitual dos laboratórios do Departamento (mas sem acesso à internet).
Terão acesso ainda ao código que se encontra no arquivo DAA1213_EstruturasDados.tgz.
O teste prático tem início às 14:00 (duração de 2h). Deverá decorrer em dois turnos e será divulgada a distribuição dos estudantes por salas e por turnos.





Alguns Apontamentos

[ Última atualização: 14.12.2013; não inclui toda a matéria já lecionada. ]

Semana 13 - 16 Dez

Problemas de emparelhamento com preferências.
Algoritmos ávidos (greedy): soluções exatas e aproximadas.

Semana 12 - 09 Dez

Problemas de fluxo e emparelhamento

Resolver "Reforma na Avesso" por redução do problema a um problema de fluxo máximo. Introduzir uma origem s e um destino fictício t. Definir um arco (s,j) de capacidade 1, de s para cada tarefa j. Definir um arco (i,t) de capacidade Ni do nó que identifica a pessoa i para o destino t, sendo Ni o número máximo de tarefas que i aceita realizar. Para cada par (j,i) tal que a pessoa i tem habilitações para desempenhar a tarefa j, considerar um arco (j,i) com capacidade 1.

Alguns links úteis:

Semana 11 - 02 Dez

Programação dinâmica.

Semana 10 - 25 Nov

Programação dinâmica.

Semana 9 - 18 Nov

Resolução de exercícios do concurso DAA1314_3 e do problema "Epidexipterix".



1ºTeste Escrito - 13 Nov

Enunciados: v1, e v2 e v3.

Semana 8 - 11 Nov

Aplicação e adaptação do algoritmo de Dijkstra.



Semana 7 - 4 Nov

Alguns problemas de aplicação dos algoritmos dados para determinar caminhos, determinar as componentes fortemente conexas de um grafo dirigido, e determinar a árvore geradora com peso óptimo (mínimo ou máximo) para um grafo não dirigido com pesos nos ramos.



Semana 6 - 28 Out

Algoritmos em grafos: construção de grafos, noção de percurso/caminho num grafo, pesquisa em largura e em profundidade; ordenação topológica dos nós de um grafo dirigido acíclico, aplicação à determinação do caminho mais longo num grafo dirigido acíclico (adaptação também de pesquisa em profundidade).

Semana 5 - 21 Out

Tipos abstratos de dados (revisão): Listas, Filas, Pilhas e Grafos. Resolução de problemas simples de aplicação. Implementação do algoritmo de Graham para determinar o invólucro convexo.


Semana 4 - 14 Out

Exercitar competências prévias de programação.

Semana 3 - 7 Out

Estudo da complexidade assintótica de alguns algoritmos.

Semana 2 - 30 Set

Ordens de grandeza para estudo da complexidade assintótica de algoritmos.

Semana 1 - 23 Set

Revisão: Escrita de algoritmos em pseudo-código e verificação de correção.

As aulas teóricas e as aulas práticas têm início na semana de 23 de setembro para todas as turmas.


© Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2013/2014

Thu Dec 19 19:38:30 WET 2013