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: 2021/2022 - 2S

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

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 "Programação Imperativa" 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 directas e indirectas;

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. Questionários extra-aulas para consolidação da matéria dada.

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	70,00
Teste	25,00
Trabalho prático ou de projeto	5,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas	56,00
Estudo autónomo	66,00
Trabalho laboratorial	40,00
Total:	162,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ários não contará para avaliação, mas para obter frequência um estudante terá de ter respondido a pelo menos 50% dos questionários.

Perde a frequência por não obtenção de nota mínima num componente da avaliação o estudante que tenha nota prática total inferior ou igual a 1.5 valores (25% de um máximo de 6).

 

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

• P: nota prática, valendo 30% da nota final, obtida através de 3 componentes: 2 testes práticos de programação (2.5 valores cada) e uma componente contínua de resolução de exercícios ao longo do semestre (1 valor). Nota mínima: P>=1.5 (escala de 0 a 6).


• EN: nota do exame de época normal, valendo 70% da nota final, obtida através de um exame escrito (presencial) com nota de 0 a 20.


• ER: na época de recurso será feito feito um único exame (presencial), com nota de 0 a 20, não sendo possível repetir a componente prática.

Classificação da época normal: C = EN*0.7 + P >= 9.5
Classificação da época de recurso: C = ER*0.7 + P >= 9.5

Provas e trabalhos especiais

No decorrer do semestre serão realizados dois testes práticos de programação e serão sugeridos exerícios práticos para resolver nas aulas e/ou em casa.

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

A componente prática é obrigatória para todos os estudantes inscritos.

Melhoria de classificação

Observações

Recomendado ter conhecimentos básicos de programação ministrados nas u.c. de Programação Imperativa (CC2003) e Estruturas de Dados (CC1007), ou em u.c. equivalentes.