Desenho e Análise de Algoritmos

Código:

CC211

Sigla:

CC211

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

Ocorrência: 2013/2014 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/1314
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:CC	57	Plano de estudos de 2008 até 2013/14	2	-	7,5	-
MI:ERS	101	Plano de Estudos a partir de 2007	2	-	7,5	-

Língua de trabalho

Português

Objetivos

Aprendizagem de técnicas de concepção e análise de algoritmos eficientes.

Resultados de aprendizagem e competências

Enriquecimento do conhecimento sobre modelos genéricos de tipos de problemas e técnicas algorítmicas a eles associadas. Experiência prática na aplicação de algoritmos genéricos a problemas concretos. Competência na análise da complexidade de algoritmos. Compreensão das principais classes de complexidade e da reducibilidade de problemas, com conhecimento de exemplos típicos.

 

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Conhecimentos de programação (C ou JAVA), de algoritmos básicos (de contagem, pesquisa e de ordenação) e de algumas estruturas de dados. Preferencialmente, o estudante deverá ter concluído as unidades curriculares de "Introdução à Programação" (CC111) e de "Estruturas de Dados" (CC114), ou equivalente.

Programa

Complexidade algorítmica: análise assintótica, recorrências, análise amortizada, classes de complexidade P, NP e co-NP. Algoritmos de grafos: tipos de grafos, algoritmos elementares, cobertura mínima, caminhos mais curtos, problemas de fluxo. Estruturas de dados: árvores de pesquisa binária, red-black; heaps e filas de prioridade; conjuntos disjuntos. Programação dinâmica e algoritmos ávidos.

Bibliografia Obrigatória

000102107. ISBN: 9780262033848 hbk (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 3rd ed, 2009)
S. Dasgupta, C.H.Papadimitriou, U.V.Vazirani; Algorithms, McGraw-Hill, 2006. ISBN: 978-0073523408 (disponível on-line em http://www.cs.berkeley.edu/~vazirani/algorithms.html)
J. Kleinberg, E. Tardos; Algorithm Design, Addison-Wesley, 2005. ISBN: 978-0321295354 (slides disponíveis em http://www.cs.princeton.edu/~wayne/kleinberg-tardos/)

Bibliografia Complementar

000074403. ISBN: 0-387-00163-8 (S.Skiena, M.Revilla. Programming Challenges. Springer, 2003)

Métodos de ensino e atividades de aprendizagem

Aulas teóricas para exposição da matéria acompanhada da discussão de alguns exemplos. Aulas práticas laboratoriais para resolução de folhas de exercícios e de problemas em computador ao estilo dos propostos em concursos de programação ACM (análise de problemas, desenvolvimento e implementação de programas, teste e correção) . Proposta de problemas adicionais para resolução extra-aula e com avaliação automática pelo sistema Mooshak.

Software

Linguagens de programação: C, C++, Java ou Python
Programming languages: C, C++, Java or Python
Servidor Mooshak para CC211 (http://mooshak.dcc.fc.up.pt/~daa)

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	85,00
Participação presencial	0,00
Teste	15,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas
Trabalho laboratorial
Total:	0,00

Obtenção de frequência

Serão registadas as presenças às aulas práticas. Perde a frequência por falta de assiduidade o estudante que faltar a mais de 25% das aulas práticas previstas. Perde a frequência por não obtenção de nota mínima numa componente da avaliação o estudante que tenha nota prática inferior a 1.0 (em 3.0) .

O número máximo de faltas às aulas práticas é de quatro.

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

-  NP: nota obtida num teste prático de programação com avaliação automática pelo sistema Mooshak
(ponderação de 3/20 na nota final);  Necessário, NP >= 1.

- E: Exame final  (ponderação 17/20)

- F: média ponderada de dois testes escritos (TE1 e TE2) a realizar durante o semestre para dispensa de exame final (TE2 global). Os estudantes com classificação inferior a 8.0 valores no primeiro teste não poderão realizar o segundo. F = max(0.3 TE1 + 0.7 TE2, TE2) . Para dispensa de exame, F >= 8.0.

Classificação na época normal:   C =  max(E,F)*0.85+NP  >= 9.5

Classificação na época de recurso:   C = E*0.85 + NP >= 9.5

Provas e trabalhos especiais

No decorrer do semestre são realizados dois testes escritos e um teste de programação. As provas escritas (testes e exames) consistem em perguntas gerais e perguntas sobre problemas vistos nas aulas práticas. O teste de programação consiste na submissão no sistema Mooshak da resolução de problemas relacionados com os propostos nas aulas práticas.

Datas dos testes:

     - 1ºTeste Escrito, 13 de novembro de 2013, 14:30, salas FC1 219 e FC1 226

     - 2ºTeste Escrito, 18 de dezembro de 2013, 14:30

     - Teste Prático de Programação, 7 de janeiro de 2014, 14:00-18:00, Labs. 2,3,4 (2H, por turnos)

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

O teste prático é obrigatório para todos os estudantes inscritos.

Melhoria de classificação

Os estudantes aprovados em 2012/2013 que pretendam efetuar melhoria de classificação terão de realizar o exame final e o teste prático Mooshak (não realizarão os testes escritos). O exame incidirá sobre a matéria lecionada em 2013/2014 (incluindo a relativa aos exercícios propostos nas aulas práticas).