8INF806

Conception et analyse des algorithmes

Cour 1

Rappels

• Alphabet: A

• Mot: w A*

• Langage: L A*

• Problème de décision:

– Entrée: w

– Sortie: 1 si wL, 0 sinon

• Langage = Probleme de décision

Problèmes

On est intéressé par les problèmes satisfaisant les deux conditions suivantes:

1. Doit pouvoir se résoudre sur un ordinateur: Par exemple le problème de trouver une juste sentence pour une personne reconnu coupable d'un délit fait appel à des considérations culturelles et philosophiques et ne peut donc pas être résolu par un ordinateur.

2. L'ensemble des solutions correctes doit être non ambiguë: Par exemple la traduction d'un texte de l'anglais au français peut être réalisée par un ordinateur mais il n'est pas clair ce que l'on doit considérer comme une traduction correcte.

Problèmes algorithmiques

Un problème algorithmique est défini par:

1. La description de l'ensemble des entrées possibles (chaque entrée est une séquence finie de caractères).

2. La description d'une fonction qui associe à chaque entrée un ensemble de résultats corrects (chaque résultat est aussi une séquence finie de caractères)

Exemples: Accessibilité dans un graphe

Entrée: Un graphe G et deux noeuds a et b

Résultat:

• Problème de recherche: On cherche un chemin de a à b.

• Problème de décision: On veut savoir s'il existe un chemin de a à b

• Problème d'optimisation: On veut un plus court chemin de a à b

• Problème d'évaluation: On veut la longueur du plus court chemin de a à b

Choix d'un modèle de calcul

On veut exprimer nos algorithmes à l'aide d'un langage simple mais universel.

– Simple: Petit ensemble d'instructions facilement analysable.

– Universel: Même puissance qu'un programme en C.

Temps d'exécution d'un algorithme

Le temps d'exécution d'un algorithme dépend de:

1. L'entrée

2. Le choix de l'ordinateur

3. Le choix du langage de programmation

4. L'implémentation

Remarque: On veut une notion de temps d'exécution qui ne dépende que de la longueur de l'entrée.

Pseudo-C

• Opération d'assignation

• Opérations arithmétiques

• Instructions conditionelles

• Instruction d'arrêt

• Operations d'entrées/sortie

On compte le nombre d'opérations et d'instructions élémentaires (s'exécutant en temps constant).

Machine de Turing (1)

Machine de Turing (2)

M=(Q, , , , q0, F)

– Q est un ensemble fini d'états

est l'alphabet d'entrée

est l'alphabet de la machine: contient tous les symboles de , le symbole blanc, et possiblement d'autres symboles.

: Q x Q x x {-1, 0, 1} est la fonction de transition (le programme)

– F Q est l'ensemble des états finaux

Machine de Turing (3)

• Initialement les n=|w| premières cases du ruban contiennent l'entrée w et toutes les autres cases contiennent le symbole blanc.

• La tête de lecture est placée au début du ruban.

• La machine exécute la suite de transitions indiquées par la fonction et elle s'arrête si elle atteint un état final.

• Le résultat est le contenu du ruban.

Généralisation

• Plusieurs pistes sur le ruban

• Plusieurs rubans

• Rubans infinis dans les deux directions

• Plusieurs têtes de lecture/écriture

• Multidimentionel

• Tous équivalents au modèle original

Exemples

• Échanger le contenu de deux variables

• Incrémenter ou décrémenter un compteur

• Convertir un nombre unaires/binaires

• Additioner deux entiers en binaires

• Multiplier deux entiers en binaire

• Comparer deux entiers en binaire

• Trier un tableau

Pseudo-C vs Machine de Turing

Tout ce qui peut être fait avec l'un peut être fait avec l'autre.

– Opération d'assignation

– Opérations arithmétiques

– Instructions conditionelles

– Instruction d'arrêt

– Opérations d'entrées/sortie

Thèse de Church-Turing

• Tout ce qui est calculable peut être calculé par une machine de Turing... ou par un programme en pseudo-C

• Notion intuitive d'algorithme = machine de Turing.

• On ne peut pas construire un ordinateur plus puissant qu'une machine de Turing

Ordinateurs et machines de Turing

Problème U:

Entrée: mot w et description d'une mT M

Résultat: Résultat de M sur l'entrée w

Machine de Turing universelle: Machine de Turing qui résoud le problème U.

Encodage d'une machine de Turing

• On veut encoder en binaire une machine de Turing M.

• On encode les transitions (qi,sj)=(qk, sl, dm) sous la forme: 0i10j10k10l10m

• Si C1, C2, C3, ... , Cr est une énumération des transitions

de la machine alors l'encodage binaire de M est:

111 C1 11 C2 11 ... 11 Cr 111

• On encode les machines à plusieurs ruban de façon similaire.

• L'encodage d'une machine M est dénoté <M>

Problèmes calculables

• Une fonction (ou problème) est calculable si il est calculé par une machine de Turing

• On dit qu'il est décidable s'il s'agit d'un problème de décision (ou langage).

Problèmes incalculables(Gödel 1931, Turing 1936)

Certains problèmes algorithmiques ne peuvent pas être résolus par une machine de Turing ni par aucun autre modèle de calcul

Preuve: Diagonalisation

Exemples: Le problème d'arrêt.

Théorème de la récursion(Kleene, 1952)

Dénotons par f<M>(w) la fonction calculée par la machine de Turing M.

Pour toute fonction totale et calculable g il existe une machine de Turing M telle que:

fM(w)=fg(<M>)(w) pour tout w.

Conséquence

Supposons que g est une fonction qui sur entrée w écrit en sortie la description d'une mT Mw qui ignore son entrée et écrit w en sortie.

Par le théorème de la récursion il existe une mT M telle que M et g(<M>) donne le même résultat sur toutes les entrées.

Cela signifie que M écrit sa description en sortie.

Autre conséquences

• Démontre l'existence des fonctions récursives. En particulier, on peut toujours supposer qu'une machine de Turing a accès à son propre code.

• Aucun virus ne peut affecter tous les programmes informatiques.

• Soit M1, M2, M3, ... une énumération quelconque (mais calculable) des machine de Turing

Alors il existe un indice i tel que Mi et Mi+1 calculent la même fonction.

Classes de complexité

• TIME(T(n)) = ensemble des problèmes pouvant être résolus en temps T(n).

• SPACE(S(n)) = ensemble de problèmes pouvant être résolu en temps S(n).

• 0k

k)TIME(nP

Thèse de Church-Turingétendue

Soit P un algorithme s'exécutant en temps t(n) sur un modèle de calcul R

La simulation de P sur une machine de Turing peut être réalisée en temps p(t,n) où p est un polynôme.

Temps polynomial

Nous dirons qu'un algorithme est efficace s'il fonctionne en temps polynomial.

La thèse de Church-Turing étendue implique que cette définition est indépendante du modèle de calcul utilisé.

Problèmes intraitables

Pour toute fonction calculable T(n), il existe un problème calculable P qui ne peut pas être résolu par une machine de Turing en moins de T(n) étapes

Preuve: Diagonalisation

L={xi= | Mi n'accepte pas xi en moins de T(|xi|) étapes}

En particulier, certains problèmes ne possèdent aucun algorithme efficace.

Hiérarchie temporelle(Hartmanis et Stearns, 1965)

Soit T1(n) et T2(n), deux fonctions ''raisonnables''.

Si lim alors

il existe un problème dans TIME(T2(n))-TIME(T1(n)).

Remarque: Cela implique qu'il y a une hiérarchie infinie de classes de complexité.

0)(

))(log()(

2

11 nT

nTnT

Gap Theorem(Borodin, 1972)

Pour toute fonction totale calculable g(n) il existe une fonction totale calculable T(n) telle que

TIME(T(n))=TIME(g(T(n)))

Par exemple, si g(n)=2n alors

TIME(T(n))=TIME(2T(n))

Speed-up Theorem(Blum, 1967)

Soit f(n) une fonction totale et calculable.

Il existe un problème P possédant la propriété suivante:

Si M1 est une machine de Turing résolvant P en temps T1(n) alors il existe une machine de Turing M2 résolvant P en temps T2(N) et f(T2(n))≤ T1(n) presque partout.

Exemple: Si f(n)=n2 alors

Conclusion: Certain problèmes ne possède aucun "meilleur" algorithme.

)()( 12 nTnT

Linear speed-up theorem(Hartmanis-Stearns, 1965)

Si f(w) est une fonction calculée par une mT en temps T(n) alors pour tout c>0 il existe une mT M' qui calcule f(w) en temps cT(n)+n+m.

Note: Les termes n=|w| et m=|f(w)| sont nécessaires pour lire et l'entrée et écrire la solution.

Bornes supérieures et inférieures

En général on ne peut pas déterminer précisément le temps minimal TP(n) nécessaire pour résoudre un problème P:

• Difficulté de calculer TP(n) même si on connaît un algorithme optimal

• Speed-up theorem: En général, il n'y a pas d'algorithme optimal

• Linear speed-up theorem.

• Différents résultats sur différents modèles de calcul.

On se contente donc de borner le temps d'exécution en utilisant la notation asymptotique.

Notation asymptotique

• f(n)=O(g(n)) si (similaire à )

• f(n)=(g(n)) si (similaire à )

• f(n)=o(g(n)) si (similaire à <)

• f(n)= (g(n)) si (similaire à >)

• f(n)=(g(n)) si (similaire à =)

cng

nf)(

)(lim

cng

nf)(

)(lim

0)(

)(lim

ng

nf

)(

)(lim

ng

nf

cng

nf)(

)(lim