8INF433 Algorithmique (Introduction). Définition informelle Algorithme: Procédure ou ensemble fini...

8INF433

Algorithmique(Introduction)

Définition informelle

Algorithme: Procédure ou ensemble fini de règles permettant de résoudre un problème

Exemple: programme en C.

Structures de données: Méthodes permettant d'organiser de grandes quantités de données.

Il y a plusieurs algorithmes possibles pour un même problème.

Exemple 1Multiplication: algorithme standard

45

× 19

------

405 (9 × 45)

+ 45 (1 × 45)

------

855

Exemple 2Multiplication à la russe

45 19 1922 38 11 76 765 152 1522 3041 608 608

-------855

Exemple 2 (suite) Multiplication à la russe

19 45 459 90 904 1802 3601 720 720

-------855

Objectifs principaux du cours

• Apprendre certaines techniques permettant de concevoir des algorithmes efficaces

• Être en mesure d'analyser et de comparer l'efficacité de différents algorithmes.

Origine

Le mot algorithme dérive du nom:

Abû Abdullah Muhammad Ibn Mûsâ Al-Khawarizmî Vers 825 après J.C. il écrit un ouvrage de mathématique où il

décrit la façon d'effectuer l'addition, la multiplication, etc.

Premier algorithme non trivial connu (295 avant J.C.):

Algorithme d'Euclide pour calculer le plus grand commun multiple de deux nombres entiers.

Algorithme naïf

PGCD(m,n)

i = min(n,m) + 1

répéter

i=i-1

jusqu'à ce que i divise m et n

retourner i

Algorithme d'Euclide (version moderne)

PGCD(m,n)

tant que m>0 faire

t=m

m=n mod m

n=t

retourner n

t m n15 21

15 6 156 3 63 0 3

Problèmes

On est intéressé par les problèmes algorithmiques seulement:

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 culturelle 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 de problèmes algorithmiques

• Multiplication (problème d'évaluation):Entrée: Deux entiers binaires x et y (de longueur arbitraire)Sortie: Le produit de x par y en binaire

• Test de primalité (problème de décision):Entrée: Un entier binaire positif nSortie: 1 si n est premier, 0 sinon.

• Problème du plus court chemin (problème d'optimisation):Entrée: Un graphe pondéré, donné sous la forme d'une matrice

d'adjacence, ainsi que deux noeuds particuliers s et tSortie: Une suite de noeuds représentant un plus court chemin du

noeud s au noeud t

Le choix de l'algorithme

L'analyse d'un algorithme se fait selon les critères suivants:

1. Rectitude

2. Complexité (temps d'exécution, espace mémoire, etc.)

3. Facilité de maintenance

Nous nous intéresserons principalement au deux premiers critères.

Quelques problèmes étudiés dans ce cours (1)

Problèmes de nature mathématique:– Plus grand commun diviseur

– test de primalité

– multiplication

– exponentiation

– factorisation

– multiplication matricielle

Grande utilité en cryptologie (commerce électronique)

Cryptologie à clef publique (RSA)

1) Choisir 2 grands nombres premiers p et q2) Calculer n=pq3) Calculer m=(p-1)(q-1)4) Trouver e et d tels que ed mod m = 1

Clef privée: (d, n)Clef publique: (e, n)

Comment Alice et Bernard utilisent RSA

Bernard encodeson message Mavec cette clef:C=Me (mod n)

Bernard cherchela clef publiqued’Alice (e, n)dans un annuaire.

Alice reçoit C et utilise sa clef privée (d, n) pour le décrypter :M= Cd (mod n)

Quelques problèmes étudiés dans ce cours (2)

Problèmes de graphes:– Plus court chemin

– Arbre couvrant

– Problème du commis voyageur

– Coloration de graphes

– Parcours de graphes

Utilité dans plusieurs domaines (jeux, réseaux, etc.)

Quelques problèmes étudiés dans ce cours (3)

Traitement de séquences de caractères:– Plus longue sous-séquence commune

– Mise en forme de textes

– Recherche de chaînes de caractères

– Compression de texte

Applications en bio-informatique, base de données, traitement de texte.

Quelques problèmes étudiés dans ce cours (4)

Géométrie algorithmique:– Déterminer si deux segments de droite se coupent

– Recherche de l'enveloppe convexe

– Recherche des points les plus rapprochés

Application en infographie.

Techniques de conception d'algorithmes (1)

Algorithmes voraces (ou gloutons): Méthode itérative utilisée pour résoudre des problèmes d'optimisation.

Exemples d'applications: – Chemin le plus court dans un graphe

– Arbre couvrant minimal

– Compression de texte

– Souvent utilisé pour trouver une solution initiale afin résoudre un problème d'optimisation (e.g. branch and bound)

Techniques de conception d'algorithmes (2)

Algorithmes diviser-pour-régner: Approche récursive: On divise le problème en plusieurs sous problèmes et on combine les résultats pour obtenir la solution globale.

Exemples d'applications: – Tri par fusion– Quicksort– Multiplication de grand entiers– Exponentiation– Trouver les points les plus rapprochés

Techniques de conception d'algorithmes (3)

Programmation dynamique: Utilisé lorsqu'une solution récursive est inefficace parce que beaucoup d'appels identiques sont effectués

Exemples d'applications: – Calcul des nombres de Fibonacci

– Formatage de texte en paragraphe

– Produit de plusieurs matrices

– Plus longue sous séquence commune

Techniques de conception d'algorithmes (4)

Algorithmes probabilistes: L'algorithme a accès à un générateur de bits aléatoires.

Deux principaux types:1. Faible probabilité que le temps d'exécution soit long.2. Faible probabilité de ne pas trouver la bonne réponse.

Exemples d'applications: – Test de primalité– Factorisation– Approximation de problèmes complexes– Hachage universel

Techniques de conception d'algorithmes (5)

Algorithmes parallèles: L'algorithme peut utiliser plusieurs processeurs pour accélérer les calculs.

Exemples d'applications: – Multiplication matricielle– Tri par fusion

Outils mathématiques

• Notation asymptotique: Pour comparer et analyser les algorithmes indépendamment de la machine ou du langage

• Résolution de récurrence: Pour analyser l'efficacité des algorithmes récursifs

• Éléments de base de la théorie des probabilité: Pour analyser les algorithmes probabilistes.