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: 2023/2024 - 2S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/2324
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	48	162
L:CC	70	Plano estudos a partir do ano letivo 2021/22	2	-	6	48	162
L:F	0	Plano de Estudos Oficial	3	-	6	48	162
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	6	48	162
			3
L:IACD	57	Plano Oficial a partir do ano letivo 2021/22	2	-	6	48	162
L:M	2	Plano de Estudos Oficial	2	-	6	48	162
			3
L:MA	0	Plano de Estudos Oficial	3	-	6	48	162
L:Q	0	Plano estudos a partir do ano letivo 2016/17	3	-	6	48	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. O estudante deve preferencialmente ter já aprovação à unidade curricular de  "Programação Imperativa" (CC1003) e a  "Estruturas de Dados" (CC1007), ou a unidades curriculares equivalentes.  

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), divisão-e-conquista, programação dinâmica;

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

Árvores binárias de pesquisa balanceadas: á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.

Problemas computacionalmente difíceis. Breve introdução às classes de complexidade de problemas P, NP, NP-hard e NP-Completos. Introdução aos algoritmos de aproximação e paramétricos.

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)
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/)
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8 (S. Skiena. The Algorithm Design Manual, 2nd Edition, 2008)
Mark de Berg; Computational geometry. ISBN: 978-3-540-65620-3 hbk
S. Halim and F. Halim; Competitive Programming, 1st Edition, 2011 (Livro disponível grátis em https://sites.google.com/site/stevenhalim/)
Michael R. Garey; Computers and intractability. ISBN: 0-7167-1045-5

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

Linguagens de programação/Programming Languages: C, C++ or Java
Servidor Mooshak para CC2001 (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
Trabalho laboratorial	20,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	72,00
Frequência das aulas	48,00
Trabalho laboratorial	42,00
Total:	162,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 que implica não ter possibilidade de obter aprovação à UC em 2023/2024). O número máximo de faltas às aulas práticas é de três.

 

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

• NP: nota prática, vale 20% da nota final, obtida através de dois testes práticos, a realizar durante o semestre. Se não for possível realizar dois testes práticos, haverá apenas  um teste final. 


• NT: nota teórica, vale 80% da nota final. Se o calendário escolar de 2023/2024, 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.  NT = max((TE1+TE2)/2, TE2, FinalExam).


• A classificação final é calculada por  NP + 0.8*NT    (esta classificação deverá ser >= 9.5). Para dispensa de exame final, a classificação dos testes escritos terá de satisfazer max((TE1+TE2)/2, TE2) >= 8.  Serão aprovados à UC também os estudantes com classificação NT >= 10.0. 


• Classificação da época de recurso: C = Exame*0.8 + NP >= 9.5, devendo a classificação no exame ser >= 8. Serão aprovados à UC também os estudantes com Exame >= 10.0. 


• Casos de fraude académica: será aplicado o regulamento em vigor 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ão realizados um ou dois testes de programação com classificação de 4 valores (em 20) na nota final (ou seja 20%). Os testes terão avaliação automática pelo sistema Mooshak . Os problemas a resolver estarão relacionados com os propostos nas aulas práticas e para trabalho extra-aula.

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

A componente prática é obrigatória para todos os estudantes inscritos, independentemente do seu Estatuto. Se não a realizar, terá zero valores nessa componente.

Melhoria de classificação

Os estudantes aprovados em 2022/2023 que pretendam efetuar melhoria de classificação, devem realizar os testes práticos de programação e o exame.

Observações

O estudante deve ter já aprovação à unidade curricular de  "Programação Imperativa" (CC1003) e a  "Estruturas de Dados" (CC1007), ou a unidades curriculares equivalentes.

A não aprovação a CC1003 (ou UC similar) não impede a inscrição a CC2001, mas não é de todo aconselhável.

Se o estudante não concluiu CC1007 (ou UC similar), poderá necessitar de um esforço suplementar para obter aprovação a CC2001.

Recomenda-se vivamente o acompanhamento das matérias desde o início do semestre, através do estudo, da participação ativa nas aulas teóricas e práticas, e da resolução dos problemas propostos (para avaliação pelo Mooshak).