Visão Geral e Dicas

Informações que irão auxiliá-lo a cursar bem a disciplina e a compreender sua importância para o curso.

Ementa

  • Definição formal de grafo e representações
  • Tipos de grafos

    • Simples
    • Direcionado
    • Completo
    • Conectado
    • Multigrafo
    • Bipartido
    • Caminho
    • Ciclo
    • Subgrafo
    • Ponderado
    • Gerador
    • Induzido
    • Árvore
    • Árvore geradora
    • Aleatório
  • Definição, propriedades, operações e algoritmos associados a conceitos de grafos

    • Grau e vizinhança
    • União e intersecção de grafos
    • Isomorfismo
    • Decomposição
    • Corte
    • Cobertura
    • Ponte
    • Passeio
    • Trilha
    • Circuito
    • Cintura
    • Clustering
    • Busca em árvores
    • Co-árvore
    • Matróides
    • Vértice de corte
    • Separações e blocos
    • Orientações
    • Conectividade
    • Contração
  • Tópicos Avançados

    • Circuitos de Euler e Hamiltoniano
    • Fluxos em redes
    • Grafos planares
    • Estabilidade e cliques
    • Coloração
    • Casamento
  • Noções básicas de complexidade de algoritmos e aproximações

Visão Geral

A disciplina é pautada em apresentar a teoria que embasa todo o estudo e as aplicações dos grafos na Ciência da Computação, porém não está focada apenas em aspectos teóricos. Também são apresentadas ferramentas para o desenvolvimento de aplicações, visualização e fixação dos conceitos ministrados. São estas:

  • yEd

    • Esta é a primeira ferramenta que o aluno tem contato, com ela é possível construir vários tipos de representações, dos tipos de grafos mais simples até um dos mais complexos principalmente em termos de visualização.
  • API JgraphT

    • É uma API desenvolvida em Java e que traz todos os conceitos estudados modelados e em sua grande maioria implementados e disponíveis para uso. Ao usá-la é possível enxergar resultados e aplicações práticas dos conceitos expostos em sala de aula
  • Neo4J e Cypher

    • O Neo4j é um sistema de gerenciamento e armazenamento de dados através de grafos (graph database).
    • Cypher é uma linguagem de consulta semelhante a SQL que se baseia no uso de padrões de nós e relacionamentos em um grafo.

Avaliação

Não há provas na disciplina, a avaliação é realizada através de:

  • MTI - Minitestes teóricos individuais (escritos).
  • MTG - Minitestes teóricos (escritos) em grupo de 3 a 4 integrantes.
  • EPG - Exercícios práticos em grupo, que consiste na resolução de problemas utilizando a teoria ministrada e a(s) ferramenta(s) disponibilizada(s). O EPG é dividido em duas etapas, a primeira etapa é realizada em sala, onde o planejamento da solução é feito, registrado e entregue à professora, a segunda etapa consiste na implementação da solução propriamente dita.

A nota é acumulativa e calculada da seguinte maneira:

  • Média: ((MTG1+MTI1+MTG2) + (MTI2+MTG3+MTG4) + (MTI3+MTG5+MTG6) + (EPG1+EPG2+EPG3+EPG))/4

Ao final da disciplina o aluno terá aprendido conceitos e algoritmos importantes que o tornarão capaz de desenvolver aplicações eficientes para resolução, representação e otimização de problemas utilizando grafos.

Dicas

  • Tente não deixar o conteúdo acumular, pois uma aula precisa e utiliza o conteúdo da aula anterior, o assunto é totalmente acumulativo e os conceitos aprendidos serão utilizados durante toda a disciplina.
  • Faça resumos, leitura ativa das notas de aula e slides e sempre procure se aprofundar nos conceitos.
  • Procure sempre tirar suas dúvidas, faça uso da monitoria. Converse com o(a) monitor(a) e/ou com a professora, não guarde suas dúvidas.
  • Pratique bastante! Ao praticar utilizando os exercícios conceituais e em paralelo utilizar as ferramentas propostas, você irá fixar muito mais cada conceito e saberá pô-los em prática.
  • Não deixe de fazer os quizzes, e tente fazê-los logo após as aulas, pois desse modo você consegue também perceber suas dificuldades e assim focar seus estudos nelas, além de estar praticando.
  • Sempre faça uso do repositório da disciplina, nele há exemplos de todos os conceitos vistos implementados utilizando a JgraphT. Se possível, depois de estudar a teoria, tente implementar estes exemplos também, pois assim você poderá comparar com as suas soluções, e assim você estará testando seus conhecimentos e adquirindo novos.
  • Faça uso da JgraphT, além de você está se aperfeiçoando também na linguagem Java, você aprenderá sobre classes e métodos que poderão facilitar a resolução de problemas comuns, além de tornar a sua aplicação eficiente e prática usando grafos.
  • Teoria dos grafos é uma disciplina muito importante, pode-se apontá-la como um dos pilares da Ciência da Computação, não negligencie! Todo o aprendizado adquirido, facilitará o seu entendimento em outras disciplinas e áreas da computação. Um profissional que consegue modelar problemas utilizando os conceitos e a estrutura de grafos, é muito valorizado no mercado, além de desenvolver ótimas soluções para problemas, pois seu pensamento abstrato e o seu conhecimento sobre padrões e ferramentas são eficientes, e tudo isso pode ser concretizado com a ajuda dos conceitos da teoria dos grafos.
  • Recomendo que você escute este podcast sobre a A beleza matemática dos Grafos, vai lhe dar uma ótima dimensão sobre aplicações da teoria dos grafos.
Edite esta página