Python et Algorithmique

1) 🧠 Python & Algorithmique

• S.D.D

  • Liste : L = [1, 2, 3]
    • Accès : L[i]
    • Parcours :
      • for x in L :
      • for i in range(len(L)) :
  • Dictionnaire : d = {'a':1, 'b':2}
    • Clés : for k in d :
    • Valeurs : for v in d.values() :
    • Couples : for k,v in d.items() :

• Piles & Files

  • Piles (LIFO)
    • Avec liste python :
      Empiler : pile.append(x)
      Dépiler : x = pile.pop()
  • Files (FIFO)
    from collections import import deque
file = deque
file.append(x) ← enfiler
    x = file.popleft() ← défiler
    ajoute à la fin, retire en tête

• Quand utiliser quoi ?

  • Besoin de revenir en arrière (historique, annuler)
    → Pile
  • Ordre d'arrivée (file d'attente)
    → File

• Récursivité

def f(n) :
    if condition_base :
        return ...
    else :
        return f(n-1) ...

• À savoir faire :
  • Identifier la condition d'arrêt
  • Compter le nb d'appels (C ~) :
    • si on entre 1 à chaque fois → n appel
    • si on coupe n en 2 à chaque fois → log n appel
    • si on a 2 appel récursifs par appel → souvent exp.

2) 📊 Complexité & Tri

• Ordre grandeur à connaître

  • O(1) : temps constant → accès tab[i], dico["clé"]
  • O(n) : 1 boucle simple sur n éléments
  • O(n²) : 2 boucles imbriquées
  • O(log n) : tri fusion, tri rapide (en moyenne)

• Tri classiques

  • Tri par insertion : Idéal pour tableau presque trié
    Moyenne et pire cas : O(n²), meilleur cas (déjà trié) : O(n)
  • Tri par sélection
    Toujours O(n²) (on cherche min, on échange)
  • Tri fusion : Découpage en 2 + fusion triée
    O(n log n), stable

3) 🌳 Arbre Binaire & ABR

• Définition :
  Chaque nœud a au plus 2 enfants (gauche, droite)

• Arbre Binaire de Recherche :

  • sous-arbre G : val < racine
  • sous-arbre D : val > racine

• Parcours

  • Préfixe : Racine - Gauche - Droite
  • Infixe : Gauche - Racine - Droite
  • Suffixe : Gauche - Droite - Racine

• Taille = nb total de nœuds

• Hauteur = longueur du plus long chemin racine → feuille (nb d'arêtes ou de niveau selon énoncé)

• Notions

  • Racine : le sommet de l'arbre
  • Feuille : un nœud sans fils
  • Nœuds intern. : les nœuds qui sont ni la racine ni les feuilles
  • Arêtes : un lien entre 2 nœuds
  • Branche : une suite de nœuds consécutifs de la racine vers une feuille
  • Arité : nb maximal d'enfants qu'un nœud peut avoir
  • Taille : nb total de nœuds de l'arbre
  • Hauteur : nb de nœuds de la branche la plus longue
  • Profondeur / niveau : nb de nœuds sur le chemin de la racine à un nœud donné

• Implémentation Arbres Binaires

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

    def taille(a):
        if a is None:
            return 0
        return 1 + taille(a.gauche) + taille(a.droite)

    def hauteur(a):
        if a is None:
            return 0
        else:
            return 1 + max(hauteur(a.gauche), hauteur(a.droite))

    def parcours_prefixe(a):
        if a is None:
            return []
        return [a.valeur] + parcours_prefixe(a.gauche) + parcours_prefixe(a.droite)

    def parcours_infixe(a):
        if a is None:
            return []
        return parcours_infixe(a.gauche) + [a.valeur] + parcours_infixe(a.droite)

    def parcours_suffixe(a):
        if a is None:
            return []
        return parcours_suffixe(a.gauche) + parcours_suffixe(a.droite) + [a.valeur]

• Pour un ABR, obtenir les valeurs triées = parcours infixe G-R-D

4) Graphes, BFS/DFS

• Un nœud → 2 enfants : g, d
• Feuille : nœud sans enfants → sous-arbre g/d
• Racine : nœud du départ

5) SQL & BDD

• Requête générale

SELECT colonne
FROM table1
JOIN table2 ON table1.cle = table2.cle
WHERE condition
GROUP BY ...
HAVING ...
ORDER BY colonne ASC/DESC;

• Opérations courantes :

  • Sélection :
    SELECT * FROM Eleves WHERE age > 17;
  • Projection (certaines colonnes) :
    SELECT nom, prenom FROM Eleves;
  • Tri :
    SELECT * FROM Eleves ORDER BY nom ASC;

• Insertion
  INSERT INTO Eleves (nom, prenom, age) VALUES ("Dupont", "Paul", 17);

• Mise à jour
  UPDATE Eleves SET age = 18 WHERE nom = "Dupont";

• Suppression
  DELETE FROM Eleves WHERE id = 3;

• Jointure classique

  SELECT Eleves.nom, Classes.nom
  FROM Eleves
  JOIN Classes ON Eleves.id_classe = Classes.id;
  

• Requêtes d'agrégat

  SELECT COUNT(*) FROM Eleves;
  SELECT AVG(montant) FROM Eleves;
  SELECT MIN(age) FROM Eleves;
  

6) Réseaux & Architecture

• Modèle (simplifié)

  • IP : adresse logique machine
  • TCP : protocole fiable, connexion, garantit l'ordre
  • UDP : plus rapide, pas de garantie (vidéo, jeux)

• Routage : RIP vs OSPF

  • RIP : choisit le chemin avec le moins de sauts (routeurs)
  • OSPF :
    • utilise un coût = 10^8 / bande passante (bits/s)
    • on additionne les coûts sur chaque lien
    • meilleur chemin = coût total minimal

• Processus / Système

  • États d'un processus :
    • prêt : attend d'être exécuté
    • élu : en cours d'exécution
    • bloqué : attend 1 ressource (I/O, verrou...)
  • Interblocage (deadlock) :
    2 processus se bloquent mutuellement en attendant une ressource détenue par l'autre

7) Représentation de l'information

• 7.1 Binaire

  • Base 2
    • 1 bit : 0 ou 1
    • 1 octet : 8 bits
  • Ex : binaire → décimal : 10₁₀ = 1×2³ + 1×2¹ + 0 = 11
  • décimal → binaire : division par 2

• 7.2 Entiers signés (complément à deux)

  • Bit de poids fort = signe (1 = nég)
  • Pour inverser un signe : inversion des bits + 1

• 7.3 Images (bases)

  • Représentées par une grille de pixels
  • Chaque pixel a une couleur codée (souvent 24 bits : 8 bits par canal R, G, B)
  • Taille du fichier ≈ largeur × hauteur × bits par pixel

• 7.4 Mémoire

  • RAM : volatile, rapide
    • contient les pgm en cours d'exécution & leurs données
  • Mémoire de masse (disque dur, SSD) :
    • non volatile, plus lente
    • stockage permanent

• 7.5 Concepts

  • Base de données relationnelle : ensemble de tables
  • Une table : lignes (enregistrements) × colonnes (attributs)
  • Clé primaire (PK) : identifiant unique d'une ligne (valeurs uniques, pas null)
  • Clé étrangère (FK) : référence à une clé primaire d'une autre table (assure le lien entre tables)

• Questions fréquentes

  • Pourquoi X ne peut pas être PK ?
  • Car X n'est pas unique / doublons possibles / peut être null

8) Logique à circuits

• 8.1 Logique booléenne
  • Valeurs → True / False
  • Opérateurs :
    • not A
    • A and B
    • A or B

9) Réseaux & Internet

• 9.1 Modèles en couches

  • Modèles TCP/IP simplifié :
    • Application (HTTP, DNS)
    • Transport (TCP, UDP)
    • Internet (IP)
    • Accès réseau (Ethernet, Wi-Fi)

• 9.2 Adresse IP

  • IPv4 : 32 bits, écrite sous forme décimale pointée : 192.168.1.16
  • Sépare réseau / machine grâce au masque (ex : /24 → 255.255.255.0)

• 9.3 Routeur & DNS

  • Routeur : relie plusieurs réseaux
    • choisit le chemin pour les paquets
  • DNS : correspondance nom de domaine ↔ adresse IP
    • www.exemple.com → 93.184.216.34

• 9.4 TCP vs UDP

  • TCP :
    • orienté connexion
    • fiable (contrôle erreur, accusés ou réception)
    • plus lent
    • Ex : HTTP(s), mail
  • UDP :
    • sans connexion
    • rapide, moins fiable
    • Ex : streaming, jeux en ligne

10) P.O.O.

• Héritage
  Permet de créer une classe qui hérite d'une autre
  Ex :

class Animal :
    def __init__(self, nom):
        self.nom = nom

    def parler(self):
        return "..."

class Chien(Animal):
    def parler(self):
        return "Wouf"

• Récapitulatif SQL & BDD
  • A1. Clé primaire (PK) : attribut(s) qui identifie(nt) de façon unique chaque ligne (valeurs uniques, pas null)
  • Clé étrangère (FK) : attribut qui référence la PK d'une autre table (assure le lien entre tables)
  • A2. SELECT / WHERE

SELECT col1, col2
FROM table
WHERE condition1 AND condition2;

Ex :

SELECT nom, prenom FROM Clients WHERE ville = "Paris";
SELECT * FROM emprunt WHERE dateRendu IS NULL;

• A3. ORDER BY (tri)

SELECT ...
FROM ...
ORDER BY col1 ASC; -- croissant
ORDER BY col4 DESC; -- décroissant

• A4. COUNT / DISCOUNT (compter)

SELECT COUNT(*) FROM table;
SELECT COUNT(DISTINCT col) FROM table;

• A5. JOIN
  Quand on veut des infos dans 2 tables :

SELECT c.nom, c.prenom
FROM Clients c
JOIN Commandes co ON c.id = co.id;
WHERE co.date = "30/04/2021";

• A6. INSERT

INSERT INTO table (col1, col2) VALUES (v1, v2);

• A8. DELETE

DELETE FROM table WHERE condition;

B) Réseaux (RIP / OSPF / IP)

• B1. RIP (Routing Information Protocol)

  • Métrique = nbr de sauts (routeurs traversés)
  • Le "meilleur" chemin = moins routeurs

• B2. OSPF

  • Minimise le coût total (somme des coûts des liaisons)
  • Souvent on a une formule : coût = constante / débit
  • Débit plus faible → coût plus grand
  • Calcul du coût :
    • Calculer le coût
    • Additionner les coûts d'un chemin
    • Choisir le plus petit total

Linux

• Les droits / catégories des utilisateurs :

  • u → user
  • g → group
  • o → other (users)
  • a → all
  • r → read
  • w → write
  • x → execute

• Les commandes :

  • cd : changer de répertoire courant
  • mkdir : créer un répertoire
  • ls : lister
  • pwd : afficher le chemin absolu (de la racine → rep.)
  • cp : copier + fichier rep.
  • touch : créer + fichier vide
  • chmod : changer rm = supprimer / rep. = répertoire
  • rm : supprimer fichier ou répertoire (rm -r)

Autres

• Liste en extension

Lz = [42, 10, 25, 10, 70, 73, 17]
            0   1   2   3   4   5   6
print(type(L))
liste
print(L[3])
10
print(len(L))
7

• Append ← ajoute à la fin de la liste

• Pop(0) ← enlève le terme de rang 0

• Remove(17) ← enlève tous les éléments égaux à 17

• [3] ← 100 ← remplace le terme de rang 3

• Parcours de liste

  • for i in range(len(L)) :
    → parcours avec les indices
  • for item in L :
    → parcours avec les éléments (direct)

Fonctions Python (extraits)

def recherche(L,e):
    for i in range(len(L)):
        if L[i] == e:
            return True
    return False

def recherche(L,e):
    for item in e:
        if item == e:
            return True
    return False

def minimum(L):
    min = L[0]
    for i in range(1,len(L)):
        if L[i] < min:
            min = L[i]
    return min

def maximum(L):
    max = L[0]
    for i in range(1,len(L)):
        if L[i] > max:
            max = L[i]
    return max

def somme(L):
    s = 0
    for i in range(len(L)):
        s = s + L[i]
    return s

def moyenne(L):
    s = 0
    for i in range(len(L)):
        s = s + L[i]
    m = s / len(L)
    return m