Matrices d'adjacence. Recherche de plus court chemin dans Orsay ; alignement de séquences d'ADN. Algorithme de Dijkstra ; algorithme A*.
Parcours en profondeur d'un graphe avec une pile ; résolution d'une version simplifié du solitaire.
Graphes orientés/non orientés, pondérés/non pondérés ; sommets, arêtes, arcs, valeurs ; listes d'adjacence, dictionnaires, matrices d'adjacence ; files ; parcours en largeur ; test de connexité ; recherches de circuits ou de cycles.
Piles et dictionnaires ; détection d'enveloppe convexe, recherche de paires de points la plus proche.
Variant de boucle et terminaison d'algorithme ; invariant de boucle et correction d'algortihme. Exponentiation rapide (le retour !) ; PGCD et calculs exacts de fractions rationnelles ; système de conversion esperluette.
Questions de cours : tri par sélection, tri fusion, tri rapide ; tri d'une liste de mots, recherche dans une liste, compléxité ; aide au scrabble.
Suite de Fibonnaci : calcul direct, exponentiation rapide, récurence, fonction récursive, compléxité ; fractions égyptiennes : différence de fraction, algorithme glouton de Fibonacci-Sylverster.
Rendu de monnaie ; fermeture de filiale (variante du problème du sac à dos) ; allocation d'une salle de spectacle.
Fonctions récursives : factorielle, récherche dichotomique, tours de Hanoï, fractale du dragon, recherche de rectangle, sudoku
Questions de cours : recherche d'éléments, de doublon, tri bulle ; permutations.
Module numpy ; manipulation d'images.
Fichiers
Traçons de jolies courbes depuis un fichier texte ; après résolution numérique d'une équation différentielle ; pour le plaisir avec une fractale.
Recherche dans une liste triée ; exponentiation rapide ; recherche du zero d'une fonction.
Boucles successives, boucles imbriquées, compléxité linéaire, complexité quadratique ; recherche d'élément, de maximum, de second maximum, de doublon, d'éléments les plus proches ; tri bulle ; recherche de mot dans un texte ; où est Charlie ? séquençage de brin d'ADN.
Génome de la bactérie B. burgdorferi.
Un module pour lire un fichier texte.
Jeu de Kalyes, nombre de Grundy.
Fonctions, listes, calcul de somme, supression d'élément dans une liste, recherche d'élément dans une liste, recherche de minimum...
Pour les plus rapide, facultatif.
Variables locales, variables globales ; copie de listes ; modification de listes dans une fonction ; jeu du Backgammon
Variables locales, variables globales ; copie de listes ; modification de listes dans une fonction ; modèle simplifié du périphérique, calcul de la vitesse moyenne en fonction du traffic.
Uplets et listes ; fonctions ; recherche d'un élément dans une liste, recherche de maximum et second maximum ; simulation de propagation d'une épidémie.
Chaînes de caractères ; indices, slicing ; concaténation ; parcours par valeur, parcours par position ; recherche d'un caractère, occurence d'un caractère ; palindrome, anagramme, jeu du pendu.
Corrigé des 6 premiers exercices.
pyzo ; variables ; script ; boucle for ; instruction conditionnelle if ; boucle while ; calculs de sommes...
