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

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~apt/aulas/DAA/2425
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	100	Plano estudos a partir do ano letivo 2021/22	2	-	6	48	162
L:F	3	Plano de Estudos Oficial	3	-	6	48	162
L:G	1	Plano estudos a partir do ano letivo 2017/18	2	-	6	48	162
			3
L:IACD	96	Plano Oficial a partir do ano letivo 2021/22	2	-	6	48	162
L:M	6	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

Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-36750-9 (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 4th ed, 2022)
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)
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	65,00
Teste	30,00
Trabalho laboratorial	5,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 2024/2025). O número máximo de faltas às aulas práticas é de três.

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

• NP (7 valores): obtida através de dois testes práticos (3 valores cada) e de exercícios (1 ponto), a realizar durante o semestre. Necessário NP >= 2.5 (na escala 0 a 7).


• Ex (13 valores): nota teórica, vale 65% da nota final.


• Nota Final (requer NP >= 2.5 em 7.0 e Ex >= 8.0 em 20) calculdada por  NF = Ex * 0.65 + NP >= 9.5


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

Provas e trabalhos especiais

Serão realizados dois testes de programação com classificação de  6 valores (em 20) na nota final (ou seja 30%). Os restantes exercícios de avaliação contínua, propostos para as aulas práticas (1 valor), também terão prazos para submissão. Os testes e exercícios terão avaliação automática pelo sistema Mooshak . Os problemas a resolver nos testes estarão relacionados com os propostos nas aulas práticas e para trabalho extra-aula.  A classificação nos testes práticos não pode ser melhorada. 

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 ou tiver nota inferior a 2.5 valores não terá aprovação em 2024/2025 (classificação final RFC).

Melhoria de classificação

Os estudantes aprovados em 2023/2024 que pretendam efetuar melhoria de classificação, devem realizar os testes práticos de programação - 6 valores -  a menos que tenham obtido 3 ou 4 valores em 4 nessa componente em 2023/2024  e realizar o exame (na época normal ou de recurso).  

Nota final = 0.7*Ex + TP

onde  TP  é  a nota obtida nos testes práticos.

Para os casos em que a nota prática em 2023/2024 foi de 3 ou 4 valores, TP será essa nota multiplicada por 1.5 (a menos que o estuda queira repetir os testes).

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.

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).