AccueilLicence généraleInformatiqueEnseignementsStructures discrètes

Licence InformatiqueUE Structures discrètes

Contenu

Apprendre à raisonner sur les structures algorithmiques de bases, à les utiliser et à les programmer : tableaux, structures séquentielles (listes, mots, files), arbres et graphes.

  • Outils d'analyse des algorithmes (20%) : analyse d'algorithmes et complexité asymptotique, preuve de terminaison, preuve de correction, invariants, préconditions et postconditions
  • Vecteurs et matrices (15%) : recherche dichotomique, produits scalaire et matriciel, tableaux
  • Listes et séquences finies (25%) : monoïde libre, sous-séquences, facteurs, concaténation, listes chainées, doublement chainées, implémentation par tableau, structures abstraites de listes, files, piles
  • Arbres (25%) : induction, dépendances entre arité, nombre de nœuds et hauteur, parcours d'arbres
  • Graphes (15%) : lemme des poignées de mains, théorème de caractérisation des arbres, représentation matricielle, fermeture transitive

Compétences visées

  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation (25%)
  • Rédiger de manière synthétique et rigoureuse des preuves (20%)
  • Évaluer la complexité et la correction d’une solution algorithmique (15%)
  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement (15%)
  • Mettre en œuvre des algorithmes et des structures de données (25%)

Langue utilisée

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

Pré-requis recommandés

  • Langage mathématique
  • Programmation 1

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 24 heures
  • Travaux pratiques : 18 heures

Les formations qui utilisent cet enseignement