16 — Projet Fil-Rouge : Cours complet

Niveau : Université + Industrie — Durée : ~16h de projet Objectif : construire "RecoRoute", une plateforme de recommandation et de routage qui combine les algorithmes du cours.

---

Partie I — Le cahier des charges

1.1 Énoncé

RecoRoute est une application qui aide des utilisateurs à :

1. trouver les plus courts chemins dans un réseau de villes (routes) ;
2. découvrir des amis et contenus recommandés dans un réseau social ;
3. rechercher des lieux/événements par mots-clés ;
4. planifier des tournées de livraison (scheduling).

Le tout via une CLI et une API REST, avec des données synthétiques générées.

1.2 Les données

• Réseau routier : graphe pondéré (nœuds = villes, arêtes = routes à coût).
• Réseau social : graphe non pondéré (nœuds = personnes, arêtes = amitiés), chaque personne a des tags (centres d'intérêt).
• Événements/lieux : enregistrements textuels (nom, description, tags).
• Commandes de livraison : (destination, deadline, profit).

---

Partie II — Algorithmes mobilisés (tous les chapitres !)

Diagramme en cours de génération...

---

Partie III — Module Graphes (réseau social)

3.1 Plus courts chemins en BFS (grappe non pondérée)

Degré de séparation : dist(u, v) = plus court chemin non pondéré.

from collections import deque

def bfs_shortest_paths(adj, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

3.2 Composantes connexes

def connected_components(adj):
    seen = set()
    components = []
    for start in adj:
        if start in seen: continue
        comp, q = set(), deque([start])
        seen.add(start)
        while q:
            u = q.popleft()
            comp.add(u)
            for v in adj[u]:
                if v not in seen:
                    seen.add(v); q.append(v)
        components.append(comp)
    return components

3.3 Métriques

• Distribution des degrés.
• Taille de la plus grande composante connexe.
• Diamètre approché (échantillonnage BFS).

---

Partie IV — Module Recherche

4.1 Index par hash tables

Chaque terme → liste de documents (inverted index).

from collections import defaultdict

class InvertedIndex:
    def __init__(self):
        self.index = defaultdict(list)   # terme -> [ids de docs]

    def add(self, doc_id, text):
        for token in text.lower().split():
            if doc_id not in self.index[token]:
                self.index[token].append(doc_id)

    def search(self, query):
        terms = query.lower().split()
        if not terms:
            return []
        hits = set(self.index.get(terms[0], []))
        for term in terms[1:]:
            hits &= set(self.index.get(term, []))
        return sorted(hits)

4.2 Autocomplétion par Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def autocomplete(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children: return []
            node = node.children[ch]
        res = []
        def walk(n, w):
            if n.is_end: res.append(w)
            for c, k in n.children.items():
                walk(k, w + c)
        walk(node, prefix)
        return res[:10]

4.3 String matching (KMP) pour la recherche floue de sous-chaînes

Permet de retrouver un lieu même quand l'utilisateur tape une sous-chaîne du nom.

---

Partie V — Module Pathfinding

5.1 Dijkstra (routes pondérées)

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

5.2 A* (avec heuristique géographique)

Si les nœuds ont des coordonnées, utiliser la distance euclidienne comme heuristique admissible (≤ coût réel) :

def astar(graph, start, goal, heuristic):
    open_set = [(heuristic(start, goal), 0, start)]
    g = {start: 0}
    while open_set:
        _, cost, u = heapq.heappop(open_set)
        if u == goal:
            return cost
        for v, w in graph[u]:
            ng = cost + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(open_set, (ng + heuristic(v, goal), ng, v))
    return float("inf")

5.3 Comparaison

---

Partie VI — Module Scheduling

6.1 Ordonnancement greedy (profit, deadline)

Planifier les livraisons pour maximiser le profit (chapitre 11) :

def schedule_greedy(jobs):   # jobs: [(profit, deadline)]
    jobs.sort(reverse=True)
    max_d = max(d for _, d in jobs)
    parent = list(range(max_d + 2))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    total = 0
    for p, d in jobs:
        slot = find(min(d, max_d))
        if slot > 0:
            total += p
            parent[slot] = find(slot - 1)
    return total

6.2 DP knapsack (capacité = temps total)

Variante : si chaque livraison "pèse" un temps de préparation, on résout par DP (chapitre 10).

6.3 Choix greedy vs DP

• Si deadline + unité de temps → greedy optimal (job scheduling).
• Si un poids variable (temps de préparation) → knapsack 0/1 → DP.

---

Partie VII — Module Recommandation

7.1 Cosine similarity

Représenter chaque utilisateur par un vecteur de tags (1 si intéressé). La similarité cosinus :

import math

def cosine(a, b):
    num = sum(x * y for x, y in zip(a, b))
    da = math.sqrt(sum(x * x for x in a))
    db = math.sqrt(sum(y * y for y in b))
    if da == 0 or db == 0:
        return 0.0
    return num / (da * db)

7.2 Recommandation par similarité

recommend(user, users) : pour chaque autre utilisateur, score = cosine ; top-k des tags absents de l'utilisateur, pondérés par la similarité.

7.3 Collaborative filtering (moyenne pondérée)

Évaluations d'items (notes 1-5) : prédire la note d'un item pour un utilisateur comme la moyenne pondérée des notes des utilisateurs les plus similaires (corrélation de Pearson ou cosinus sur les notes).

def predict(user, item, ratings, sim):
    num = den = 0.0
    for other in ratings:
        if other == user or item not in ratings[other]:
            continue
        s = sim(user, other)
        num += s * ratings[other][item]
        den += s
    return num / den if den else ratings[user].get(item, 3.0)

---

Partie VIII — Architecture CLI + API

8.1 Couches

┌───────────────────────────────────────────────┐
│  CLI (argparse/click)      API (FastAPI/Express)│
├───────────────────────────────────────────────┤
│  Services (GraphService, SearchService, ...)   │
├───────────────────────────────────────────────┤
│  Algorithms (bfs, dijkstra, trie, dp, cosinus) │
├───────────────────────────────────────────────┤
│  Data (générateur synthétique, loaders)        │
└───────────────────────────────────────────────┘

8.2 CLI (exemples de commandes)

reco route --from Paris --to Nice --algo astar
reco social --friendsof Alice
reco search "restaurant italien"
reco recommend --user 42 --k 5
reco schedule deliveries.csv
reco bench --size 10000

8.3 API REST (FastAPI en Python)

8.4 Data layer

Générateur synthétique : villes sur une grille (coût = distance), utilisateurs avec tags aléatoires, livraisons aléatoires. Seed fixe pour reproductibilité.

---

Partie IX — Tests et benchmarks

9.1 Tests

• Unitaires : chaque algorithme validé sur des cas connus.
• Oracle croisé : BFS vs Dijkstra (poids 1), greedy vs DP (petites instances), cosine vs numpy.
• Propriétés : A* ≤ Dijkstra sur graphes géographiques ; recommandation top-k stable avec la seed.

9.2 Benchmarks

9.3 Outils

• Python : timeit, cProfile, pytest, pytest-benchmark.
• HTML report : tableaux de résultats générés par script.

---

Partie X — Multi-langages

La même spec est implémentée dans plusieurs langages :

Convention : mêmes noms de fichiers/commandes (bfs.py, bfs.ts, BFS.java, bfs.go, bfs.cpp), mêmes fixtures de tests → validation croisée par fichiers d'oracle.

---

Partie XI — Documentation et livrables

11.1 Livrables attendus

1. Code source multi-langages (au moins 2 langages complets).
2. Tests : suite verte (pytest + équivalents).
3. Benchmarks : rapport HTML + analyse.
4. Documentation : README d'installation, guide d'usage CLI/API.
5. ADRs : les décisions d'architecture.
6. Diagrammes : Mermaid de l'architecture et du flux de données.

11.2 Critères de qualité

• Séparation stricte Data / Algorithms / Services.
• Aucun algorithme "réinventé" : réutiliser les implémentations des chapitres.
• Reproductibilité : seed fixe, versions documentées.
• Complexités justifiées dans la doc (avec références aux chapitres).

---

Check-list de maîtrise

• Je sais intégrer 10+ algorithmes dans une architecture propre.
• Je sais structurer CLI + API + services + data.
• Je sais écrire des tests d'oracle croisés.
• Je sais mesurer et comparer des algorithmes (benchmarks).
• Je sais documenter (ADR, diagrammes, README).
• Je sais porter la même spec dans plusieurs langages.