Solution du TD1 : Calculabilité et Complexité
Exercice 1 : Machines de Turing et décidabilité
1. Définition formelle d'une machine de Turing
Une machine de Turing est définie par :
o M=(Q,Σ,Γ,δ,q0,qaccept,qreject)
où :
▪ Q est un ensemble fini d’états.
▪ Σ\Sigma est l’alphabet d’entrée.
▪ Γ\Gamma est l’alphabet du ruban (Σ⊆Γ).
▪ δ:Q×Γ→Q×Γ×{L,R} est la fonction de transition.
▪ q0 est l’état initial.
▪ qacceptq_est l’état d’acceptation.
▪ qrejectq_ est l’état de rejet.
2. Machine de Turing pour reconnaître les chaînes contenant un nombre pair de 1
o États :
▪ q0: nombre pair de 1.
▪ q1: nombre impair de 1.
o Transitions :
▪ Si q0 lit 1, passer à q1.
▪ Si q1 lit 1, revenir à q0.
▪ Si on atteint un blanc (#) dans q0, on accepte. Sinon, on rejette.
3. Pourquoi la machine de Turing ne peut pas décider le problème de l'arrêt ?
o Le problème de l’arrêt consiste à savoir si une machine de Turing s’arrêtera
sur une entrée donnée.
o Turing a prouvé qu’il est indécidable car une telle machine entraînerait un
paradoxe logique (réduction à l’auto-référence).
Exercice 2 : Machine de Turing pour la copie d’une chaîne
1. Définition de la machine
o Entrée : Une chaîne binaire w sur le ruban.
o Sortie : w#w (où # est un délimiteur).
2. Fonction de transition
o Lire un symbole et l’écrire dans la partie droite après #.
o Continuer jusqu’à la fin du mot et s’arrêter dans qaccept
3. Exécution pour w=101
o Initialement : 101#_____
o Étapes successives :
▪ Lire 1, écrire après #, avancer.
▪ Lire 0, écrire après #, avancer.
▪ Lire 1, écrire après #, s’arrêter.
Exercice 3 : Problème du sac à dos (10 kg, 3 objets)
1. Résolution par méthode gloutonne
o Trier les objets par valeur/poids décroissante :
▪ Objet 3 (7.0) → Objet 2 (6.67) → Objet 1 (5.0).
o Sélectionner en premier l’objet 3 (2 kg), puis l’objet 2 (3 kg).
o Total : 2 + 3 = 5 kg (dépasse la capacité !).
2. Solution optimale (force brute)
o Explorer toutes les combinaisons possibles et choisir celle qui maximise la
valeur sans dépasser 10 kg.
o Solution optimale : Objet 1 + Objet 2 (9 kg, valeur = 50).
3. Vérification et complexité
o Vérifier une solution : additionner les poids et vérifier s’ils sont ≤ 10.
o Complexité : Glouton = O(nlogn), Force Brute = O(2^n).
Exercice 4 : Classes de Complexité
1. P ⊆ NP
o Si un problème est en P, il peut être résolu en temps polynomial.
o Si on peut résoudre un problème, alors on peut vérifier une solution en temps
polynomial → il est donc dans NP.
2. Exemple de problème NP-complet
o Problème SAT (Satisfiabilité booléenne) : vérifie si une formule logique est
satisfiable.
o Il est NP (une solution peut être vérifiée en temps polynomial) et NP-difficile
(tous les problèmes NP peuvent s’y réduire).
3. Pourquoi PTri appartient à P ?
o Vérifier si une liste est triée prend O(n) en la parcourant une seule fois.
o Algorithme : Comparer chaque élément avec le suivant.
Exercice 5 : Réductions entre Problèmes
1. Réduction polynomiale
o Transformer un problème en un autre en temps polynomial.
o Ex : SAT → 3-SAT en transformant chaque clause en 3 littéraux.
2. TSP est NP-complet
o Vérifier un chemin proposé prend O(n) (donc NP).
o Il peut être réduit à d’autres problèmes NP-difficiles (ex : cycle Hamiltonien).
Exercice 6 : Sac à dos (15 kg, 5 objets)
1. Génération des combinaisons
o Générer toutes les combinaisons possibles des objets.
o Vérifier celles qui respectent la contrainte de poids.
2. Approche gloutonne
o Trier par valeur/poids décroissante.
o Sélectionner les objets jusqu’à atteindre 15 kg.
3. Solution optimale (programmation dynamique)
o Remplir un tableau V[i,w] où i représente les objets et w le poids maximal.
o Complexité : O(nW), pseudo-polynomial.
Exercice 7 : Complexité Temporelle et Spatiale
1. Définitions formelles des classes de complexité
o P (Polynomial Time) : Ensemble des problèmes de décision qui peuvent être
résolus en temps polynomial par une machine de Turing déterministe.
o NP (Nondeterministic Polynomial Time) : Ensemble des problèmes de
décision pour lesquels une solution peut être vérifiée en temps polynomial par
une machine de Turing déterministe.
o PSPACE (Polynomial Space) : Ensemble des problèmes de décision qui
peuvent être résolus en espace polynomial par une machine de Turing
déterministe.
o EXP (Exponential Time) : Ensemble des problèmes qui peuvent être résolus
en temps exponentiel par une machine de Turing déterministe.
2. Un problème résoluble en temps polynomial est aussi résoluble en espace
polynomial
o Si un algorithme fonctionne en temps polynomial, cela signifie que le nombre
total d'étapes d'exécution est borné par une fonction polynomiale de la taille de
l'entrée : T(n) = O(nk) .
o L'espace utilisé est au plus proportionnel au nombre d'étapes effectuées.
o Ainsi, un algorithme qui tourne en temps polynomial ne peut utiliser qu'un
espace polynomial, ce qui implique que P ⊆ PSPACE.
3. Calcul du produit matriciel et analyse de la complexité
o Algorithme naïf : Multiplication standard de deux matrices et de taille nxn .
o for i from 0 to n-1:
o for j from 0 to n-1:
o C[i][j] = 0
o for k from 0 to n-1:
C[i][j] += A[i][k] * B[k][j]
Complexité : O(n3)
o Algorithme optimisé : Algorithme de Strassen (diviser-pour-régner)
▪ Décompose les matrices en sous-matrices et utilise 7 multiplications
récursives au lieu de 8.
▪ Complexité : O(n 2 ) O(n
log 7 2.81
)
Exercice 8 : Étude de Cas
1. Modélisation du problème
o Entrées:
▪ Liste des destinations avec leurs demandes en marchandises.
▪ Contraintes de poids et de volume des véhicules.
▪ Distance et coût entre chaque point.
o Sortie :
▪ Un itinéraire optimisé minimisant le coût ou le temps d'acheminement.
o Modèle mathématique :
▪ Si le problème s'apparente au voyageur de commerce (TSP) : minimiser
la distance totale.
▪ Si le problème s'apparente au sac à dos : maximiser la valeur
transportée sous contrainte de capacité.
2. Algorithmes utilisés
o Approche exacte :
▪ Programmation dynamique (Bellman-Held-Karp pour TSP : ).
O(n2.2n)
▪ Branch and Bound.
o Approche heuristique :
Algorithmes gloutons (plus proche voisin pour TSP : ) O(n2).
▪Algorithmes métaheuristiques (recuit simulé, algorithmes génétiques,
optimisation par essaim de particules).
3. Comparaison entre approche exacte et heuristique
o Approche exacte :
▪ Trouve la solution optimale.
▪ Temps d'exécution très long pour de grands problèmes.
o Approche heuristique :
▪ Produit une solution approchée en un temps raisonnable.
▪ Peut ne pas garantir l'optimalité, mais donne des résultats satisfaisants
en pratique.
