Desenho e Análise de Algoritmos (CC211)

2012/2013

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

Exames

Época Normal: Enunciado

Época Recurso: Enunciado [Resolução]

Aulas Práticas

Teste Prático (4 Jan)

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:30 e duração de 2h30. Distribuição por laboratórios.

2º Teste Escrito (12 Dez)

Enunciados: v1, e v2.
[Resolução de v1]

Semana 12 - 10 Dez

Árvores de pesquisa binária (revisões): Folha de exercícios - 2

Semana 11 - 03 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 10 - 26 Nov

Programação dinâmica.
Algoritmos ávidos (greedy): soluções exatas e aproximadas.
Exemplos de estratégias ávidas para alguns problemas: cobertura mínima de conjuntos; mochila (linear); escalonamento de tarefas com duração unitária numa máquina com prazos limite e penalizações (ou lucros).

NB: Resolver primeiramente os problemas assinalados por (*).
Os problemas "T-Shirts XS" e "Caixotes de Morangos II" estão disponíveis no servidor Mooshak (concurso DAA_1213_5, aberto de 24/11 a 10/12).
Os restantes concursos estão também abertos.

Semana 9 - 19 Nov

Material de apoio: (sobre alguns tópicos dados na semana de 12 de Novembro)

Semana 8 - 12 Nov

Aplicação e adaptação do algoritmo de Dijkstra (tentar implementar fila de prioridade suportada por heap, seguindo material apoio) Os problemas estão disponíveis no servidor Mooshak (concurso DAA_1213_4, aberto de 10/11 a 24/11).

Material de apoio:



1º Teste Escrito (6 Nov)

Enunciados: v1,v2,v3,v4. [Resolução de v1]



Semana 7 - 5 Nov

O primeiro teste escrito realiza-se no dia 6 de Novembro, às 16:30.

Aula prática: Completar exercícios propostos anteriormente; variar o algoritmo usado.

Uma resolução dos exercícios 1 e 2 da Aula Prática 2 (semana de 1 de Outubro)

Semana 6 - 29 Out

Algoritmos em Grafos: determinar caminhos, componentes fortemente conexas de um grafo dirigido, árvore geradora com peso óptimo (mínimo ou máximo) para um grafo não dirigido com pesos nos ramos. (*) A resolver na aula prática.

Os problemas "Sociologia", "Óptica Minimalista" e "Linhas Coloridas" estão disponíveis no servidor Mooshak (concurso DAA_1213_3, aberto de 26/10 a 5/11).

Na implementação do algoritmo de Prim deve ser definido um tipo abstracto de dados (TAD) para suporte a uma fila de prioridades mas em que as operações make_priorityQueue(Vs), insert(u,key), extractMin() (ou extractMax()) e decreaseKey(u,new_key) podem não ser O(log |V|) (matéria que será dada em aulas posteriores). Na implementação do algoritmo de Kruskal deve ser definido um TAD para suporte de conjuntos disjuntos, com operações make_set(u), find_set(u), e union(u,v) mas não necessariamente eficiente (matéria que será dada em aulas posteriores). Em qualquer dos casos, pretende-se a caracterização da complexidade dos algoritmos resultantes para os ADTs implementados.

Alguns links úteis:

Semana 5 - 22 Out

Algoritmos em Grafos: construção de grafos, noção de percurso/caminho num grafo, 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). Material de apoio: alguns algoritmos em pseudo-código.

Semana 4 - 15 Out

Algoritmos em Grafos: adaptações da pesquisa em largura.

Algum material de apoio:

Semana 3 - 08 Out

Listas, Filas, e Pilhas (Revisão)
Justificar a correção dos algoritmos implementados. Efetuar análise da complexidade temporal e espacial (nos casos em que é dado um limite superior para um valor, supor antes que esse valor não é constante).

Algum material de apoio:

Semana 2 - 01 Out

Estudo de algoritmos: prova de correção e análise de complexidade.

Semana 1 - 24 Set

Exercitar competências prévias de programação.
Utilizar o sistema Mooshak para validar as resoluções (concurso DAA_1213_1).
Para os problemas assinalados com (*), justificar a correcção do algoritmo implementado e analisar a sua complexidade assimptótica.
Deverão ser resolvidos na aula prática da semana pelo menos os problemas assinalados.
O concurso Mooshak DAA_1213_1 abre a 24/9 e encerra a 14/10. As submissões poderão ser em C, Java ou Python.
Note que não poderá voltar a submeter um programa para o mesmo problema depois de ter obtido "Accepted".

Alguns links úteis:
© Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2012/2013

Last modified: Fri Jan 4 08:38:57 WET 2013