Cours : Algorithmique intermédiaire : analyse d'algorithmes, structures de données

Aperçu des sections

Tout replier Tout déplier
- Ressources basées sur :
  
  Algorithmique 1
  
  Licence 1 Informatique - Université Clermont Auvergne
  
  Contact : Aurélie Lagoutte
- Annonces Forum
- Vous devez être authentifié et "inscrit" au cours (logo paramètres, en haut à droite, puis "M'inscrire / Enrol me" puis confirmation) pour avoir accès aux quizz.
Accueil
Conseils pour bien utiliser les activités disponibles dans ce cours

Pré-requis, Objectifs, Plan du cours

Comment bien utiliser les ressources de ce cours ?

Contexte académique
Cours et exercices
- Playlist Cours Magistraux ALGO1 sur Youtube URL
- Chapitre 1 : Rappels d'algorithmique en pseudo-code
  
  Objectifs:
  
  Comprendre l'intérêt du pseudo-code par rapport à un langage de programmation
  
  Connaître la syntaxe de pseudo-code qui sera utilisé dans ce cours
  
  Etre capable de refaire en pseudo-code des algorithmes vus dans les UE précédentes
- Slides Chapitre 1: notations de pseudo-code Fichier
- Video cours ALGO1: Introduction, contexte URL
- Video cours ALGO1: chapitre 1 - partie 1 : Variables, Types, Opérations de base URL
- Video cours ALGO1: chapitre 1 - partie 2 : Si, Pour, Tant Que URL
- Video cours ALGO1: chapitre 1 - partie 3: Fonctions URL
- Video cours ALGO1: chapitre 1 - partie 4: tableaux URL
- Quizz Algo : les incontournables sur les tableaux Test
  
  Recevoir une note
- Quizz Algo : révisions de pseudo-code Test
  
  Recevoir une note
- Chapitre 2 : Analyse d'algorithmes: complexité temporelle
  
  Objectifs:
  
  Comprendre que l'exécution d'une opération n'est pas instantanée
  
  Bien faire la différence entre "une ligne de code" et "une opération" car une ligne de code peut provoquer de nombreuses opérations.
  
  Savoir calculer la complexité temporelle d'un algorithme lorsque le paramètre n est précisé, ainsi que les opérations à compter.
  
  Savoir dire, entre deux algorithmes ayant des ordres de grandeur différents, lequel est le plus efficace. En particulier, bien comprendre la différence entre complexité d'ordre constant (le nombre d'opérations ne dépend pas de la taille de l'entrée) et d'ordre linéaire (le nombre d'opérations est proportionnel à la taille de l'entrée).
  
  Savoir estimer le temps d'exécution d'un algorithme à partir du nombre d'opérations par seconde et de la complexité de l'algorithme.
- Slides Chapitre 2: complexité temporelle Fichier
- Video cours ALGO1: chapitre 2 - partie 1 : intuition sur la rapidité d'un algo URL
- Video cours ALGO1: chapitre 2 - partie 2 : Choix du paramètre et des opérations URL
- Video cours ALGO1: chapitre 2 - partie 3 : Ordre de grandeur et choix du Pire cas URL
- Video cours ALGO1: chapitre 2 - partie 4 : plein d'exemples ! URL
- Quizz Algo : un calcul détaillé de complexité Test
  
  Recevoir une note
- Quizz Algo : complexité Test
  
  Recevoir une note
- Chapitre 3 : Analyse d'algorithmes: preuves de correction et de terminaison
  
  Objectifs:
  
  Savoir prouver qu'un algo est correct par rapport aux spécifications demandées grâce à un invariant de boucle, dans des cas simples
  
  Savoir prouver qu'un algo avec une boucle Tant Que termine.
- Slides Chapitre 3: preuves d'algorithmes (invariants de boucle, terminaison) Fichier
- Video cours ALGO1: chapitre 3 - partie 1 : Pourquoi? + notre premier invariant URL
- Video cours ALGO1: chapitre 3 - partie 2 : Preuves de correction par invariant de boucle URL
- Video cours ALGO1: chapitre 3 - partie 3 : Preuves de terminaison URL
- Quizz : Preuve de correction par invariant de boucle Test
  
  Recevoir une note
- A venir : des explications pour bien réussir le quizz sur les invariants
- Fiche TD01: analyse d'algo (complexité temporelle & preuves) Fichier
- Catalogue d'algos (annexe fiche TD01) Fichier
- Fiche TD01 commune aux Chap. 1, 2, 3 - corrigé Fichier
- Chapitre 4 : Récursivité
  
  Objectifs:
  
  Savoir écrire et exécuter un algorithme récursif
  
  Savoir calculer la complexité temporelle d'un algorithme récursif grâce à une suite définie par récurrence
  
  Savoir prouver le terminaison d'un algorithme récursif
  
  Savoir écrire et exécuter un algorithme de recherche dichotomique dans un tableau trié
  
  Connaître la complexité temporelle de recherche dichotomique dans un tableau trié: O(log n)
- Slide chapitre 4: récursivité Fichier
- Video cours ALGO1: chapitre 4 - partie 1 : Principe et exemples URL
- Video cours ALGO1: chapitre 4 - partie 2 : Compter la complexité, et introduction à Diviser pour Régner URL
- Video cours ALGO1: chapitre 4 - partie 3 : Recherche dichotomique URL
- Se rafraîchir la mémoire sur les suites arithmétiques et géométriques URL
- Fiche TD02: récursivité Fichier
- Corrigé fiche TD02 récursivité Fichier
- Video expliquant l'algo. récursif des tours de Hanoï (Fiche TD02, exo 2) URL
- Quizz : algorithmes récursifs Test
  
  Recevoir une note
- Chapitre 5 : Structure de données et Types de Données Abstraits, en particulier les tableaux partiellement remplis et les listes chaînées
  
  Objectifs:
  
  Comprendre qu'un Type de Données Abstrait est une façon de stocker des données en respectant certaines spécifications
  
  Savoir quel Type de Données Abstrait choisir pour stocker des données en fonction du problème (possible ou impossible? Coûteux ou efficace?)
  
  Maîtriser le Type de Données Abstrait Tableau Partiellement Rempli (Tableau PR):
  
  Connaître les spécifications du type Tableau Partiellement Rempli (Tableau PR)
  
  Savoir exécuter des algorithmes utilisant un tableau PR
  
  Savoir écrire des algorithmes utilisant un tableau PR, et calculer leur complexité en comptant les opérations élémentaires de tableau PR
  
  Savoir ré-écrire et ré-utiliser les algorithmes définis en cours sur ce type: ajouteDebut, ajouteFin, supprimeOrdre, supprimeDesorde, RecherchePos
  
  Maîtriser le Type de Données Abstrait Liste Chaînée (aussi appelé Liste simplement chaînée):
  
  Connaître les spécifications du type Liste Chaînée
  
  Savoir exécuter des algorithmes utilisant une Liste Chaînée
  
  Savoir écrire des algorithmes utilisant une Liste Chaînée et calculer leur complexité en comptant les opérations élémentaires de Liste Chaînée
  
  Savoir ré-écrire et ré-utiliser les algorithmes définis en cours sur ce type: tailleListe, valeurMaillon, valeurPremierMaillon, ajouteDebut, ajouteFin, supprime, RechercheAdr
- Slides Chapitre 5 : Types de Données Abstraits, tableau partiellement rempli, liste (simplement) chaînée Fichier
- Video cours ALGO1: chapitre 5 - partie 1 : Introduction aux Types de Données Abstraits URL
- Video cours ALGO1: chapitre 5 - partie 2 : Tableau Partiellement Rempli URL
- Video cours ALGO1: chapitre 5 - partie 3: Liste chaînée : définition URL
- Video cours ALGO1: chapitre 5 - partie 4: Liste chaînée : premières fonctions URL
- Video cours ALGO1: chapitre 5 - partie 5: Liste chaînée : comparaison avec les tableaux PR URL
- Video cours ALGO1: chapitre 5 - partie 6: Conclusion - Utilisation d'une Liste chaînée URL
- Fiche TD03: listes chainées et tableaux partiellement remplis (PR) Fichier
- Fiche TD03 corrige Fichier
- Animation (corrigé) Exercice 1 TD03 Fichier
  
  A télécharger et à regarder comme une animation, page après page, avec un clic = page suivante.
- Quizz : liste chaînée - algorithmes impératifs Test
  
  Recevoir une note
- Quizz : liste chaînée - algorithmes récursifs Test
  
  Recevoir une note
- Vidéo corrigé - Renverser liste récursif & impératif URL
- Slides utilisées dans la vidéo - corrigé Renverser Liste Fichier
- Quizz : choisir la bonne structure de données Test
  
  Recevoir une note
- Facultatif: pour ceux qui souhaitent implémenter (en C ou en Python) les fonctions vues sur les listes chaînées, vous trouverez ci-dessous un fichier définissant les structures/classes nécessaires pour manipuler des listes chaînées dans le langage choisi. Les premières fonctions sont déjà implémentées, à titre d'exemple, les autres sont à compléter par vos soins. Vous trouverez également quelques exemples d'utilisation des fonctions implémentées dans le programme principal.
- Implémentation des listes chaînées en C Fichier
- Implémentation des listes chaînées en Python Fichier
- Evolution envisagée : ajout d'exercices d'implémentation en C/Python évalués automatiquement, avec vérification de la complexité attendue.
- Chapitre 6 : Variantes des listes chaînées (seulement pour étudiants en Majeure Info)
  
  Objectifs:
  
  Maîtriser le Type de Données Abstrait Liste Doublement Chaînée (aussi appelé Liste DC):
  
  Connaître les spécifications du type Liste DC
  
  Savoir exécuter des algorithmes utilisant une DC
  
  Savoir écrire des algorithmes utilisant une Liste DC et calculer leur complexité en comptant les opérations élémentaires de Liste DC
  
  Savoir ré-écrire et ré-utiliser les algorithmes définis en cours sur ce type: tailleListe, valeurMaillon, valeurTete, ajouteDebut, ajouteFin, supprime, RechercheAdr
  
  Maîtriser le Type de Données Abstrait Liste Doublement Chaînée Circulaire (aussi appelé Liste DCC), mentionné en cours et vu en TD :
  
  Connaître les spécifications du type Liste DCC
  
  Savoir exécuter des algorithmes utilisant une DCC
  
  Savoir écrire des algorithmes utilisant une Liste DCC et calculer leur complexité en comptant les opérations élémentaires de Liste DCC
  
  Savoir ré-écrire et ré-utiliser les algorithmes définis en TD sur ce type: tailleListe, valeurMaillon, valeurTete, ajouteDebut, ajouteFin, supprime, RechercheAdr
- Slides Chapitre 6 : Listes doublement chaînées (DC) et doublement chaînées circulaires (DCC) Fichier
- Video cours ALGO1: chapitre 6 - partie 1 : Définition d'une liste doublement chaînée URL
- Video cours ALGO1: chapitre 6 - partie 2 : fonctions sur une liste doublement chaînée URL
- Video cours ALGO1: chapitre 6 - partie 3 : fonctions sur une liste doublement chaînée (suite) URL
- Video cours ALGO1: chapitre 6 - partie 4 : conclusion & intro aux listes doublement chaînées circulaires URL
- Fiche TD04: listes doublement chaînée (liste DC) et doublement chaînées circulaires (DCC) Fichier
- Fiche TD04 corrigé Fichier
- Quizz : liste doublement chaînée - entraînement Test
  
  Recevoir une note
- Quizz : découvrir les listes doublement chaînées circulaires Test
  
  Recevoir une note
- Quizz : listes doublement chaînées circulaires - entraînement Test
  
  Recevoir une note
- Chapitre 7 : pile, file
  
  Objectifs:
  
  Savoir utiliser les opérations élémentaires de pile, de file
  
  Savoir écrire des algorithmes manipulant des piles ou des files, (et ré-écrire ceux vus dans le cours)
  
  Savoir compter la complexité d'un algorithme utilisant une pile, une file
  
  Savoir choisir le meilleur type de données en fonction du problème à résoudre (si plusieurs choix sont possibles, choisir le plus économique en terme de complexité)
- Slides Chapitre 7: pile, file Fichier
- Video cours ALGO1: chapitre 7 - partie 1 : Point de vue implementation vs. Point de vue utilisateur URL
- Video cours ALGO1: chapitre 7 - partie 2 : Pile URL
- Video cours ALGO1: chapitre 7 - partie 3 : File URL
- Fiche TD05: pile, file Fichier
- Corrigé Fiche TD05: pile, file Fichier
- Quizz : pile, file Test
  
  Recevoir une note
- Implémenter une pile avec une liste simplement chaînée Test
  
  Recevoir une note
- Implémenter une file avec une liste ou une variante de liste Test
  
  Recevoir une note
- Chapitre 8 : arbre binaire
  
  Objectifs:
  
  Connaitre la vocabulaire relatifs aux arbres
  
  Savoir écrire et executer au pas-à-pas des algorithmes simples sur les arbres bianires
  
  Savoir ré-écrire les algorithmes de parcours d'arbres (en largeur et en profondeur)
  
  Savoir exécuter un parcours en largeur et un parcours en profondeur sur un arbre donné en exemple (= donner l'ordre dans lequel les noeuds sont visités)
  
  Savoir détecter si un abre binaire vérifie les propriétés d'Arbre Binaire de Recherche (ABR)
  
  Savoir exécuter et ré-écrire les algorithmes de recherche et d'insertion simple d'une valeur dans un ABR
  
  Savoir executer et ré-écrire les algorithmes de parcours recursifs du cours: prefixe, infixe, suffixe
- Slides Chapitre 8: arbres Fichier
- Video cours ALGO1: chapitre 8 - partie 1 : Vocabulaire des arbres URL
- Video cours ALGO1: chapitre 8 - partie 2 : fonctions sur les arbres URL
- Video cours ALGO1: chapitre 8 - partie 3: parcours en largeur et en profondeur URL
- Video cours ALGO1: chapitre 8 - partie 4 : Arbres Binaires de Recherche (ABR) URL
- Video cours ALGO1: chapitre 8 - partie 5 : parcours infixe, préfixe, suffixe URL
- Quizz : arbres Test
  
  Recevoir une note
- Fiche TD06: arbres et tris Fichier
- Corrigé fiche TD06: arbres et tris Fichier
- Chapitre 9 : tris
  
  pour chacun des 4 tris présentés (tri par insertion, tri par sélection, tri rapide, tri fusion), il faut savoir:
  
  expliquer le fonctionnement de l'algorithme
  
  savoir exécuter l'algorithme pas-à-pas sur un exemple
  
  réécrire l'algorithme, y compris les fonctions auxiliaires utilisées
  
  complexité: savoir la recalculer (pour tri par insertion et tri par sélection) ou la connaître "par coeur" (pour tri rapide et tri fusion) (les trois premiers sont en O(n^2) et le tri fusion est en O(n. log n)
  
  Remarque: un soin tout particulier doit être apporté à la compréhension du tri par insertion et du tri par sélection
- Slides chapitre 9 (tris) Fichier
- Animation tri fusion Fichier
- Video cours ALGO1: chapitre 9 - partie 1 : tri par sélection URL
- Video cours ALGO1: chapitre 9 - partie 2 : tri par insertion URL
- Video cours ALGO1: chapitre 9 - partie 3 : tri rapide URL
- Video cours ALGO1: chapitre 9 - partie 3 : tri fusion URL
- TD: voir le dernier exercice de la fiche de TD06: arbres et tris
- Quizz : tris Test
  
  Recevoir une note Obtenir une note minimale de réussite
- Révisions
- Slides de révisions Fichier
Contributions, discussions enseignants
- Idées et contributions pour ce cours ouvert Forum

Dimanche	Lundi	Mardi	Mercredi	Jeudi	Vendredi	Samedi
Aucun événement, dimanche 1 juin Aucun événement, dimanche 1 juin	Aucun événement, lundi 2 juin Aucun événement, lundi 2 juin	Aucun événement, mardi 3 juin Aucun événement, mardi 3 juin	Aucun événement, mercredi 4 juin Aucun événement, mercredi 4 juin	Aucun événement, jeudi 5 juin Aucun événement, jeudi 5 juin	Aucun événement, vendredi 6 juin Aucun événement, vendredi 6 juin	Aucun événement, samedi 7 juin Aucun événement, samedi 7 juin
Aucun événement, dimanche 8 juin Aucun événement, dimanche 8 juin	Aucun événement, lundi 9 juin Aucun événement, lundi 9 juin	Aucun événement, mardi 10 juin Aucun événement, mardi 10 juin	Aucun événement, mercredi 11 juin Aucun événement, mercredi 11 juin	Aucun événement, jeudi 12 juin Aucun événement, jeudi 12 juin	Aucun événement, vendredi 13 juin Aucun événement, vendredi 13 juin	Aucun événement, samedi 14 juin Aucun événement, samedi 14 juin
Aucun événement, dimanche 15 juin Aucun événement, dimanche 15 juin	Aucun événement, lundi 16 juin Aucun événement, lundi 16 juin	Aucun événement, mardi 17 juin Aucun événement, mardi 17 juin	Aucun événement, mercredi 18 juin Aucun événement, mercredi 18 juin	Aucun événement, jeudi 19 juin Aucun événement, jeudi 19 juin	Aucun événement, vendredi 20 juin Aucun événement, vendredi 20 juin	Aucun événement, samedi 21 juin Aucun événement, samedi 21 juin
Aucun événement, dimanche 22 juin Aucun événement, dimanche 22 juin	Aucun événement, lundi 23 juin Aucun événement, lundi 23 juin	Aucun événement, mardi 24 juin Aucun événement, mardi 24 juin	Aucun événement, mercredi 25 juin Aucun événement, mercredi 25 juin	Aucun événement, jeudi 26 juin Aucun événement, jeudi 26 juin	Aucun événement, vendredi 27 juin Aucun événement, vendredi 27 juin	Aucun événement, samedi 28 juin Aucun événement, samedi 28 juin
Aucun événement, dimanche 29 juin Aucun événement, dimanche 29 juin	Aucun événement, lundi 30 juin Aucun événement, lundi 30 juin

juin 2025

Aperçu des sections

Algorithmique 1

Licence 1 Informatique - Université Clermont Auvergne

Accueil

Cours et exercices

Contributions, discussions enseignants