Concepção e Análise de Algoritmos

Código:

EIC0110

Sigla:

CAL

Áreas Científicas
Classificação	Área Científica
OFICIAL	Programação

Ocorrência: 2010/2011 - 2S

Ativa?	Sim
Página Web:	http://paginas.fe.up.pt/~rossetti/rrwiki/doku.php?id=teaching:1011:cal:start
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIEIC	136	Plano de estudos a partir de 2009/10	2	-	6	56	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta Unidade Curricular tem por objectivo complementar e aprofundar os conhecimentos assimilados nas disciplinas de "Programação" e de "Algoritmos e Estruturas de Dados", nomeadamente pela introdução de técnicas de concepção implementação de algoritmos eficientes para a resolução de diferentes tipos de problemas, assim como a sua análise e avaliação. Pretende-se dotar os estudantes das seguintes competências:

* conhecer e saber aplicar algoritmos eficientes em grafos, conjuntos e cadeias de caracteres;
* conhecer e saber aplicar técnicas genéricas de concepção de algoritmos;
* conhecer alguns problemas intratáveis e algoritmos que fornecem soluções aproximadas para alguns deles.

No final da Unidade Curricular, espera-se que o estudante seja capaz de caracterizar o problema que lhe é apresentado, formalizá-lo, conceber algoritmos eficientes para solucioná-los, e avaliar a solução concebida.

Programa

1. Técnicas de concepção de algoritmos: divisão e conquista; algoritmos gananciosos ("greedy"); programação dinâmica; algoritmos de retrocesso ("backtracking"); algoritmos probabilísticos.

2. Representação e formalização de algoritmos, análise da sua complexidade (temporal e espacial); verificação e correcção dos algoritmos.

3. Estruturas de dados avançadas: filas de prioridade com alteração de prioridade; conjuntos disjuntos.

4. Algoritmos eficientes em grafos: visita em largura e em profundidade; ordenação topológica; componentes biconexos; componentes fortemente conexos; caminho mais curto; árvore de expansão mínima; fluxo máximo e fluxo máximo de custo mínimo em redes de transporte; circuito de Euler e problema do carteiro chinês; problemas de emparelhamento ("matching") e casamentos estáveis.

5. Algoritmos em "strings": pesquisa exacta ("string matching"); pesquisa aproximada; "substring" comum mais comprida; compressão de texto.

6. Problemas intratáveis: redução de problemas; teoria dos problemas NP-completos; exemplos de problemas intratáveis em grafos; algoritmos que fornecem soluções aproximadas em tempo polinomial para alguns problemas.

Bibliografia Obrigatória

Thomas H. Cormen... [et al.]; Introduction to algorithms. ISBN: 978-0-262-53305-8
Steven S. Skiena; The algorithm design manual. ISBN: 0-387-94860-0
Sedgewick, Robert; Algorithms in C++ Part 5: Graph Algorithms, 3/E, Addison-Wesley Professional, 2001. ISBN: 0201361183

Observações Bibliográficas

Outros links e materiais de apoio serão disponibilizados no sítio Web da Unidade Curricular.

Métodos de ensino e atividades de aprendizagem

As aulas teóricas são usadas para a exposição formal da matéria, acompanhada da apresentação de exemplos e sua discussão.

As aulas práticas são usadas para a resolução de exercícios e desenvolvimento de pequenos programas em C++ para testar os algoritmos desenvolvidos.

Os estudantes também deverão realizar trabalhos práticos, em grupos de 2 (dois) estudantes no máximo. Apesar de realizados em grupo, a avaliação terá em consideração o desempenho individual de cada estudante no grupo.

Software

Cute C++ Unit Testing Framework (plug-in p/ Eclipse)
Eclipse C++

Palavras Chave

Ciências Tecnológicas > Tecnologia > Tecnologia de computadores > Tecnologia de software
Ciências Físicas > Matemática > Algoritmos

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	60,00
Exame (normal + recurso)	Exame	4,00		2011-07-15
Trabalho de Grupo 1 - grafos	Trabalho escrito	24,00		2011-05-09
Trabalho de Grupo 2 - strings/ficheiros	Trabalho escrito	16,00		2011-05-30
	Total:	-	0,00

Componentes de Ocupação

Descrição	Tipo	Tempo (Horas)	Data Conclusão
Estudo individual	Estudo autónomo	60	2011-07-15
	Total:	60,00

Obtenção de frequência

Para obtenção de frequência:
* O estudante deverá cumprir com o requisito do número máximo de faltas permitido às aulas práticas;
* Em cada componente da avaliação distribuída, o estudante deverá obter nota superior a 40% naquele momento de avaliação.

Estudantes que tenham frequentado a Unidade Curricular "Concepção e Análise de Algoritmos" (CAL) no ano lectivo anterior e tenham obtido nota de frequência, estão dispensados de frequentar a cadeira, tendo apenas de realizar o exame final (EF). No entanto, se quiserem melhorar a nota da componente distribuída, terão de frequentar a unidade curricular novamente.

Fórmula de cálculo da classificação final

A nota final é baseada nas seguintes componentes:

* Exame final (EF) com consulta condicionada, com duração de 2 horas
* Componente distribuída (CD), composta por dois trabalhos práticos de grupo:
- Trabalho de grupo 1 (T1) – Grafos
- Trabalho de grupo 2 (T2) – strings/ficheiros

A classificação CD correspondente à componente distribuída é calculada da seguinte forma:

CD = 0,60 *T1 + 0,4 * T2, onde T1 >= 8 valores e T2 >= 8 valores

A nota final (NF) é calculada da seguinte forma:

NT = 0,6 * EF + 0,4 * CD, onde EF >= 8 valores

Avaliação especial (TE, DA, ...)

Os estudantes que frequentam a Unidade Curricular ao abrigo de estatutos especiais têm os mesmos requisitos de avaliação de frequência dos estudantes regulares, devendo realizar os trabalhos práticos nas épocas estabelecidas. Poderá, entretanto, acordar com o docente das aulas práticas uma data e hora para apresentação dos trabalhos fora dos horários da aula prática.

Melhoria de classificação

A classificação distribuída pode ser melhorada na ocorrência seguinte da unidade curricular.

Observações

É aconselhável que os estudantes tenham cursado previamente as Unidades Curriculares de "Programação" e de "Algoritmos e Estruturas de Dados" para potenciar melhor aproveitamento.