Saltar para:
Logótipo
Você está em: Início > M2007
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

Algoritmos em Matemática Discreta

Código: M2007     Sigla: M2007     Nível: 200

Áreas Científicas
Classificação Área Científica
OFICIAL Matemática

Ocorrência: 2018/2019 - 1S Ícone do Moodle

Ativa? Sim
Unidade Responsável: Departamento de Matemática
Curso/CE Responsável: Licenciatura em Matemática

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 3 Plano de estudos a partir de 2014 2 - 6 56 162
3
L:F 0 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 52 Plano de Estudos Oficial 2 - 6 56 162
L:Q 0 Plano estudos a partir do ano letivo 2016/17 3 - 6 56 162

Docência - Horas

Teórica: 2,00
Teorico-Prática: 2,00
Tipo Docente Turmas Horas
Teórica Totais 1 2,00
Samuel António de Sousa Dias Lopes 2,00
Teorico-Prática Totais 1 2,00
Samuel António de Sousa Dias Lopes 2,00

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.

Modo de trabalho

Presencial

Programa





1. Revisão de alguns dos princípios básicos da combinatória: contagens, ordenação, listas, conjuntos e multiconjuntos, contagem de funções de vários tipos (injetivas, sobrejetivas, crescentes, decrescentes), partições, etc.; combinatória das 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', códigos de Gray; relações de recorrência, equação característica, sucessões de Fibonacci e Catalan, desarranjos.

3. Introdução à teoria de grafos: definiçoes e exemplos, isomorfismo, grafos aleatórios; grafos orientados e fluxos; circuitos Eulerianos e ciclos Hamiltonianos; árvores, algoritmos de Prim, Kruskal, 'depth-first' e 'breadth first'.

4. Introdução à análise de algoritmos. [A aboragem deste tópico depende do tempo disponível.]





Bibliografia Obrigatória

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. Para além das aulas, há períodos de atendimento semanais onde os estudantes têm oportunidade de esclarecer dúvidas.


 





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 (%)
Exame 100,00
Total: 100,00

Componentes de Ocupação

Designação Tempo (Horas)
Estudo autónomo 106,00
Frequência das aulas 56,00
Total: 162,00

Obtenção de frequência

Sem restrições.

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

Serão efetuados testes opcionais ao longo do semestre (entre 2 e 4 testes, no total), cuja soma das cotações é igual a 15 valores. A classificação correspondente a cada um dos testes pode ser usada nos exames das épocas normal e de recurso, nos termos descritos a seguir.

O exame final (época normal e época de recurso) consiste de N+1 partes, onde N é o número de testes realizados durante o semestre, correspondendo cada uma destas partes a um teste. A classificação em qualquer destas partes é igual ao máximo das classificações obtidas no teste correspondente e nessa parte do exame. No exame da época de recurso, contará para esse máximo também a classificação obtida na parte correspondente do exame da época normal. O conjunto destas N partes tem a cotação de 15 valores. A restante parte tem a cotação de 5 valores e não corresponde a nenhum dos testes.

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

Qualquer tipo de avaliação especial poderá revestir uma das seguintes formas: exclusivamente uma prova oral; uma prova oral e uma prova escrita, ambas com caráter eliminatório; somente uma prova escrita. A opção por uma das alternativas compete exclusivamente aos docentes responsáveis pela unidade curricular.

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.

Júri da disciplina:
Samuel António de Sousa Dias Lopes
Pedro Ventura Alves da Silva
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-10-06 às 12:15:47 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais | Denúncias