Tópicos Avançados em Algoritmos

Código:

CC445

Sigla:

CC445

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2013/2014 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~ap/taa/1314
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
M:CC	11	PE do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
MI:ERS	4	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5

Língua de trabalho

Português

Objetivos

Compreender a relação entre o desenho, a prova de correcção e a análise de algoritmos. Aprender técnicas gerais úteis na implementação de novos algoritmos. Conhecer alguns dos principais algoritmos nalguns domínios específicos. Experiência prática na aplicação de algoritmos genéricos a problemas concretos.

Resultados de aprendizagem e competências

Compreender a relação entre o desenho, a prova de correcção e a análise de algoritmos. Aprender técnicas gerais úteis na implementação de novos algoritmos. Conhecer alguns dos principais algoritmos nalguns domínios específicos. Experiência prática na aplicação de algoritmos genéricos a problemas concretos.

Modo de trabalho

Presencial

Programa

Fundamentos da análise de algoritmos, análise amortizada Divisão e conquista, recorrências Algoritmos aleatorizados Ordenação linear, seleção ordinal Hash universal e perfeito Programação dinâmica e algoritmos ávidos Algoritmos multialinhados (paralelos) Emparelhamento de cadeias

Bibliografia Obrigatória

000102107. ISBN: 9780262033848

Métodos de ensino e atividades de aprendizagem

Aulas teóricas expositivas. Em cada semana são propostos exercícios e problemas a resolver, e na aula prática as resoluções são apresentadas pelos alunos e discutidas, com avaliação individual.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Participação presencial	20,00
Teste	80,00
Total:	100,00

Obtenção de frequência

É exigida a classificação global de 8 nos treinos (ver abaixo).

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

Há duas componentes de avaliação: os treinos e as provas. A classificação final é a média pesada de 80% da das provas e 20% da dos treinos. Quanto aos treinos: - consistem na resolução individual dos problemas propostos semanalmente (em 12 semanas); - em cada aula prática é individualmente avaliada a resposta aos problemas propostos na semana anterior; - cada avaliação resulta em 0 (nulo), 1 (fraco), 2 (satisfatório) ou 3 (bom); - a classificação global é a média das 8 melhores prestações (das 12), normalizada para 20; - é exigida a classificação final de 8 para ter frequência. Quanto às provas: - consistem em 3 testes e no exame final; - a classificação provisória é a média dos 3 testes; - a classificação final derivada da provisória das provas (ponderada com a dos treinos) dispensa de exame; - indo a exame (com ou sem dispensa), a classificação das provas é a do exame se esta é melhor que a provisória, senão é a média das duas, ficando garantida a aprovação com 10 no caso de ter havido dispensa.

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

Um estudante-trabalhador pode decidir, no início do semestre, ser avaliado apenas por exame, com dispensa de frequência. Nesse caso a classificação final é simplesmente a do exame, para aprovação ou melhoria.

Melhoria de classificação

A melhoria de classificação é obtida apenas por exame no caso de classificação obtida no ano anterior. A melhoria de quem obteve frequência e aprovação na época normal é feita usando a classificação do novo exame (em época de recurso ou especial) em vez do anterior na fórmula de classificação final acima descrita.