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: 2015/2016 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1516/
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	55	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

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;

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	65,00
Teste	25,00
Trabalho laboratorial	10,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

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 numa componente da avaliação o estudante que tenha nota prática total inferior 2 valores (num máximo de 7).

 

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

• P: nota prática, valendo 35% 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 (2 valores). Nota mínima: P>=2 (escala de 0 a 7).


• T: nota teórica, valendo 65% da nota final, obtida através da média de dois testes escritos (TE1+TE2), com nota de 0 a 20 (TE1 e TE2 incidirão sobre conjuntos de matérias diferentes). Nota mínima em cada teste: 5 (de 0 a 20).


• R: na época de recurso será feito um único exame, com nota de 0 a 20, com a matéria correspondente aos dois testes escritos. Nota mínima: 5.

Classificação da época normal: C = T*0.65 + NP >= 9.5
Classificação da época de recurso: C = R*0.65 + NP >= 9.5

Provas e trabalhos especiais

No decorrer do semestre serão realizados dois testes escritos, dois testes práticos de programação e serão sugeridos exerícios práticos para resolver nas aulas e/ou em casa. As provas escritas (testes e exames) consistem em perguntas gerais e perguntas sobre problemas vistos nas aulas teóricas e práticas. Os testes de programação são obrigatórios e consistem na submissão no sistema Mooshak da resolução de problemas relacionados com os propostos nas aulas práticas.

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

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

Melhoria de classificação

Os estudantes aprovados em 2014/2015 ou em anos anteriores que pretendam efetuar melhoria de classificação poderão realizá-las nas condições de avaliação do ano passado, podendo efectuar melhoria apenas da componente teórica (via exame), apenas da componente prática (via teste prático como no ano passado) ou de ambas as componentes.