Rappels

Fonctions comme paramètres

def appliquer(fonction, valeur):
    """Applique une fonction à une valeur"""
    return fonction(valeur)

def carre(x):
    return x ** 2

resultat = appliquer(carre, 5)  # 25

Fonctions lambda

# Fonction lambda (anonyme)
carre = lambda x: x ** 2
somme = lambda a, b: a + b

# Avec map, filter
nombres = [1, 2, 3, 4, 5]
carres = list(map(lambda x: x**2, nombres))      # [1, 4, 9, 16, 25]
pairs = list(filter(lambda x: x%2==0, nombres))  # [2, 4]

Compréhensions de listes

# Liste des carrés
carres = [x**2 for x in range(10)]

# Avec condition
pairs = [x for x in range(20) if x % 2 == 0]

# Liste imbriquée
matrice = [[i*j for j in range(3)] for i in range(3)]

Principe

Une fonction récursive s'appelle elle-même. Elle doit avoir un cas de base pour arrêter les appels.

# Factorielle
def factorielle(n):
    if n == 0:              # Cas de base
        return 1
    return n * factorielle(n-1)  # Appel récursif

# Fibonacci
def fibonacci(n):
    if n <= 1:              # Cas de base
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# Somme d'une liste
def somme_recursive(liste):
    if len(liste) == 0:     # Cas de base
        return 0
    return liste[0] + somme_recursive(liste[1:])

# Créer un tuple
point = (3, 5)
coordonnees = (10, 20, 30)

# Accès
x = point[0]  # 3

# Unpacking
a, b = point  # a=3, b=5

# Tuple à un élément
singleton = (5,)  # Virgule obligatoire

# Créer un dictionnaire
eleve = {
    "nom": "Alice",
    "age": 17,
    "classe": "1NSI"
}

# Accès
nom = eleve["nom"]
age = eleve.get("age", 0)

# Ajouter/modifier
eleve["note"] = 15

# Parcourir
for cle, valeur in eleve.items():
    print(cle, valeur)

Méthodes des dictionnaires

dico = {"a": 1, "b": 2, "c": 3}

dico.keys()      # dict_keys(['a', 'b', 'c'])
dico.values()    # dict_values([1, 2, 3])
dico.items()     # dict_items([('a', 1), ('b', 2), ('c', 3)])
dico.pop("b")    # Supprime et retourne la valeur de "b"
"a" in dico      # True

Lecture de fichiers

# Lire tout le fichier
with open("fichier.txt", "r", encoding="utf-8") as f:
    contenu = f.read()

# Lire ligne par ligne
with open("fichier.txt", "r", encoding="utf-8") as f:
    for ligne in f:
        print(ligne.strip())

# Lire toutes les lignes dans une liste
with open("fichier.txt", "r", encoding="utf-8") as f:
    lignes = f.readlines()

Écriture dans des fichiers

# Écrire (écrase le contenu)
with open("fichier.txt", "w", encoding="utf-8") as f:
    f.write("Première ligne\n")
    f.write("Deuxième ligne\n")

# Ajouter à la fin
with open("fichier.txt", "a", encoding="utf-8") as f:
    f.write("Ligne ajoutée\n")

Recherche dans un tableau

# Recherche séquentielle
def recherche(tableau, valeur):
    for i in range(len(tableau)):
        if tableau[i] == valeur:
            return i
    return -1

# Recherche dichotomique (tableau trié)
def dichotomie(tableau, valeur):
    gauche, droite = 0, len(tableau) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == valeur:
            return milieu
        elif tableau[milieu] < valeur:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Tableaux à deux dimensions

# Créer une matrice 3x3
matrice = [[0, 1, 2],
           [3, 4, 5],
           [6, 7, 8]]

# Accès
element = matrice[1][2]  # 5

# Parcours
for ligne in matrice:
    for element in ligne:
        print(element, end=" ")

Structure d'un arbre

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

# Créer un arbre
racine = Noeud(10)
racine.gauche = Noeud(5)
racine.droite = Noeud(15)
racine.gauche.gauche = Noeud(3)
racine.gauche.droite = Noeud(7)

Parcours d'arbres

# Parcours préfixe (racine, gauche, droite)
def parcours_prefixe(noeud):
    if noeud is not None:
        print(noeud.valeur)
        parcours_prefixe(noeud.gauche)
        parcours_prefixe(noeud.droite)

# Parcours infixe (gauche, racine, droite)
def parcours_infixe(noeud):
    if noeud is not None:
        parcours_infixe(noeud.gauche)
        print(noeud.valeur)
        parcours_infixe(noeud.droite)

# Parcours postfixe (gauche, droite, racine)
def parcours_postfixe(noeud):
    if noeud is not None:
        parcours_postfixe(noeud.gauche)
        parcours_postfixe(noeud.droite)
        print(noeud.valeur)

Opérations sur les arbres

# Hauteur d'un arbre
def hauteur(noeud):
    if noeud is None:
        return -1
    return 1 + max(hauteur(noeud.gauche), hauteur(noeud.droite))

# Taille d'un arbre (nombre de noeuds)
def taille(noeud):
    if noeud is None:
        return 0
    return 1 + taille(noeud.gauche) + taille(noeud.droite)

Représentation par liste d'adjacence

# Graphe non orienté
graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Parcours en largeur (BFS)

def parcours_largeur(graphe, depart):
    visite = set()
    file = [depart]
    
    while file:
        sommet = file.pop(0)
        if sommet not in visite:
            print(sommet)
            visite.add(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visite:
                    file.append(voisin)

Parcours en profondeur (DFS)

def parcours_profondeur(graphe, sommet, visite=None):
    if visite is None:
        visite = set()
    
    visite.add(sommet)
    print(sommet)
    
    for voisin in graphe[sommet]:
        if voisin not in visite:
            parcours_profondeur(graphe, voisin, visite)

Tri par sélection

def tri_selection(tableau):
    n = len(tableau)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if tableau[j] < tableau[min_idx]:
                min_idx = j
        tableau[i], tableau[min_idx] = tableau[min_idx], tableau[i]
    return tableau

Tri par insertion

def tri_insertion(tableau):
    for i in range(1, len(tableau)):
        cle = tableau[i]
        j = i - 1
        while j >= 0 and tableau[j] > cle:
            tableau[j + 1] = tableau[j]
            j -= 1
        tableau[j + 1] = cle
    return tableau

Notation O (grand O)

Mesure l'efficacité d'un algorithme en fonction de la taille des données.

Définir une classe

class Voiture:
    # Constructeur
    def __init__(self, marque, modele):
        self.marque = marque      # Attribut
        self.modele = modele
        self.vitesse = 0
    
    # Méthode
    def accelerer(self, increment):
        self.vitesse += increment
    
    def __str__(self):
        return f"{self.marque} {self.modele} ({self.vitesse} km/h)"

# Créer un objet
ma_voiture = Voiture("Renault", "Clio")
ma_voiture.accelerer(50)
print(ma_voiture)  # Renault Clio (50 km/h)

Héritage

class VoitureElectrique(Voiture):
    def __init__(self, marque, modele, autonomie):
        super().__init__(marque, modele)
        self.autonomie = autonomie
    
    def recharger(self):
        self.autonomie = 100
        print("Batterie rechargée !")

# Utilisation
tesla = VoitureElectrique("Tesla", "Model 3", 80)
tesla.accelerer(60)
tesla.recharger()