Saltar para:
Logótipo
Você está em: Início > CC2001
Mapa das Instalações
FC6 - Departamento de Ciência de Computadores FC5 - Edifício Central FC4 - Departamento de Biologia FC3 - Departamento de Física e Astronomia e Departamento GAOT FC2 - Departamento de Química e Bioquímica FC1 - Departamento de Matemática

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

Docência - Responsabilidades

Docente Responsabilidade
Ana Paula Nunes Gomes Tomás Regente

Docência - Horas

Teórica: 2,00
Práticas Laboratoriais: 2,00
Tipo Docente Turmas Horas
Teórica Totais 1 2,00
Ana Paula Nunes Gomes Tomás 2,00
Práticas Laboratoriais Totais 6 12,00
Ana Paula Nunes Gomes Tomás 2,00
Pedro Manuel Pinto Ribeiro 4,00
Hélder Filipe Pinto de Oliveira 6,00

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.

Recomendar Página Voltar ao Topo
Copyright 1996-2022 © Faculdade de Ciências da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z  I Livro de Visitas
Página gerada em: 2022-09-29 às 11:51:52 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais | Denúncias