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

Тематический план

• Свернуть всё Развернуть всё
  • Ressources basées sur : Algorithmique 1 Licence 1 Informatique - Université Clermont Auvergne Contact : Aurélie Lagoutte

  • 

    Annonces Форум
  • 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

  1. Pré-requis, Objectifs, Plan du cours
  2. Comment bien utiliser les ressources de ce cours ?
  3. Contexte académique

• Cours et exercices
  • 

    Playlist Cours Magistraux ALGO1 sur Youtube Гиперссылка
  • ---

    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 Файл
  • 

    Video cours ALGO1: Introduction, contexte Гиперссылка
  • 

    Video cours ALGO1: chapitre 1 - partie 1 : Variables, Types, Opérations de base Гиперссылка
  • 

    Video cours ALGO1: chapitre 1 - partie 2 : Si, Pour, Tant Que Гиперссылка
  • 

    Video cours ALGO1: chapitre 1 - partie 3: Fonctions Гиперссылка
  • 

    Video cours ALGO1: chapitre 1 - partie 4: tableaux Гиперссылка
  • 

    Quizz Algo : les incontournables sur les tableaux Тест

    Получить оценку
  • 

    Quizz Algo : révisions de pseudo-code Тест

    Получить оценку
  • ---

    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 Файл
  • 

    Video cours ALGO1: chapitre 2 - partie 1 : intuition sur la rapidité d'un algo Гиперссылка
  • 

    Video cours ALGO1: chapitre 2 - partie 2 : Choix du paramètre et des opérations Гиперссылка
  • 

    Video cours ALGO1: chapitre 2 - partie 3 : Ordre de grandeur et choix du Pire cas Гиперссылка
  • 

    Video cours ALGO1: chapitre 2 - partie 4 : plein d'exemples ! Гиперссылка
  • 

    Quizz Algo : un calcul détaillé de complexité Тест

    Получить оценку
  • 

    Quizz Algo : complexité Тест

    Получить оценку
  • ---

    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) Файл
  • 

    Video cours ALGO1: chapitre 3 - partie 1 : Pourquoi? + notre premier invariant Гиперссылка
  • 

    Video cours ALGO1: chapitre 3 - partie 2 : Preuves de correction par invariant de boucle Гиперссылка
  • 

    Video cours ALGO1: chapitre 3 - partie 3 : Preuves de terminaison Гиперссылка
  • 

    Quizz : Preuve de correction par invariant de boucle Тест

    Получить оценку
  • A venir : des explications pour bien réussir le quizz sur les invariants

  • 

    Fiche TD01: analyse d'algo (complexité temporelle & preuves) Файл
  • 

    Catalogue d'algos (annexe fiche TD01) Файл
  • 

    Fiche TD01 commune aux Chap. 1, 2, 3 - corrigé Файл
  • ---

    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é Файл
  • 

    Video cours ALGO1: chapitre 4 - partie 1 : Principe et exemples Гиперссылка
  • 

    Video cours ALGO1: chapitre 4 - partie 2 : Compter la complexité, et introduction à Diviser pour Régner Гиперссылка
  • 

    Video cours ALGO1: chapitre 4 - partie 3 : Recherche dichotomique Гиперссылка
  • 

    Se rafraîchir la mémoire sur les suites arithmétiques et géométriques Гиперссылка
  • 

    Fiche TD02: récursivité Файл
  • 

    Corrigé fiche TD02 récursivité Файл
  • 

    Video expliquant l'algo. récursif des tours de Hanoï (Fiche TD02, exo 2) Гиперссылка
  • 

    Quizz : algorithmes récursifs Тест

    Получить оценку
  • ---

    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 Файл
  • 

    Video cours ALGO1: chapitre 5 - partie 1 : Introduction aux Types de Données Abstraits Гиперссылка
  • 

    Video cours ALGO1: chapitre 5 - partie 2 : Tableau Partiellement Rempli Гиперссылка
  • 

    Video cours ALGO1: chapitre 5 - partie 3: Liste chaînée : définition Гиперссылка
  • 

    Video cours ALGO1: chapitre 5 - partie 4: Liste chaînée : premières fonctions Гиперссылка
  • 

    Video cours ALGO1: chapitre 5 - partie 5: Liste chaînée : comparaison avec les tableaux PR Гиперссылка
  • 

    Video cours ALGO1: chapitre 5 - partie 6: Conclusion - Utilisation d'une Liste chaînée Гиперссылка
  • 

    Fiche TD03: listes chainées et tableaux partiellement remplis (PR) Файл
  • 

    Fiche TD03 corrige Файл
  • 

    Animation (corrigé) Exercice 1 TD03 Файл

    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 Тест

    Получить оценку
  • 

    Quizz : liste chaînée - algorithmes récursifs Тест

    Получить оценку
  • 

    Vidéo corrigé - Renverser liste récursif & impératif Гиперссылка
  • 

    Slides utilisées dans la vidéo - corrigé Renverser Liste Файл
  • 

    Quizz : choisir la bonne structure de données Тест

    Получить оценку
  • 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 Файл
  • 

    Implémentation des listes chaînées en Python Файл
  • 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) Файл
  • 

    Video cours ALGO1: chapitre 6 - partie 1 : Définition d'une liste doublement chaînée Гиперссылка
  • 

    Video cours ALGO1: chapitre 6 - partie 2 : fonctions sur une liste doublement chaînée Гиперссылка
  • 

    Video cours ALGO1: chapitre 6 - partie 3 : fonctions sur une liste doublement chaînée (suite) Гиперссылка
  • 

    Video cours ALGO1: chapitre 6 - partie 4 : conclusion & intro aux listes doublement chaînées circulaires Гиперссылка
  • 

    Fiche TD04: listes doublement chaînée (liste DC) et doublement chaînées circulaires (DCC) Файл
  • 

    Fiche TD04 corrigé Файл
  • 

    Quizz : liste doublement chaînée - entraînement Тест

    Получить оценку
  • 

    Quizz : découvrir les listes doublement chaînées circulaires Тест

    Получить оценку
  • 

    Quizz : listes doublement chaînées circulaires - entraînement Тест

    Получить оценку
  • ---

    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 Файл
  • 

    Video cours ALGO1: chapitre 7 - partie 1 : Point de vue implementation vs. Point de vue utilisateur Гиперссылка
  • 

    Video cours ALGO1: chapitre 7 - partie 2 : Pile Гиперссылка
  • 

    Video cours ALGO1: chapitre 7 - partie 3 : File Гиперссылка
  • 

    Fiche TD05: pile, file Файл
  • 

    Corrigé Fiche TD05: pile, file Файл
  • 

    Quizz : pile, file Тест

    Получить оценку
  • 

    Implémenter une pile avec une liste simplement chaînée Тест

    Получить оценку
  • 

    Implémenter une file avec une liste ou une variante de liste Тест

    Получить оценку
  • ---

    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 Файл
  • 

    Video cours ALGO1: chapitre 8 - partie 1 : Vocabulaire des arbres Гиперссылка
  • 

    Video cours ALGO1: chapitre 8 - partie 2 : fonctions sur les arbres Гиперссылка
  • 

    Video cours ALGO1: chapitre 8 - partie 3: parcours en largeur et en profondeur Гиперссылка
  • 

    Video cours ALGO1: chapitre 8 - partie 4 : Arbres Binaires de Recherche (ABR) Гиперссылка
  • 

    Video cours ALGO1: chapitre 8 - partie 5 : parcours infixe, préfixe, suffixe Гиперссылка
  • 

    Quizz : arbres Тест

    Получить оценку
  • 

    Fiche TD06: arbres et tris Файл
  • 

    Corrigé fiche TD06: arbres et tris Файл
  • ---

    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) Файл
  • 

    Animation tri fusion Файл
  • 

    Video cours ALGO1: chapitre 9 - partie 1 : tri par sélection Гиперссылка
  • 

    Video cours ALGO1: chapitre 9 - partie 2 : tri par insertion Гиперссылка
  • 

    Video cours ALGO1: chapitre 9 - partie 3 : tri rapide Гиперссылка
  • 

    Video cours ALGO1: chapitre 9 - partie 3 : tri fusion Гиперссылка
  • TD: voir le dernier exercice de la fiche de TD06: arbres et tris

  • 

    Quizz : tris Тест

    Получить оценку Получить проходной балл
  • ---

    Révisions

  • 

    Slides de révisions Файл

• Contributions, discussions enseignants
  • 

    Idées et contributions pour ce cours ouvert Форум