Programmation & Algorithmique

Sommaire du Cours

1. Complexite Algorithmique

La complexite algorithmique mesure les ressources (temps, memoire) consommees par un algorithme en fonction de la taille $n$ de l'entree. On utilise les notations asymptotiques pour decrire le comportement quand $n \to \infty$.

1.1 Notations Asymptotiques

1.2 Classes de Complexite – Echelle

1.3 Regles de Calcul

2. Recursivite

Une fonction recursive s'appelle elle-meme. Elle doit avoir un cas de base (condition d'arret) et un cas recursif (appel sur un sous-probleme plus petit).

2.1 Factorielle

def factorielle(n):
    # Cas de base
    if n <= 1:
        return 1
    # Cas recursif
    return n * factorielle(n - 1)

Complexite : $O(n)$ – $n$ appels recursifs, $O(1)$ par appel.

2.2 Suite de Fibonacci

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Complexite naive : $O(2^n)$ – explosion exponentielle ! Avec memoisation : $O(n)$.

2.3 Tours de Hanoi

def hanoi(n, depart, arrivee, auxiliaire):
    if n == 1:
        print(f"Deplacer disque 1 de {depart} vers {arrivee}")
        return
    hanoi(n - 1, depart, auxiliaire, arrivee)
    print(f"Deplacer disque {n} de {depart} vers {arrivee}")
    hanoi(n - 1, auxiliaire, arrivee, depart)

Complexite : $O(2^n)$ – $2^n - 1$ deplacements. Pour $n=64$ disques, c'est environ 585 milliards d'annees !

3. Structures de Donnees

Une structure de donnees organise et stocke les donnees pour un acces et une modification efficaces. Le choix de la structure impacte directement la performance des algorithmes.

3.1 Comparatif des Structures Fondamentales

* Moyennes ; cas pire : ABR non equilibre → $O(n)$, table de hachage avec collisions → $O(n)$.

3.2 Pile et File – Principe LIFO / FIFO

3.3 Arbre Binaire de Recherche (ABR / BST)

3.4 Table de Hachage

4. Algorithmes de Tri

Trier est l'une des operations les plus fondamentales en informatique. Voici les 4 algorithmes incontournables, du plus simple au plus efficace.

4.1 Tableau Comparatif des Tris

5. Tableaux et Chaines de Caracteres

Manipuler efficacement tableaux et chaines est essentiel. Voici les techniques classiques et la recherche de motifs.

5.1 Techniques Classiques sur Tableaux

5.2 Recherche de Motifs (Pattern Matching)

6. Exercices Corriges

Mets en pratique les concepts avec ces 4 exercices, du niveau debutant a avance.

def mystere(arr, n):
    for i in range(n):
        j = 1
        while j < n:
            print(arr[i] * j)
            j = j * 2

def somme_chiffres(n):
    # Cas de base : un seul chiffre
    if n < 10:
        return n
    # Dernier chiffre + appel sur le reste
    return (n % 10) + somme_chiffres(n // 10)