Théorie des graphes avancée

Informations

Langue d'enseignement : Anglais
Crédits ECTS: 3

Programme

  • Heures d'enseignement dispensées à l'étudiant : 24 heures
  • Temps de travail personnel : 51 heures

Objectifs et compétences

Objectifs :
La théorie des graphes est un modèle très général qui permet de représenter des problèmatiques très variées, que ce soit dans les réseaux (de toute nature) mais aussi pour des structures hierarchisées comme les bases de données. La culture générale des problématiques de graphe que nous proposons dans ce cours ainsi que la connaissance des outils efficaces pour ces problématiques sont des atouts pour reconnaître et traiter les problèmes qu'elles modélisent.

Cet enseignement présente des notions avancées de théorie des graphes et familiarise l’étudiant avec certaines techniques de preuve classiques de graphes, liées notamment à la coloration et la domination. Quelques problèmes et conjectures classiques sont abordés.

---

Graph theory is a very general model that can represent various problems, from networks (of any kind) to hierarchical structures such as data bases. The general knowledge of graph theory we provide in this course is useful for recognising and dealing with the problems it modelizes.

This teaching presents advanced notions of graph theory and faces the student with some classical proof techniques on graphs, illustrated on graph coloring and domination. Some classical problems and conjecture are also presented.

Compétences :
  • Être initié au processus de production, de diffusion et de valorisation des connaissances.
  • Etre capable de communiquer des résultats à l'écrit et à l'oral en français et en anglais
  • Assurer une veille scientifique et professionnelle
  • Etre capable de communiquer des résultats à l'écrit et à l'oral
  • Etre capable d’adapter les modèles théoriques à un objet de recherche ou aux réalités de terrain.

  • Comprendre et mettre en oeuvre l'intérêt et les principes de la démarche de recherche fondamentale et/ou appliquée
  • Savoir construire et rédiger un état de l'art
  • Rédiger des documents de travail ( rapports, notes de synthèse...) adaptés aux personnes et situations rencontrées et appropriés aux organisations et structures concernées
  • Être autonome dans l’activité d’écriture et montrer à cette occasion sa capacité à communiquer sa pensée, à raisonner et à organiser ses connaissances.
  • Construire et développer une argumentation.

  • Connaître et mettre en application les principaux modèles mathématiques intervenant dans les différentes disciplines connexes du domaine Sciences et Technologies mais aussi des autres domaines
  • Construire et rédiger une démonstration mathématique synthétique et rigoureuse.
  • Être capable de traduire un problème simple en langage mathématique.
  • Maîtriser les bases de la logique et organiser un raisonnement mathématique.
  • Identifier les limites de l'informatique en termes de calculabilité et de complexité
  • Modéliser une situation concrète en un énoncé formel au moyen d'outils (e.g., automates, langages, grammaires, graphes)
  • Concevoir des algorithmes avancés dans son domaine de spécialisation, et savoir les programmer
  • Comprendre et traduire sous forme algorithmique la spécification mathématique d'une méthode de son domaine de spécialisation
  • Implémenter et/ou comparer les méthodes de l'état de l'art dans son domaine de spécialisation
  • Comprendre une preuve de correction d'algorithme (e.g., variants/invariants, induction, convergence)
  • Ecrire une preuve de correction d'algorithme

Organisation pédagogique

- Non défini -

Contrôle des connaissances

Session 1:

Travaux personnels à distance (contrôle continu, coefficient 1/2)

Épreuve écrite de synthèse (durée 1h30, coefficient 1/2)

Deuxième session: épreuve écrite (1h30) ou orale selon effectif, coeff. 1/2.

CC, report de la note de session 1, coeff. 1/2

Note finale session 2: max(NoteEx2, 0.5*NoteEx2 + 0.5*NoteCC)

Lectures recommandées

- Non défini -

Responsable de l'unité d'enseignement

Paul Dorbec

Enseignants

- Non défini -