0. Prérequis

Avoir validé la Leçon 1 (référentiel et parcours). Connaître les opérateurs de base d'un langage impératif (Python ou JavaScript). Avoir installé sur sa machine : Python 3.11+, OpenJDK 17+, PHP 8.2+, Node.js 20+, un IDE (VS Code, IntelliJ IDEA Community ou PyCharm Educational). Lecture conseillée : docs.python.org/3/tutorial.

1. Introduction contextuelle — programmer, ce n'est pas que coder

En 1968, lors de la célèbre conférence de l'OTAN à Garmisch, le terme « crise du logiciel » est forgé : les projets explosent en coût, en délai et en bugs. C'est l'acte de naissance du génie logiciel et de l'algorithmique scientifique. Depuis, Donald Knuth (TAOCP, 1968-2025), Edsger Dijkstra (« Go To Statement Considered Harmful », 1968), Niklaus Wirth (Pascal) et plus récemment Guido van Rossum (Python, 1991) ont forgé les fondations.

Au BUT Informatique, la R1.01 Initiation au développement au S1 forme à la rigueur algorithmique (séquence, sélection, itération, fonctions, complexité). La R2.01 Développement orienté objets au S2 introduit Java et les 4 piliers de la POO. Les SAÉ S1.01 (« Implémentation d'un besoin client »), S2.01 (« Développement d'une application »), S3.01 (« Développement d'une application complexe ») cadrent l'évaluation.

L'enjeu : un développeur senior produit 10 à 20 lignes de code par jour en moyenne — ce qui semble peu jusqu'à comprendre que 80 % du temps est consacré à lire du code, débuguer, tester et documenter. La lisibilité prime donc sur le « code malin ». Le programme du BUT cible donc autant la maîtrise syntaxique que les bonnes pratiques : nommage, modularité, tests unitaires, revues de code.

Cette leçon couvre les langages obligatoires, la théorie de la complexité, les structures de données, la POO, les patrons et la programmation dynamique. Tous les exemples sont fonctionnels et testés.

2. Les langages enseignés en BUT Informatique

Le Programme National BUT Informatique 2021 impose un tronc multilingue. Aucun parcours ne se limite à un seul langage.

Selon Bjarne Stroustrup, créateur du C++ : « Il n'existe que deux types de langages : ceux dont les gens se plaignent et ceux que personne n'utilise. » — Choisir un langage, c'est accepter ses compromis.
Source : stroustrup.com.

3. Notions fondamentales d'algorithmique

3.1 Structures de contrôle universelles

Tout algorithme repose sur 3 structures de base, démontrées formellement par Corrado Böhm & Giuseppe Jacopini en 1966 (« Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules », Communications of the ACM) :

1. Séquence : les instructions s'exécutent l'une après l'autre.
2. Sélection (alternative) : if / else if / else, ou switch / match.
3. Itération (répétition) : while, for, do-while.

Toute fonction calculable peut être écrite avec ces 3 structures — c'est l'équivalence de Turing. Le goto est donc strictement évitable (cf. Dijkstra, 1968).

3.2 Complexité asymptotique — notation O

La notation O (Big-O) mesure le comportement d'un algorithme quand n → +∞, indépendamment du matériel.

Selon Donald Knuth (« Structured Programming with go to Statements », Computing Surveys, 1974) : « Premature optimization is the root of all evil. » — La lisibilité prime sur l'optimisation tant que la complexité asymptotique reste correcte.
Source : doi.org/10.1145/356635.356640.

4. Structures de données classiques

4.1 Structures linéaires

4.2 Structures hiérarchiques

• Arbre binaire de recherche (BST) — recherche/insertion O(log n) si équilibré, O(n) dégénéré.
• Arbre AVL / Rouge-Noir — auto-équilibré, garantit O(log n).
• Tas (heap) — extraction min/max en O(log n), usage : files de priorité (Dijkstra), tri par tas.
• Trie (arbre de préfixes) — autocomplétion, correcteur orthographique, dictionnaires.
• B-tree / B+ tree — index bases de données (PostgreSQL, MySQL InnoDB).

4.3 Graphes

• Représentation : matrice d'adjacence O(V²) en espace, ou liste d'adjacence O(V+E).
• Parcours : DFS (Depth-First Search, pile) — trouve cycles, composantes connexes. BFS (Breadth-First Search, file) — plus court chemin en nombre d'arêtes.
• Plus court chemin pondéré : Dijkstra (1959, poids positifs, O((V+E) log V)), Bellman-Ford (poids négatifs, O(V·E)), Floyd-Warshall (tous-vers-tous, O(V³)).
• Arbre couvrant minimum (MST) : Kruskal (tri arêtes + union-find), Prim (tas).

4.4 Schéma ASCII — pile vs file

PILE (LIFO)             FILE (FIFO)
                        +---+---+---+---+
[Pop] <- sommet  -> [D] | A | B | C | D | -> [Dequeue C? Non, A]
                        +---+---+---+---+
[Push E] ->        [E]    debut             fin
[D] [C] [B] [A]    base    Enqueue --> (cote fin)

5. Application pratique — 4 cas concrets résolus

# Recherche dichotomique en Python - O(log n) en temps, O(1) en espace
def dicho(tab, x):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == x:
            return m
        elif tab[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1

# Test
print(dicho([1, 3, 5, 7, 9, 11, 13], 7))   # 3
print(dicho([1, 3, 5, 7, 9, 11, 13], 4))   # -1

// Recherche dichotomique en Java 17 - O(log n)
public class Dicho {
    public static int rechercher(int[] tab, int x) {
        int g = 0, d = tab.length - 1;
        while (g <= d) {
            int m = g + (d - g) / 2; // evite overflow int
            if (tab[m] == x) return m;
            if (tab[m] < x) g = m + 1;
            else d = m - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] t = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(rechercher(t, 7));  // 3
    }
}

# Fibonacci naif - O(2^n) - inutilisable au-dela de n=35
def fib_naif(n):
    if n < 2:
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

# Fibonacci memoise - O(n) en temps, O(n) en espace
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Iteratif - O(n) en temps, O(1) en espace (optimal)
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(100))  # 354224848179261915075

<?php
// Pattern Observer (GoF, 1994) - PHP 8 avec types stricts
declare(strict_types=1);

interface Observer {
    public function notifier(string $event): void;
}

class Sujet {
    /** @var Observer[] */
    private array $observers = [];

    public function attacher(Observer $o): void {
        $this->observers[] = $o;
    }

    public function diffuser(string $event): void {
        foreach ($this->observers as $o) {
            $o->notifier($event);
        }
    }
}

class Logger implements Observer {
    public function notifier(string $event): void {
        echo "[LOG] " . $event . PHP_EOL;
    }
}

$sujet = new Sujet();
$sujet->attacher(new Logger());
$sujet->diffuser("Utilisateur connecte");
// [LOG] Utilisateur connecte

6. Programmation orientée objet (POO) — 4 piliers

Les 4 piliers de la POO :

1. Encapsulation — visibilité private / protected / public. Cacher les détails internes.
2. Héritage — relation « est-un » (extends en Java, : en Python, extends en PHP). Réutiliser le comportement parent.
3. Polymorphisme — méthodes redéfinies (override), surcharge (overload), méthodes virtuelles. Un même appel peut produire des comportements différents.
4. Abstraction — classes abstract, interfaces. Exposer un contrat sans dévoiler l'implémentation.

Les 23 design patterns GoF (Gamma, Helm, Johnson, Vlissides, « Design Patterns », Addison-Wesley, 1994) sont étudiés en S4. Les 5 patrons incontournables BUT :

7. Pièges fréquents et erreurs à éviter

# MAUVAIS : la liste par defaut est partagee entre TOUS les appels
def ajouter(elem, lst=[]):
    lst.append(elem)
    return lst

print(ajouter(1))  # [1]
print(ajouter(2))  # [1, 2]  <-- inattendu !

# BON
def ajouter(elem, lst=None):
    if lst is None:
        lst = []
    lst.append(elem)
    return lst

# dicho(tab, x) -> O(log n) en temps, O(1) en espace.
# Precondition : tab trie en ordre croissant.
def dicho(tab, x): ...

8. Mini-quiz prose intégré (3 QCM corrigés en fin de section)

1. Question 1 : Quelle est la complexité asymptotique d'une recherche dichotomique dans un tableau trié de n éléments ?
   (a) O(1) — (b) O(log n) — (c) O(n) — (d) O(n²)
2. Question 2 : Lequel de ces 4 piliers POO permet à une sous-classe de redéfinir une méthode de la classe parente ?
   (a) Encapsulation — (b) Héritage — (c) Polymorphisme — (d) Abstraction
3. Question 3 : Quel pattern GoF garantit qu'une classe ne sera instanciée qu'une seule fois dans toute l'application ?
   (a) Factory — (b) Observer — (c) Strategy — (d) Singleton

Correctifs : 1=b (log₂ n comparaisons max) ; 2=c (polymorphisme = override) ; 3=d (Singleton, Gang of Four 1994).

9. Synthèse — 10 points-clés à retenir

• 4 langages obligatoires : Python (S1), Java (S2), JavaScript (S2), SQL (S1). PHP/C selon parcours.
• Böhm-Jacopini 1966 : toute fonction calculable = séquence + sélection + itération.
• Complexité O : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
• Tri optimal comparatif : O(n log n) (borne de Shannon). Plus rapide impossible sans hypothèses.
• Structures linéaires : tableau (O(1) accès), pile LIFO, file FIFO, hash map O(1) moyen.
• Structures hiérarchiques : BST/AVL O(log n), tas (file priorité), trie (autocomplétion).
• Graphes : DFS (pile), BFS (file), Dijkstra (plus court chemin), Kruskal/Prim (MST).
• 4 piliers POO : encapsulation, héritage, polymorphisme, abstraction.
• Gang of Four 1994 : 23 design patterns. Top 5 BUT : Singleton, Factory, Observer, Strategy, MVC.
• Mémoïsation = recette anti-récursion explosive : Fibonacci passe de O(2ⁿ) à O(n).

10. Pour aller plus loin

• Tutoriel Python officiel (Python Software Foundation)
• Documentation Java SE 17 LTS (Oracle)
• Référence JavaScript — MDN Web Docs (Mozilla)
• Manuel PHP officiel
• LeetCode — entraînement entretiens techniques
• Livre de référence : Cormen T., Leiserson C., Rivest R., Stein C., « Introduction to Algorithms (CLRS) — 4th ed. », MIT Press, 2022 — la bible mondiale.
• Livre de référence : Knuth D., « The Art of Computer Programming (TAOCP) vol. 1-4A », Addison-Wesley — fondation théorique de l'algorithmique.
• Livre de référence : Gamma E., Helm R., Johnson R., Vlissides J., « Design Patterns: Elements of Reusable Object-Oriented Software », Addison-Wesley, 1994 — 23 patrons GoF.
• Livre de référence : Bloch J., « Effective Java — 3rd edition », Addison-Wesley, 2018 — 90 bonnes pratiques Java.