Cours et exercices rôle des algorithmes en informatique

PARTIE 1 • INTRODUCTION
CHAPITRE 1 • RÔLE DES ALGORITHMES EN INFORMATIQUE
1.1 Algorithmes
Exercices
1.2 Algorithmes en tant que technologie
Exercices
PROBLÈMES
CHAPITRE 2 • PREMIERS PAS
2.1 Tri par insertion
Exercices
2.2 Analyse des algorithmes
Exercices
2.3 Conception des algorithmes
Exercices
PROBLÈMES
CHAPITRE 3 • CROISSANCE DES FONCTIONS
3.1 Notation asymptotique
Exercices
3.2 Notations standard et fonctions classiques
Exercices
PROBLÈMES
CHAPITRE 4 • RÉCURRENCES
4.1 Méthode de substitution
Exercices
4.2 Méthode de l’arbre récursif
Exercices
4.3 Méthode générale
Exercices
4.4 Démonstration du théorème général
Exercices
PROBLÈMES
CHAPITRE 5 • ANALYSE PROBABILISTE ET ALGORITHMES RANDOMISÉS
5.1 Le problème de l’embauche
Exercices
5.2 Variables indicatrices
Exercices
5.3 Algorithmes randomisés
Exercices
5.4 Analyse probabiliste et autres emplois des variables indicatrices
Exercices
PROBLÈMES
PARTIE 2 • TRI ET RANGS
CHAPITRE 6 • TRI PAR TAS
6.1 Tas
Exercices
6.2 Conservation de la structure de tas
Exercices
6.3 Construction d’un tas
Exercices
6.4 Algorithme du tri par tas
Exercices
6.5 Files de priorité
Exercices
PROBLÈMES
CHAPITRE 7 • TRI RAPIDE
7.1 Description du tri rapide
Exercices
7.2 Performances du tri rapide
Exercices
7.3 Versions randomisées du tri rapide
Exercices
7.4 Analyse du tri rapide
Exercices
PROBLÈMES
CHAPITRE 8 • TRI EN TEMPS LINÉAIRE
8.1 Minorants pour le tri
Exercices
8.2 Tri par dénombrement
Exercices
8.3 Tri par base
Exercices
8.4 Tri par paquets
Exercices
PROBLÈMES
CHAPITRE 9 • MÉDIANS ET RANGS
9.1 Minimum et maximum
Exercices
9.2 Sélection en temps moyen linéaire
Exercices
9.3 Sélection en temps linéaire dans le cas le plus défavorable
Exercices
PROBLÈMES
PART I E 3 • STRUCTURES DE DONNÉES
CHAPITRE 10 • STRUCTURES DE DONNÉES ÉLÉMENTAIRES
10.1 Piles et files
Exercices

Rôle des algorithmes en informatique

Qu’est-ce qu’un algorithme? En quoi l’étude des algorithmes est-elle utile ? Quel est le rôle des algorithmes par rapport aux autres technologies informatiques? Ce chapitre a pour objectif de répondre à ces questions.

ALGORITHMES
Voici une définition informelle du terme algorithme : procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d’étapes de calcul qui transforment l’entrée en sortie.
L’on peut aussi considérer un algorithme comme un outil permettant de résoudre un problème de calcul bien spécifié. L’énoncé du problème spécifie, en termes généraux, la relation désirée entre l’entrée et la sortie. L’algorithme décrit une procédure de calcul spécifique permettant d’obtenir cette relation entrée/sortie.
Supposons, par exemple, qu’il faille trier une suite de nombres dans l’ordre croissant.
Ce problème, qui revient fréquemment dans la pratique, offre une base fertile pour l’introduction de nombre de techniques de conception et d’outils d’analyse standard.
Voici comment nous définissons formellement le problème de tri :
Ainsi, à partir de la suite
31, 41, 59, 26, 41, 58, un algorithme de tri produit en sortie la suite
26, 31, 41, 41, 58, 59. À propos de la suite donnée en entrée, on parle d’instance du problème de tri. En général, une instance d’un problème consiste en l’entrée (satisfaisant aux contraintes, quelles qu’elles soient, imposées dans l’énoncé du problème) requise par le calcul d’une solution au problème.
Le tri est une opération majeure en informatique (maints programmes l’emploient comme phase intermédiaire), ce qui explique que l’on ait inventé un grand nombre d’algorithmes de tri. L’algorithme optimal pour une application donnée dépend, entre autres facteurs, du nombre d’éléments à trier, de la façon dont les éléments sont plus ou moins triés initialement, des restrictions potentielles concernant les valeurs des éléments, ainsi que du type de périphérique de stockage à utiliser : mémoire principale, disques ou bandes.
Un algorithme est dit correct si, pour chaque instance en entrée, il se termine en produisant la bonne sortie. L’on dit qu’un algorithme correct résout le problème donné. Un algorithme incorrect risque de ne pas se terminer pour certaines instances en entrée, voire de se terminer sur une réponse autre que celle désirée. Contrairement à ce que l’on pourrait croire, un algorithme incorrect peut s’avérer utile dans certains cas, si son taux d’erreur est susceptible d’être contrôlé. Nous en verrons un exemple au chapitre 31, quand nous étudierons des algorithmes servant à déterminer les grands nombres premiers. En général, seuls nous intéresseront toutefois les algorithmes corrects.
Un algorithme peut être spécifié en langage humain ou en langage informatique, mais peut aussi être basé sur un système matériel. L’unique obligation est que la spécification fournisse une description précise de la procédure de calcul à suivre.

…

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Introduction à l’algorithmique (5.3 Mo) (Cours PDF)