Aller au contenu

🏠 Accueil

Bienvenue sur ce site dédié aux structures arborescentes avec Python, pour les élèves qui souhaitent approfondir leurs connaissances en algorithmique et se tester en autonomie. Cours progressif, exercices débranchés, exercices pratiques.

Python sans aucune installation, et en local

De très nombreux exercices en Python sont inclus dans ce site web. Le code est exécuté en local sur votre machine, sans aucune installation nécessaire. Le respect du RGPD est complet, il n'y a strictement aucune donnée qui sort ; gage de sécurité. Ceci est rendu possible avec la technologie Pyodide 1 qui a été portée vers MkDocs2 initialement par Vincent BOUILLOT 3, puis par Frédéric ZINELLI 4. Un grand merci à eux, et tous les collègues qui ont participé à la relecture, comme Nicolas REVÉRET avec qui nous avons créé une très grande partie du contenu du groupe e-nsi. Pour ce chapitre, tout le cours et les exercices sont créés par Franck CHAMBON.

Contenus en bonus

  1. La présence de 🎁 indique un petit cadeau, sous forme de compléments de cours, accessible si vous résolvez correctement un exercice.
  2. La présence de 🥚 indique un exercice fécond, en plusieurs parties, accessibles progressivement en cas de succès aux premiers. Un joli cadeau se trouve à la fin ; un easter egg.

Extraits de contenu

Compléter la fonction somme qui est récursive

Vous ajouterez des tests !

🐍 Script Python
def somme(arbre):
    "Renvoie la somme des valeurs des nœuds de l'arbre"
    racine, enfants = arbre
    return ... + sum(... for sous_arbre in enfants)

# Tests
T_6 =[[6, [
    [5, [
        [3, []],
        [1, []],
    ]],
    [4, []],
    [2, []],
]]
assert somme(T_6) == 21

Exemple : Un arbre à six nœuds

graph TB
    A(6)
    B(5)
    C(4)
    D(2)
    E(3)
    F(1)
    A --- B
    A --- C
    A --- D
    B --- E
    B --- F

Un arbre binaire de hauteur 3

graph TB
    N0("11")
    N0 --> N1("42")
    N0 --> N2("11")
    N1 --> N11(" ")
    N1 --> N12("21")
    N12 --> N121(" ")
    N12 --> N122(" ")
    N2 --> N21(" ")
    N2 --> N22(" ")

Un arbre binaire de recherche

graph TB
    A("28")
    B("13")
    C("35")
    D("13")
    E((" "))
    F("32")
    G("43")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M

Contenu

  • Du cours détaillé avec de nombreux exemples.
  • Des exercices débranchés pour illustrer le cours.
  • De nombreux exercices d'algorithmique et de programmation en Python, en ligne, avec autocorrection.
  • Mode jour (idéal pour vidéoprojecteur) ou mode nuit pour apaiser la lecture.

Au programme

  • On découvre les graphes de manière succincte
    • et on teste pour prendre un bon départ.
  • On découvre les variétés d'arbres avec plusieurs angles d'approches :
    • d'abord comme un graphe connexe acyclique,
      • l'occasion de réviser les dictionnaires (avec l'adjacence),
    • puis les arbres binaires,
      • un peu de POO, une classe Noeud sans méthode,
    • puis les arbres binaires de recherche,
      • l'occasion de créer une classe ABR avec ses méthodes,
    • puis les arbres binaires presque complets,
      • avec des modélisations variées suivant le contexte,
      • tels les tas, en guise d'exercices facultatifs,
      • et d'autres encore...
    • puis les arbres enracinés, qui ont une racine précisée,
      • pas de POO dans cette section, uniquement des listes imbriquées.
      • Mais avec certains exercices qui sont plus difficiles.

De très nombreux exercices sont présentés

  • La récursivité intervient souvent.
  • La programmation dynamique y est parfois présente (🥼).
  • Il y a plusieurs niveaux de difficulté
    • Application directe du cours et des méthodes.
    • 💥 Nécessite une autre technique ou structure, comme un dictionnaire...
    • 💥💥 Nécessite des techniques variées, comme des constructions de fonctions auxiliaires...
    • 💥💥💥 Nécessite de réfléchir plus sérieusement...
  • Une correction détaillée écrite avec soin est proposée ; ne pas hésiter pas à l'étudier !
  • Il faut comprendre que l'écriture des tests de validation, partie cachée, est également un travail complexe.
  • Bonne progression !

Culture

Arbre de famille de langues

Voici la structure des liens entre langues indo-européennes et fino-ougriennes.

Langues

Source : Feast Your Eyes on This Beautiful Linguistic Family Tree

  1. Pyodide is a Python distribution for the browser and Node.js based on WebAssembly. ↩

  2. MkDocs is a fast, simple and downright gorgeous static site generator. ↩

  3. Pyodide-MkDocs 0.9.1 : Terminal et IDE dans MkDocs ↩

  4. Pyodide-Mkdocs-Theme : Éditeurs & terminaux python dans MkDocs ↩