• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Algorithmique 1 (INFO503_INFO)

  • Composante

    UFR Sciences et Montagne

Description

Introduction à la notion d’algorithme. Complexité des algorithmes. Ordre de grandeur asymptotique. Les arbres : structure et métrique. Arbre binaires de recherche et arbres équilibrés. Algorithmes de tri interne : tri par insertion, fusion, échanges et sélection. Tri de Shell, tri rapide et tri par tas. Tris linéaires : tri par dénombrement. Tris externes. Terminaison des algorithmes itératifs : méthode de Floyd, compteurs de Knuth. Terminaison des algorithmes récursifs.

TD et TP

Approfondissement des concepts vus en cours et ouverture vers d’autres types d’algorithmes. B-arbres, en particulier arbres 2-3-4. Arbres rouges et noirs. Codage d’un arbre binaire dans un tableau.  Variantes des algorithmes de tri vus en cours.  Jeu de la vie. Algorithmes d’approximation. Etude de la terminaison d’algorithmes.

Lire plus

Heures d'enseignement

  • CMCours Magistral6h
  • TDTravaux Dirigés9h
  • TPTravaux Pratiques12h