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: 2017/2018 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/1718
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:B	0	Plano de Estudos Oficial	3	-	6	56	162
L:CC	67	Plano de estudos a partir de 2014	2	-	6	56	162
L:F	1	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	6	56	162
			3
L:M	8	Plano de Estudos Oficial	2	-	6	56	162
			3
L:Q	0	Plano estudos a partir do ano letivo 2016/17	3	-	6	56	162
MI:ERS	113	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 para alguns tipos de problemas e sobre 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 assintótica 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

Análise assintótica de algoritmos: Notação Big O (O, Ω e Θ), estimativas de tempo de execução, análise de programas iterativos e recursivos;

Ordenação: ordenação como peça básica de outros algoritmos, algoritmos comparativos e não comparativos, pesquisa binária e aplicações diretas e indiretas;

Técnicas de desenho de algoritmos: pesquisa exaustiva, algoritmos ávidos (greedy), dividir-para-conquistar, programação dinâmica;

Algumas estruturas de dados especializadas: filas de prioridade, conjuntos disjuntos;

Árvores binárias de pesquisa balanceadas: árvores AVL e árvores Red-Black.

Algoritmos de grafos: representação de grafos, pesquisas em profundidade e largura, árvore de suporte de custo mínimo, distâncias mínimas, fluxo máximo.

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 com avaliação e feedback automatizado pelo sistema Mooshak.

Software

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

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	85,00
Trabalho laboratorial	15,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas	0,00
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. O número máximo de faltas às aulas práticas é de quatro.

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)

 

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

• NP: nota prática, valendo 15% da nota final, obtida através de um teste prático. Nota mínima de 1 em 3 no teste é requisito para frequência.


• NT: nota teórica, valendo 85% da nota final. Se o calendário escolar para 2017/2018 o permitir, serão realizados dois testes escritos (TE1, TE2) para dispensa de exame final (Exame). Para acesso ao segundo teste escrito, será exigida uma classificação de pelo menos 8.0 valores no primeiro teste. Para dispensa de exame, a classificação do segundo teste deverá ser também de pelo menos 8.0 valores. O segundo teste é global.  T = max(0.4*TE1+0.6*TE2, TE2, FinalExam).


• A classificação final será calculada por  NP + 0.85*NT     (esta classificação deverá ser >= 9.5)
  

  Para dispensa de exame final a classificação dos testes escritos terá de satisfazer max(0.4*TE1+0.6*TE2, TE2) >= 8.

  
  


• Classificação da época de recurso: C = Exame*0.85 + NP >= 9.5, devendo a classificação no exame ser >= 8.


• Casos de fraude académica: será aplicado o regulamento vigente na FCUP/Universidade do Porto.

Provas e trabalhos especiais

No decorrer do semestre são realizados dois testes escritos para dispensa de exame, se o calendário escolar permitir. As provas escritas (testes e exames) incluem perguntas gerais e perguntas sobre problemas vistos nas aulas práticas. 
Será realizado um teste de programação. O teste de programação é obrigatório e será utilizado o sistema Mooshak. Os problemas a resolver estarão relacionados com os propostos nas aulas práticas.

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

A componente prática é obrigatória para todos os estudantes inscritos, independentemente do seu Estatuto.

Melhoria de classificação

Os estudantes aprovados em 2016/2017 que pretendam efetuar melhoria de classificação, devem realizar o  teste prático de programação e o exame.