Fiche de révision : Informatique et calculabilité

📋 Plan du Cours

1. Algorithmes et programmes
2. Machines de calcul historiques
3. Fonctions et récursion de Peano
4. Listes et accumulateurs
5. Multiplication russe binaire
6. Fonctions calculables
7. Indécidabilité du problème PCP
8. Chiffrement symétrique
9. Clés publiques et signatures

📖 1. Algorithmes et programmes

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions permettant de résoudre un problème et destinée à un lecteur humain, avec une précision qui peut rester vague.
• Programme : Algorithme écrit dans un langage compris par une machine ; il doit être correct et non ambigu.

📝 Points essentiels

• Les traducteurs comprennent notamment :
  • des assembleurs
  • des interpréteurs
  • des compilateurs

💡 Astuce mémo

L’algorithme s’adresse à l’humain, le programme à la machine.

📖 2. Machines de calcul historiques

📝 Points essentiels

• La Pascaline, créée par Blaise Pascal en 1642, effectue des additions et des soustractions.

• La machine de Leibniz, datée de 1694, était conçue pour effectuer les quatre opérations, mais ne fut pas fabriquée à l’époque.

• La machine à différences de Charles Babbage, datée de 1830, était destinée au calcul de polynômes.

• La tabulatrice de Herman Hollerith, utilisée pour le recensement américain de 1890, réalisait du comptage à 150 additions par seconde grâce à une machine électrique.

💡 Astuce mémo

Pascaline (1642) → Leibniz (1694) → Babbage (1830) → Hollerith (1890).

📖 3. Fonctions et récursion de Peano

📝 Points essentiels

• La machine de Peano manipule les entiers naturels et évalue des expressions arithmétiques au moyen de fonctions définies et appelées dans le programme.

📌 Dans la machine de Peano, ++E désigne le successeur de E, soit E+1, tandis que ––E désigne son prédécesseur et est indéterminé lorsque E vaut 0.

• L’algorithme récursif PLUS_A additionne X et Y en renvoyant Y si X=0 et, sinon, en calculant ++PLUS_A(––X,Y).

• Un programme de Peano prend une suite d’entiers en entrée et, soit s’arrête en renvoyant un entier, soit ne s’arrête pas.

💡 Astuce mémo

Le décrément de X rapproche de 0 → la condition d’arrêt finit par être atteinte.

📖 4. Listes et accumulateurs

🔑 Notions clés & Définitions

• Accumulateur : Variable qui mémorise progressivement une valeur intermédiaire au cours d’un calcul.

📝 Points essentiels

• Dans la machine de Peano 3.0, [] représente la liste vide, cons(X,L) ajoute X en tête, car(L) renvoie la tête et cdr(L) renvoie le reste ; car et cdr sont indéterminées sur une liste vide, et vide(L) renvoie 1 si L est vide et 0 sinon.

• SOMME(L) renvoie 0 si L est vide et, sinon, additionne car(L) au résultat de SOMME(cdr(L)).

• MINIMUM(L) initialise le minimum actuel avec car(L), puis parcourt le reste en remplaçant cette valeur par car(L) lorsqu’elle est plus petite ; la liste doit être non vide et, en cas d’égalité, la première occurrence est retenue.

💡 Astuce mémo

Une liste se dépile par sa tête tandis que le minimum actuel reste dans l’accumulateur.

📖 5. Multiplication russe binaire

★ À maîtriser

📐 Formule - Tout entier n possède une écriture binaire $n=\sum_{i=0}^{k} n_i 2^i$ où chaque chiffre binaire $n_i$ appartient à $\{0{,}1\}$.

• La multiplication russe initialise Z à 0, ajoute X à Z si Y est impair, double X, divise Y par 2 avec une division entière et répète ces opérations jusqu’à Y=0 ; Z contient alors le produit.

Compléments

• Avec X=61 et Y=37, la multiplication russe donne 2257.

💡 Astuce mémo

Y impair : ajouter X ; puis doubler X et diviser Y par 2.

📖 6. Fonctions calculables

🔑 Notions clés & Définitions

• Fonction calculable : Fonction f de N vers N pour laquelle il existe un programme de Peano qui s’arrête pour tout entier n fourni en entrée et renvoie f(n).

📝 Points essentiels

• Il existe des fonctions de N vers N qui ne sont pas calculables, car il y a strictement plus de fonctions de N vers N que de programmes de Peano, selon un argument de cardinalité.

• La thèse de Church-Turing affirme que tout algorithme intuitivement calculable peut être implémenté par un programme de Peano.

💡 Astuce mémo

Un programme qui termine avec f(n) rend f calculable ; une fonction non calculable échappe à tout programme de Peano.

📖 7. Indécidabilité du problème PCP

🔑 Notions clés & Définitions

• Problème PCP : Problème de décision qui demande s’il existe une séquence, avec répétitions autorisées, de dominos à deux chaînes dont la concaténation supérieure est identique à la concaténation inférieure.

★ À maîtriser

📌 Le problème de correspondance de Post est indécidable : aucun algorithme général ne peut toujours répondre « oui » ou « non » à la question posée.

Compléments

• Emil Post a démontré l’indécidabilité du PCP en 1946.

• Le problème de correspondance de Post sert souvent de point de départ pour démontrer l’indécidabilité d’autres problèmes par réduction.

💡 Astuce mémo

Des dominos empilés : les chaînes concaténées du haut et du bas doivent coïncider.

📖 8. Chiffrement symétrique

🔑 Notions clés & Définitions

• Chiffrement symétrique : Méthode qui utilise la même clé secrète pour chiffrer et déchiffrer les messages.

★ À maîtriser

• Le code de César décale chaque lettre de k positions dans l’alphabet et possède un espace de clés de 26 possibilités.

📌 Vigenère utilise une clé qui fournit des décalages successifs, tandis que le one-time pad exige une clé aléatoire aussi longue que le message et jamais réutilisée ; ce dernier est présenté comme incassable.

Compléments

• ROT13 est une involution : appliquer deux fois le décalage de 13 positions restitue le texte d’origine.

• Le code de César est vulnérable à la force brute et à l’analyse de fréquences des lettres.

💡 Astuce mémo

Même clé pour chiffrer et déchiffrer ; le partage de cette clé est le problème.

📖 9. Clés publiques et signatures

🔑 Notions clés & Définitions

• Cryptographie à clés publiques : Méthode qui attribue à chaque utilisateur une clé publique P et une clé privée p, différentes l’une de l’autre.

📝 Points essentiels

📌 Un message chiffré avec la clé publique P se déchiffre avec la clé privée p correspondante, et un message chiffré avec p se vérifie avec P.

• Pour envoyer un message confidentiel à Bob, Alice le chiffre avec la clé publique de Bob et Bob le déchiffre avec sa clé privée.

• Pour signer M, Alice calcule S=Code(pAlice,M) et envoie (M,S) ; Bob vérifie la signature en appliquant la clé publique d’Alice à S et en comparant le résultat à M.

💡 Astuce mémo

Clé publique du destinataire pour la confidentialité ; clé privée de l’expéditeur pour signer.

📊 Tableaux de synthèse

Chiffrement symétrique et à clés publiques