-
Apresentação
Apresentação
A UC de Introdução à Teoria dos Grafos e Redes pretende dar ferramentas aos alunos para utilização de grafos em diversos problemas, partindo dos conceitos básicos, passando por problemas clássicos, e finalmente uma breve introdução de redes complexas, e as suas aplicações em problemas de Ciência de Dados.
-
Disciplina do curso
Disciplina do curso
-
Grau | Semestres | ECTS
Grau | Semestres | ECTS
Licenciado | Semestral | 6
-
Ano | Natureza | Lingua
Ano | Natureza | Lingua
2 | Obrigatório | Português
-
Código
Código
ULHT6638-24499
-
Pré-requisitos e co-requisitos
Pré-requisitos e co-requisitos
Não aplicável
-
Estágio Profissional
Estágio Profissional
Não
-
Conteúdos Programáticos
Conteúdos Programáticos
CP1. Conceitos básicos (Definição, vértices, arestas, grafos orientados e não orientados, métricas, subgrafos, distância e conexidade, isomorfismos, invariantes e teoria espetral). CP2. Redes e fluxos (Fluxo máximo, fluxo de custo mínimo) CP3. Análise de redes (Representação de redes, visualização de redes, grau, medidas de distância e centralidade) CP4. Grafos aleatórios (Erdös-Rényi, Watts-Strogatz, Barabasi-Albert) CP5 Aplicações. em Data Science.
-
Objetivos
Objetivos
Os objetivos principais desta disciplina são: OA1. Identificar e utilizar conceitos e fundamentos sobre teoria de grafos; OA2. Introduzir o aluno aos problemas e teoremas básicos da teoria de grafos; OA3. Representar redes, determinar estatísticas de distâncias e coeficientes de clustering; OA4. Analisar a centralidade de uma rede; OA5. Caracterizar redes aleatórias: clássicas (Erdös-Rény), pequeno mundo (Watts-Strogatz) e livres de escala (Barabasi-Albert); OA6. Aplicar os conceitos abordados na unidade curricular à Ciência de Dados.
-
Metodologias de ensino
Metodologias de ensino
As aulas são divididas em aulas teóricas e práticas, sendo na sua maioria aulas expositivas presenciais. O aluno deverá dedicar 115h de trabalho assíncrono, e 52h em aulas presenciais. ME1. Aulas expositivas. ME2. Aulas práticas, com alguns momentos expositivos e outros com exercícios. ME3. Listas de exercícios teóricas e práticas. ME4. Desenvolvimento de projetos de maneira autónoma. ME5. Recomendação de material complementar.
-
Bibliografia principal
Bibliografia principal
L. Barabasi, M. Pósfai, Network Science, Cambridge University Press, 2016 B. Bollobás, Random Graphs, Cambridge University Press, 2001 D. M. Cardoso, J. Szymanski, M. Rostami, Matemática Discreta: combinatória, teoria dos grafos e algoritmos, Escolar Editora, 2008. P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos, 2004
-
Avaliação
Avaliação
A avaliação da cadeira está dividida em componentes prática e teórica, sendo composta por:
Componente prática:
- Assiduidade, participação e Laboratórios computacionais (20%).
- Projetos computacionais a desenvolver em grupo, com um prazo de duas semanas para desenvolvimento (80%).
Componente teórica:
- Assiduidade, participação e exercícios realizados em sala de aula (30%)
- 2 testes escritos, sendo o primeiro realizado numa aula teórica e o segundo na data final da frequência (70%).
Cada componente de avaliação tem peso de 50% na nota final. Sendo que o aluno deve atingir no mínimo 50% por componente, e 50% na média dos componentes.
-
Mobilidade
Mobilidade
Não
