DIU EIL de Grenoble – bloc 2 : Algorithmique
Retour au site principal du DIU
Table des matières
- 1. Documents 2020
- Apprentissage Par Problèmes (Lundi 6 juillet)
- Débat scientifique (Lundi 6 juillet)
- Démarche algorithmique et complexité Lundi 6 juillet)
- Introduction aux preuves de correction et de terminaison de programmes (mardi 7 juillet)
- Apprentissage Par Problèmes (Mardi 7 juillet + suite)
- Diviser pour régner
- Structures arborescentes
- Introduction aux graphes par Nadia Brauner
- Recherche de motifs dans un texte
- Structure de donnée partition : Union-Find
- Algorithmes glouton
- Arbre couvrant minimal : Kruskal-Prim
- 2. Évaluation 2019
- 3. Documents 2019
- Débat scientifique (Jeudi 11 avril)
- Introduction aux preuves de correction et de terminaison de programmes (Mercredi 15 mai et mercredi 22 mai)
- Démarche algorithmique et complexité (Mercredi 22 mai)
- Introduction aux graphes (Mercredi 29 mai)
- Expression des algorithmes (Lundi 24 avril)
- Apprentissage Par Problèmes (Lundi 24 avril + suite)
- Diviser pour régner l'archétype du tri (Mardi 25/mercredi 26 juin)
- Les arbres (Jeudi 27 juin)
- Un peu de glouton (Lundi 1er juillet)
- Retour APP et QCM (Jeudi 4 juillet)
- Activités d'informatique débranchée (Jeudi 4 juillet)
- Recherche de motifs dans un texte (Vendredi 5 juillet)
- Enveloppe convexe d'un nuage de points
- 4. Quelques références bibliographiques
1 Documents 2020
Apprentissage Par Problèmes (Lundi 6 juillet)
- Les documents distribués :
Débat scientifique (Lundi 6 juillet)
- Les deux diapos
- Les scripts utilisés pour la séance en fichier zip
- Pour compléter la séance :
- Ensembles et Séquences vs Tableaux : sur la représentation des ensembles et séquences en mémoire à base de tableaux (proche de ce qu'utilise python pour ses listes)
- Complexité : une introduction à la complexité algorithmique
Démarche algorithmique et complexité Lundi 6 juillet)
une petite introduction à la démarche algorithmique et la la complexité d'un problème Transparents
Comme exercice on peut analyser les différents algorithmes de calcul des nombres de Fibonnacci Code python
- le calcul par appels récursifs, mémoisation explicite (dictionnaire) ou implicite (décoration de fonction)
- le calcul itératif (approche bottom-up avec ou sans recouvrement de la mémoire)
- une approche matricielle basée sur l'exponentiation rapide de matrice
- reprendre avec le schéma du TD de programmation \[\begin{cases} F_{2n}=F_n^2+F_{n-1}^2 & \\ F_{2n+1}= (2F_{n-1}+F_n)F_n& \end{cases}\]
Bien entendu les méthodes de comptage et de mesure de temps d'exécution sont rudimentaires, il est plus intéressant d'utiliser des décorateurs de fonctions qui ajouteront automatiquement la fonctionalité demandée et sera donc réutilisable dans tout contexte.
On peut également reprendre la formule de Binet en utilisant l'exponentiation rapide et un arrondi. \[ F_n=\frac 1 {\sqrt{5}} \left( \frac {1+\sqrt{5}}2\right)^{n+1} - \frac 1 {\sqrt{5}} \left( \frac {1-\sqrt{5}}2\right)^{n+1} \]
Comment évolue la taille de \(F_n\) en fonction de \(n\) ? Quelles remarques peut-on faire sur la complexité du calcul ?
Introduction aux preuves de correction et de terminaison de programmes (mardi 7 juillet)
Un code sans bug, c'est parfois impératif (nucléaire, aviation, etc.) Les tests sont un élément essentiel du développement logiciel permettant de détecter et corriger des bugs (le plus tôt est le mieux), mais ils ne suffisent pas dans certains contextes.
Pour prouver (mais aussi pour tester), il faut avoir des spécifications (plus ou moins formelles) comme les signatures (des modules, objets, fonctions, etc.), les pré-conditions, les post-conditions, etc.
Pour les algorithmes, on peut prouver différents types de propriétés (terminaison, complexité, correction, etc.), preuves communes ou séparées suivant les algorithmes. Comme en mathématique, les preuves peuvent être plus ou moins formelles. En cas de boucles dans les algorithmes, les preuves utilisent souvent la notion d'invariants (propriétés vérifiées à chaque tour de boucle). Trouver le bon invariant est souvent la partie difficile de la preuve.
Une preuve n'est valide que dans son contexte. Une preuve d'un algorithme ne suffit pas à garantir un programme sans bug. Il faut aussi qu'il n'y ait pas de bugs dans l'implémentation de l'algorithme (dans le langage choisi par le programmeur), ni dans les outils de compilation, ni dans l'environnement de programmation et d'exécution (bibliothèques, système d'exploitation, etc.), ni dans le matériel exécutant le code (microprocesseurs, bus de communication, etc.), ni …
Exemple avec des algorithmes de tris et une correction plutôt formelle de la preuve du tri par insertion. Fichier python des algorithmes de tris proposés.
Apprentissage Par Problèmes (Mardi 7 juillet + suite)
- Les documents distribués :
- Les documents supplémentaires :
Diviser pour régner
pour le Tri partition/fusion et le quicksort voir les feuilles de TD (le niveau est à adapter à des terminales, les TD vont au-dela)
Pour le Master theorem (savoir qu'il existe et qu'il y a 3 cas de figure)
voir les documents en fin de page sur les enveloppes convexes
Structures arborescentes
Introduction aux graphes par Nadia Brauner
Recherche de motifs dans un texte
Structure de donnée partition : Union-Find
Les transparents ici
Algorithmes glouton
Les transparents et le problème de l'allocation d'intervalles (code illustratif, non optimisé)
Arbre couvrant minimal : Kruskal-Prim
- Transparents du cours
- Fiche de TD
2 Évaluation 2019
Cette évaluation se déclinera en trois points :
- Un QCM de 3/4 d'heure qui sera fait le vendredi 28 juin matin pendant une séance d'algorithmique, et qui portera sur les notions vues en séances jusqu'à ce jour.
- Un rapport à effectuer par groupes de 5-6 personnes et qui portera sur un problème que vous aurez à étudier durant 4 séances d'Apprentissage Par Problème (APP). Ce rapport pourra être effectué sous forme électronique ou papier.
- La fiche d'activité (séquence pédagogique), comme dans les autres blocs.
Les rendus sont pour le vendredi 5 juillet, à donner en main propre ou envoyer aux personnes suivantes : Florent Bouchez Tichadou, Jean-Marc Vincent, Vincent Danjean.
N'hésitez pas à nous contacter si vous souhaitez plus de précisions.
3 Documents 2019
Débat scientifique (Jeudi 11 avril)
- Les deux diapos
- Les scripts utilisés pour la séance en fichier zip
- Pour compléter la séance :
- Ensembles et Séquences vs Tableaux : sur la représentation des ensembles et séquences en mémoire à base de tableaux (proche de ce qu'utilise python pour ses listes)
- Complexité : une introduction à la complexité algorithmique
Introduction aux preuves de correction et de terminaison de programmes (Mercredi 15 mai et mercredi 22 mai)
Un code sans bug, c'est parfois impératif (nucléaire, aviation, etc.) Les tests sont un élément essentiel du développement logiciel permettant de détecter et corriger des bugs (le plus tôt est le mieux), mais ils ne suffisent pas dans certains contextes.
Pour prouver (mais aussi pour tester), il faut avoir des spécifications (plus ou moins formelles) comme les signatures (des modules, objets, fonctions, etc.), les pré-conditions, les post-conditions, etc.
Pour les algorithmes, on peut prouver différents types de propriétés (terminaison, complexité, correction, etc.), preuves communes ou séparées suivant les algorithmes. Comme en mathématique, les preuves peuvent être plus ou moins formelles. En cas de boucles dans les algorithmes, les preuves utilisent souvent la notion d'invariants (propriétés vérifiées à chaque tour de boucle). Trouver le bon invariant est souvent la partie difficile de la preuve.
Une preuve n'est valide que dans son contexte. Une preuve d'un algorithme ne suffit pas à garantir un programme sans bug. Il faut aussi qu'il n'y ait pas de bugs dans l'implémentation de l'algorithme (dans le langage choisi par le programmeur), ni dans les outils de compilation, ni dans l'environnement de programmation et d'exécution (bibliothèques, système d'exploitation, etc.), ni dans le matériel exécutant le code (microprocesseurs, bus de communication, etc.), ni …
Exemple avec des algorithmes de tris et une correction plutôt formelle de la preuve du tri par insertion. Fichier python des algorithmes de tris proposés.
Démarche algorithmique et complexité (Mercredi 22 mai)
une petite introduction à la démarche algorithmique et la la complexité d'un problème Transparents
Comme exercice on peut analyser les différents algorithmes de calcul des nombres de Fibonnacci Code python
- le calcul par appels récursifs, mémoisation explicite (dictionnaire) ou implicite (décoration de fonction)
- le calcul itératif (approche bottom-up avec ou sans recouvrement de la mémoire)
- une approche matricielle basée sur l'exponentiation rapide de matrice
- reprendre avec le schéma du TD de programmation \[\begin{cases} F_{2n}=F_n^2+F_{n-1}^2 & \\ F_{2n+1}= (2F_{n-1}+F_n)F_n& \end{cases}\]
Bien entendu les méthodes de comptage et de mesure de temps d'exécution sont rudimentaires, il est plus intéressant d'utiliser des décorateurs de fonctions qui ajouteront automatiquement la fonctionalité demandée et sera donc réutilisable dans tout contexte.
On peut également reprendre la formule de Binet en utilisant l'exponentiation rapide et un arrondi. \[ F_n=\frac 1 {\sqrt{5}} \left( \frac {1+\sqrt{5}}2\right)^{n+1} - \frac 1 {\sqrt{5}} \left( \frac {1-\sqrt{5}}2\right)^{n+1} \]
Comment évolue la taille de \(F_n\) en fonction de \(n\) ? Quelles remarques peut-on faire sur la complexité du calcul ?
Introduction aux graphes (Mercredi 29 mai)
Expression des algorithmes (Lundi 24 avril)
Quelques remarques autour de l'expression des algorithmes Transparents
Apprentissage Par Problèmes (Lundi 24 avril + suite)
- Les documents distribués :
- Les documents supplémentaires :
Diviser pour régner l'archétype du tri (Mardi 25/mercredi 26 juin)
À partir de l'analyse de deux algorithmes de tri, le tri partition/fusion et le tri par segmentation, on abordera le principe de diviser pour régner avec les schémas récursifs correspondants.
On reprend également le calcul de la complexité associée à de tels schémas Master Theorem
Feuille d'exercice avec des exercices avancés (les 3,4 et 5)
Pour réaliser la segmentation en place on utilise un algorithme dit du "drapeau hollandais", dû à Dijkstra ? (à confirmer) ou à Hoare (partition) Exemple du drapeau hollandais
Quelques compléments
Le texte de Hoare Communication of the ACM page 321
Comment "tuer" Quicksort A Killer Adversary for Quicksort
Les arbres (Jeudi 27 juin)
Introduction : qu'est-ce qu'un arbre ?
- des racines, des branches, un tronc, des feuilles, ça grandit avec du soleil et du CO2
une racine, des branches, des feuilles et c'est présent dans plein d'algorithmes
Un arbre n'est pas un objet natif en informatique. Ce n'est pas un type de base dans le matériel et très rarement dans les languages.
Un arbre est une structure pour stocker et/ou représenter de l'information, structure sur laquelle on pourra appliquer des algorithmes.
Avoir une structure générique permet de concevoir des algorithmes génériques s'appliquant à de nombreux problèmes différents.
- Spécifications
- de l'objet lui-même
- graphe sans cycle maximum en nombre d'arrête (avec un nœud racine)
Arbre := ArbreVide | (Étiquette, liste(Arbre))
Ici, pas de distinction entre un arbre et un sous-arbre. C'est souvent une vision intéressante (appels récursifs facilités) mais parfois on a besoin de distinguer les deux notions.
- des accès
- ListeFils(Arbre) -> liste(Arbre)
- LectureEtiquette(Arbre) -> Étiquette
- père(Arbre) -> Arbre
- EstVide(Arbre) -> boolean
- nbFils(Arbre) -> int
- de la construction de l'objet
- construction fonctionnelle (sans effet de bord)
- ArbreVide()
- NouvelArbre(Étiquette, Arbre, Arbre) -> Arbre
- construction avec effet de bord
- ArbreVide()
- AjouterFils(Arbre, Arbre) Le second arbre est ajouté à la liste des fils du premier
- construction fonctionnelle (sans effet de bord)
- de l'objet lui-même
Propriétés
- profondeur d'un nœud
- profondeur(n) = distance(n, racine)
- hauteur d'un arbre
- hauteur(arbre) = maxn ∈ arbre(profondeur(nœud))
- par convention : hauteur(arbreVide) = -1
- niveaux d'un arbre
- niveau(i, arbre) = { nœud ∈ arbre tq prof(nœud) == i }
Formes d'arbres
- Arbres binaires et Arbres n-aires
Arbres binaires très utilisés en algorithmique, avec des spécifications adaptées :
- FilsGauche(Arbre) -> Arbre
- FilsDroit(Arbre) -> Arbre
- NouvelArbre(Etiquette, Arbre, Arbre) -> Arbre
- peignes
- équivalent à une pile
- arbres binaires équilibrés
- ∀ nœud ∈ arbre, |hauteur(filsDroit(nœud))-hauteur(filsGauche(nœud))| ≤ 1
Représentation des arbres
- n-uplet
- objet
- tableau (chaînage par indice)
Algorithmes de parcours classiques
parcours en profondeur
- préfixé
- infixé exemple : Arbre Binaire de Recherche (ABR)
- posfixé exemple : calcul
Les trois en même temps : les appels de fonctions imbriquées (i.e. l'arbre d'exécution des fonctions d'un programme)
parcours_profondeur_recursif(arbre): traiter_prefixe(arbre) if non estArbreVide(fg(arbre)): parcours_profondeur_recursif(fg(arbre)) traiter_infixe(arbre) if non estArbreVide(fd(arbre)): parcours_profondeur_recursif(fd(arbre)) traiter_postfixe(arbre)
parcours_profondeur_prefixe(arbre): f = pileVide() enpiler(f, racine(arbre)) while non pileEstVide(f): n = depiler(f) if non estArbreVide(n): traiter_prefix(n) enpiler(f, fg(n)) enpiler(f, fd(n))
parcours en largeur utilisation d'une file.
En python, il faut utiliser un objet 'deque' qui permet des insertions/suppressions à l'un des deux bouts en temps constant. La liste classique permet l'insertion et la suppression en fin en temps constant, mais pas au début (coût linéaire). Or, pour une file, il faut enfiler à un bout et défiler à l'autre bout.
parcours_largeur(arbre): f = fileVide() enfiler(f, racine(arbre)) while non fileEstVide(f): n = defiler(f) if non estArbreVide(n): traiter(n) enfiler(f, fg(n)) enfiler(f, fd(n))
- exercices :
- calcul de la hauteur d'un arbre binaire
- calcul du nombre de nœuds d'un arbre binaire
- calcul du nombre de feuilles d'un arbre binaire
Pour aller plus loin
- Exercice présenté en cours : rotation d'un arbre
- Exemple de feuilles d'exercices de troisième année de licence
TD sur les arbres binaires :
- manipulation d'arbres binaires avec une interface imposées
TD sur les arbres n-aires :
- comment 'ranger' un arbre n-aire dans un arbre binaire
- réflexions sur la différence entre la structure que l'on veut manipuler logiquement (l'arbre n-aire) et la structure dont on se sert pour la stocker (arbre binaire)
Un peu de glouton (Lundi 1er juillet)
Les transparents et le problème de l'allocation d'intervalles (code illustratif, non optimisé) Le problème de l'arbre couvrant (feuille de TD) Quelques exercices de TD feuille de TD
Retour APP et QCM (Jeudi 4 juillet)
- les transparents diffusés
- le logiciel Auto Multiple Choice :
- Site web
- Le QCM généré (60 exemplaires avec permutation des réponses)
Le code source LaTeX du QCM (les insertions d'image ont été commentées pour simplifier la compilation)
Note : en commentant la ligne
,noshufflegroups
(ligne 13) et la ligne\newpage
(ligne 149), on obtient le même QCM avec :- permutation des groupes de questions
- permutation des questions dans les groupes
- mais le groupe "histoire" à la fin
- et la question de la citation toujours en dernier
Activités d'informatique débranchée (Jeudi 4 juillet)
Point d'entrée possible pour ces activités :
- plusieurs activités y sont directement proposées
- des liens permettent de découvrir d'autres sites avec d'autres activités (et d'autres liens)
- pour aller plus loin sur les marmottes aller voir le cours sur la compression du DU-ISN page
Recherche de motifs dans un texte (Vendredi 5 juillet)
Enveloppe convexe d'un nuage de points
Le problème : Étant donné un nuage de n points du plan, il faut construire l'enveloppe convexe de ces points, c'est à dire la séquence de points du nuage formant un polygone englobant l'ensemble du nuage.
En fait l'objectif pédagogique de la séance est de retrouver quelques schémas algorithmiques et de les adapter à un autre contexte. Nous n'avons détaillé que les algorithmes (pas de mise en oeuvre qui peut être faite par la suite)
On revient également sur la complexité de ces algorithmes et on révise des éléments de récursivité.
Algorithme de Jarvis (1973)
L'algorithme consiste à partir d'un point de l'enveloppe, par exemple celui d'ordonnée la plus faible puis à prendre la droite d'angle le plus faible avec les points restants
On évalue la complexité de cet algorithme (faire les calculs) à \(\mathcal{O}(n^2)\)
À quel schéma d'algorithme cela fait-il penser ? (tri par sélection)
Algorithme de Graham (1972)
L'algorithme consiste à partir d'un point intérieur (centre), on trie l'ensemble des points par angle croissant et on parcourt ces points dans l'ordre, le cas échéant, lorsque la convexité n'est pas respectée on se connecte au point précédentde l'enveloppe, par exemple celui d'ordonnée la plus faible puis à prendre la droite d'angle le plus faible avec les points restants
On évalue la complexité de cet algorithme (faire les calculs) à \(\mathcal{O}(n^2)\)
À quel schéma d'algorithme cela fait-il penser ? (tri par insertion)
Algorithme de partition-fusion
L'algorithme consiste à séparer par une droite le nuage de points en 2 nuages de points de même taille, on peut au préalable trier les points par abscisse croissante (coût en \(\mathcal{O}(n\log n)\)). On applique l'algorithmes aux deux sous-nuages, puis on recolle les 2 enveloppes obtenues en "remontant les tangentes" plus faible avec les points restants
On évalue la complexité de cet algorithme (faire les calculs) à \(\mathcal{O}(n \log n)\)
À quel schéma d'algorithme cela fait-il penser ? (tri partition fusion)
Algorithme Quick-Hull
L'algorithme consiste à segmenter le nuage par un segment entre 2 points de l'enveloppe (ici les points de plus faible et plus grande abscisse). On traite indépendamment le nuage au dessus du segment et au-dessous du segmen. On prend le point le plus éloigné du segment(il est sur l'enveloppe) et on recommence.
On évalue la complexité de cet algorithme (faire les calculs) à \(\mathcal{O}(n \log n)\) en moyenne
À quel schéma d'algorithme cela fait-il penser ? (tri par segmentation)
4 Quelques références bibliographiques
Attention cette bibliographie concerne la formation des enseignants et n'est pas destinée aux élèves de NSI, elle permet de prendre du recul par rapport au domaine et illustre des approches différentes de l'algorithmique. Des références historiques sont également fournies ainsi que des ouvrages plus "grand public".
Pour aller plus loin le site Interstice contient une foule d'idées et de synthèses accessibles pour des élèves de lycée
Et pour la compréhension des liens entre informatique et société le Le blog binaire du Monde