Desenho e Análise de Algoritmos

Código:

CC2001

Sigla:

CC2001

Nível:

200

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

Ocorrência: 2014/2015 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1415/
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	60	Plano de estudos a partir de 2014	2	-	6	56	162
MI:ERS	105	Plano Oficial desde ano letivo 2014	2	-	6	56	162

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.

Modo de trabalho

Presencial

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

Conhecimentos de programação (C/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" e de "Estruturas de Dados", ou equivalente.

Programa

Complexidade algorítmica: análise assintótica, recorrências, algumas classes de complexidade. Técnicas de desenho de algoritmos: dividir para conquistar, algoritmos ávidos e programação dinâmica. Estruturas de dados especializadas: filas de prioridade, conjuntos disjuntos e árvores de pesquisa equilibradas. Algoritmos de grafos: pesquisa em largura e em profundidade, árvores de cobertura mínima, caminhos mais curtos, problemas de fluxo.

Bibliografia Obrigatória

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 3rd ed, 2009)
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8 (S. Skiena. The Algorithm Design Manual, 2nd Edition, 2008)
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

R. Sedgewick and K. Wayne; Algorithms, 4th Edition, Addison-Wesley, 2011. ISBN: 978-0321573513 (material auxiliar disponível em http://algs4.cs.princeton.edu/)
S. Halim and F. Halim; Competitive Programming, 1st Edition, 2011 (Livro disponível grátis em https://sites.google.com/site/stevenhalim/)

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	80,00
Teste	20,00
Total:	100,00

Componentes de Ocupação

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

Obtenção de frequência

Não serão registadas as presenças nem marcadas faltas nas aulas teóricas e nas práticas laboratoriais. No entanto, semanalmente serão feitos questionários online cujo preenchimento é obrigatório. Cada questionário estará online durante 7 dias e irá conter perguntas de escolha múltipla relativas à materia lecionada na semana anterior. A nota obtida em cada um dos questionário não contará para avaliação, mas para obter frequência um estudante terá de ter respondido a pelo menos 80% dos questionários.

Irão existir 12 questionários, pelo que o número máximo de questionários não preenchidos é de 2.

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 igual a zero.

 

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 (avaliado de 0 a 4, peso de 20% na nota final); Nota mínima, NP>0.


• E: exame escrito final (peso de 80% na nota final)


• F: média de dois testes escritos (TE1 e TE2) a realizar durante o semestre para dispensa de exame final (TE1 e TE2 incidirão sobre conjuntos de matérias diferentes). Os estudantes com classificação inferior a 6.0 no primeiro teste não poderão realizar o segundo. F = 0.5*TE1 + 0.5*TE2. Para dispensa de exame, F>=7.0.

Classificação da época normal: C = max(E,F)*0.8 + NP >= 9.5
Classificação da época de recurso: C = E*0.8 + 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 teóricas e práticas. O teste de programação é obrigatório consiste na submissão no sistema Mooshak da resolução de problemas relacionados com os propostos nas aulas práticas.

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

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

Melhoria de classificação

Os estudantes aprovados em 2013/2014 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 2014/2015 (incluindo a relativa aos exercícios propostos nas aulas práticas).