AccueilLicence généraleInformatiqueEnseignementsGraphes, arbres et complexité

Licence InformatiqueUE Graphes, arbres et complexité

Contenu

Objectifs de l'enseignement :

L’objectif de ce module est d’harmoniser les connaissances dans des domaines théoriques de l’informatique pour les étudiants venant de filières où ces éléments sont insuffisamment traités. Il s’agit ici de renforcer les étudiants dans les domaines de l’informatique théorique en leur présentant différents modèles mathématiques (les automates, les graphes et les arbres) qui formalisent des méthodes de calcul liées à la théorie des langages ou à celle de la complexité des algorithmes. Les étudiants doivent acquérir les connaissances leur permettant de construire des algorithmes efficaces.

Compétences visées

A l’issue du module l’étudiant doit être capable de /d’ :

  • évaluer la complexité d'un algorithme
  • expliquer la notion de complexité asymptotique, de borne supérieure et inférieure du temps d'exécution d'un algorithme
  • expliquer les notions fondamentales sur les graphes et leur représentation sur ordinateur
  • utiliser les algorithmes de parcours d'un graphe et les appliquer pour résoudre des problèmes élémentaires sur les graphes
  • expliquer les notions fondamentales sur les arbres et leur représentation sur ordinateur
  • utiliser les algorithmes de construction et de parcours d'un arbre et les appliquer pour résoudre des problèmes de gestion de données avec les arbres

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Volume des enseignements

  • Cours magistraux : 15 heures
  • Travaux dirigés : 15 heures

Les formations qui utilisent cet enseignement