Algoritmos em Matemática Discreta
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Matemática |
Ocorrência: 2023/2024 - 1S
Ciclos de Estudo/Cursos
Língua de trabalho
Português - Suitable for English-speaking students
Objetivos
Ao completar esta unidade curricular, o estudante deve conhecer e saber aplicar os conceitos e resultados básicos estudados. Pretende-se paralelamente que a frequência desta unidade curricular contribua para o desenvolvimento de aptidões e competências no âmbito da matemática discreta e dos algoritmos.
Resultados de aprendizagem e competências
Pretende-se que no final deste curso o estudante seja capaz de:
• Completar e estruturar alguns conhecimentos básicos previamente adquiridos;
• Resolver problemas através de métodos elementares estruturados;
• Conhecer e mobilizar conceitos básicos e universais, que são a base de ferramentas de múltiplas ciências, num contexto próximos das aplicações;
• Utilizar (e conceber, quando possível) soluções algorítmicas de diversos problemas.
• Saber utilizar ferramentas computacionais para resolver problemas.
Modo de trabalho
Presencial
Programa
1. Revisão de alguns dos princípios básicos da combinatória: contagens, ordenação, listas, conjuntos, permutações.
2. Árvores de decisão e recursividade: definições básicas em árvores, ordem, rank, 'depth-first' e 'breadth first'; algoritmos recursivos, 'sorting',
3. Introdução à teoria de grafos: definiçoes e exemplos, isomorfismo, grafos aleatórios; grafos orientados e fluxos; circuitos Eulerianos e ciclos Hamiltonianos; árvores,
4. Introdução à análise de algoritmos como algoritmos de ordenação e de 'searching', algorithmos de Prim, de Kruskal, de Dijkstra, greedy, método de Ford-Fulkerson
Bibliografia Obrigatória
Dieter Jungnickel;
Graphs, networks and algorithms. ISBN: 978-3-540-72779-8 (Graphs, networks and algorithms)
Bender Edward A. 1942-;
Mathematics for algorithm and systems analysis
Bibliografia Complementar
Bondy J. A.;
Graph theory with applications. ISBN: 0-333-17791-6
Cormen Thomas H.;
Introduction to algorithms. ISBN: 9780262031417 hbk
Sedgewick Robert 1946-;
An introduction to the analysis of algorithms. ISBN: 978-0-201-40009-0
Métodos de ensino e atividades de aprendizagem
As horas de contacto estão distribuídas em aulas teóricas e teórico-práticas. Nas primeiras são apresentados os conteúdos do programa, recorrendo-se a exemplos para ilustrar os conceitos tratados e orientar os estudantes. Nas aulas teórico-práticas são resolvidos exercícios e problemas, previamente indicados. São disponibilizados materiais de apoio na página da disciplina.
Software
SageMath
Palavras Chave
Ciências Físicas > Matemática > Algoritmos
Ciências Físicas > Matemática > Análse combinatória
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Designação |
Peso (%) |
Teste |
100,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Estudo autónomo |
114,00 |
Frequência das aulas |
48,00 |
Total: |
162,00 |
Obtenção de frequência
Sem requisitos.
Fórmula de cálculo da classificação final
Nota final = max((T1+T2)/2,E)
onde T_i é a nota do i-esmio teste e E é a nota do exame na época normal
Os testes realizar-se-ão durante o tempo das aulas.
O exame de recurso terá duas partes para melhorar as notas dos testes ou seja os estudantes podem optar para manter a nota de um dos testes.
Observações
Artigo 13º do Regulamento Geral para Avaliação dos Discentes de Primeiros Ciclos, de Ciclos de Estudos Integrados de Mestrado e de Segundos Ciclos da U.Porto, aprovado em 19 de Maio de 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "A fraude cometida na realização de uma prova, em qualquer das suas modalidades, implica a anulação da mesma e a comunicação ao órgão estatutariamente competente para eventual processo disciplinar."
A qualquer aluno pode ser exigida a realização de uma prova oral para esclarecer dúvidas que tenham surgido relativamente às provas ou trabalhos de avaliação.