Sommaire: Cours algorithme et programmation méthodes de tri
Introduction
Complexite des algorithmes
Scalaires
Les entiers
Les nombres ottants
1 Tableaux
1.1 Le tri
1.1.1 Methodes de tri elementaires
1.1.2 Analyse en moyenne
1.1.3 Le tri par insertion
1.2 Recherche en table
1.2.1 La recherche sequentielle
1.2.2 La recherche dichotomique
1.2.3 Insertion dans une table
1.2.4 Hachage
1.3 Programmes en C
2 Recursivite
2.1 Fonctions recursives
2.1.1 Fonctions numeriques
2.1.2 La fonction d’Ackermann
2.1.3 Recursion imbriquee
2.2 Indecidabilite de la terminaison
2.3 Procedures recursives
2.4 Fractales
2.5 Quicksort
2.6 Le tri par fusion
2.7 Programmes en C
3 Structures de donnees elementaires
3.1 Listes chainees
3.2 Piles
3.3 Evaluation des expressions arithmetiques prexees
3.4 Files
3.5 Operations courantes sur les listes
3.6 Programmes en C
4 Arbres
4.1 Files de priorite
4.2 Borne inferieure sur le tri
4.3 Implementation d’un arbre
4.4 Arbres de recherche
4.5 Arbres equilibres
4.6 Programmes en C
5 Graphes
5.1 Denitions
5.2 Matrices d’adjacence
5.3 Fermeture transitive
5.4 Listes de successeurs
5.5 Arborescences
5.6 Arborescence des plus courts chemins
5.7 Arborescence de Tremaux
5.8 Composantes fortement connexes
5.8.1 Denitions et algorithme simple
5.8.2 Utilisation de l’arborescence de Tremaux
5.8.3 Points d’attache
5.9 Programmes en C
6 Analyse Syntaxique
6.1 Denitions et notations
6.1.1 Mots
6.1.2 Grammaires
6.2 Exemples de Grammaires
6.2.1 Les systemes de parentheses
6.2.2 Les expressions arithmetiques prexees
6.2.3 Les expressions arithmetiques
6.2.4 Grammaires sous forme BNF
6.3 Arbres de derivation et arbres de syntaxe abstraite
6.4 Analyse descendante recursive
6.5 Analyse LL
6.6 Analyse ascendante
6.7 Evaluation
6.8 Programmes en C
7 Modularite
7.1 Un exemple les les de caracteres
7.2 Interfaces et modules
7.3 Interfaces et modules en Pascal
7.4 Compilation separee et librairies
7.5 Dependances entre modules
7.6 Tri topologique
7.7 Programmes en C
8 Exploration
8.1 Algorithme glouton
8.1.1 Aectation d’une ressource
8.1.2 Arbre recouvrant de poids minimal
8.2 Exploration arborescente
8.2.1 Sac ados
8.2.2 Placement de reines sur un echiquier
8.3 Programmation dynamique
8.3.1 Plus courts chemins dans un graphe
8.3.2 Sous-sequences communes
A Pascal
A.1 Un exemple simple
A.2 Quelques elements de Pascal
A.2.1 Symboles, separateurs, identicateurs
A.2.2 Types de base
A.2.3 Types scalaires
A.2.4 Expressions
A.2.5 Types tableaux
A.2.6 Procedures et fonctions
A.2.7 Blocsetportee des variables
A.2.8 Types declares
A.2.9 Instructions
A.2.10 Cha^nes de caracteres
A.2.11 Ensembles
A.2.12 Arguments fonctionnels
A.2.13 Entrees { Sorties
A.2.14 Enregistrements
A.2.15 Pointeurs
A.2.16 Fonctions graphiques
A.3 Syntaxe BNF de Pascal
A.4 Diagrammes de la syntaxe de Pascal
B Le langage C
B.1 Un exemple simple
B.2 Quelques elements de C
B.2.1 Symboles, separateurs, identicateurs
B.2.2 Types de base
B.2.3 Types scalaires
B.2.4 Expressions
B.2.5 Instructions
B.2.6 Procedures, fonctions, structure d’un programme
B.2.7 Pointeurs et tableaux
B.2.8 Structures
B.2.9 Entrees-Sorties
B.2.10 Fonctions graphiques
B.3 Syntaxe BNF de C
B.4 Diagrammes de la syntaxe de C
C Initiation au systeme Unix
C.1 Trousse de Survie
C.1.1 Se connecter
C.1.2 Se deconnecter
C.1.3 Le systeme de fen^etres par defaut
C.1.4 Obtenir de l’aide
C.1.5 Changer son mot de passe
C.1.6 Courrier electronique
C.1.7 Polyaf
C.1.8 Editeur de texte
C.1.9 Manipulations simples de chiers
C.1.10 Cycles de mise au point
C.1.11 Types de machines
C.2 Approfondissement
C.2.1 Systeme de chiers
C.2.2 Raccourcis pour les noms de chiers
C.2.3 Variables
C.2.4 Le chemin d’acces aux commandes
C.2.5 Quotation
C.2.6 Redirections et ltres
C.2.7 Processus
C.2.8 Programmation du shell
C.3 Unix et le reseau de l’X
C.4 Bibliographie Unix
Bibliographie
Table des gures
Index
Extrait du cours algorithme et programmation méthodes de tri
Introduction
En 30 ans, l’informatique est devenue une industrie importante: 10% des investissements hors batiments des societes francaises. Au recensement de 1982, 50000 cadrestechniciens se declaraient informaticiens, 150000 en 1991. Une certaine maniere de pensee et de communication a decoule de cette rapide evolution. L’informatique appara^t comme une discipline scientique introduisant des problemes nouveaux ou faisant revivre d’autres. Certains pensent que l’informatique est la partie constructive des mathematiques, puisqu’on ne s’y contente pas de theoremes d’existence, mais du calcul des objets. D’autres y voient les mathematiques concretes, puisque le domaine a l’exactitude et la rigueur des mathematiques, et que la confrontation des idees abstraites a la realisation de programmes interdit le raisonnement approximatif. Une autre communaute est interessee surtout par la partie physique du domaine, car une bonne part des progres de l’informatique est due au developpement foudroyant de la micro-electronique.
La jeunesse de l’informatique permet a certains de nier son aspect scientifique: \les ordinateurs ne sont que des outils pour faire des calculs ou des machines traitement de texte ». Malheureusement, beaucoup de \fous de la programmation » etayent l’argument precedent en ignorant toute consideration theorique qui puisse les aider dans leurs constructions souventtres habiles. Regardons la definition du mot hacker fournie dans The New Hacker’s Dictionary [39], dictionnaire relu et corrige electroniquement par une bonne partie de la communauté Informatique.
Complexite des algorithmes
Dans ce cours, il sera question de complexite d’algorithmes, c’est-a-dire du nombre d’operations elementaires (aectations, comparaisons, operations arithmetiques) eectuees par l’algorithme. Elle s’exprime en fonction de la taille n des donnees. On dit que la complexite de l’algorithme est O(f(n)) ou f est d’habitude une combinaison de polynomes, logarithmes ou exponentielles. Ceci reprend la notation mathematique classique, et signie que le nombre d’operations eectuees est borneparcf(n), ou c est une constante, lorsque n tend vers l’inni.
Considerer le comportement a l’inni de la complexite est justie par le fait que les donnees des algorithmes sont de grande taille et qu’on se preoccupe surtout de la croissance de cette complexite en fonction de la taille des donnees. Une question systematique a se poser est: que devient le temps de calcul si on multiplie la taille des Scalaires Faisons un rappel succinct du calcul scalaire dans les programmes. En dehors de toutes les representations symboliques des scalaires, via les types simples, il y a deux grandes categories d’objets scalaires dans les programmes: les entiers en virgule xe, les reels en virgule ottante.
Les entiers
Le calcul entier est relativement simple. Les nombres sont en fait calcules dans une arithmetique modulo N =2N ou n estlenombre de bits des mots machines. Ainsi, les processeurs de 1992 peuventavoir une arithmetique precise sur quelques milliards de milliards, 100 fois plus rapide qu’une machine 16 bits! Il faut toutefois faire attention alamultiplication ou pire a la division qui a tendance sur les machines RISC (Reduced Instruction Set Computers)a prendre beaucoup plus de temps qu’une simple addition, typiquement 10 fois plus sur le processeur R3000 de Mips. Cette precision peut ^etre particulierement utile dans les calculs pour acceder aux chiers. En eet,on a des disques de plus de 4 Giga Octets actuellement, et l’arithmetique 32 bits est insusante pour adresser leurs contenus.
Chapitre 1 Tableaux
Les tableaux sont une des structures de base de l’informatique. Un tableau represente selon ses dimensions, un vecteur ou une matrice d’elements d’un meme type. Un tableau permet l’acces direct a un element, et nous allons nous servir grandement de cette propriete dans les algorithmes de tri et de recherche en table que nous allons considerer.
1.1 Le tri
Qu’est-ce qu’un tri? On suppose qu’on se donne une suite de N nombres entiers ha et on veut les ranger en ordre croissant au sens large. Ainsi, pour N = 10, la suite devra devenir
h18; 3; 10; 25; 9; 3; 11; 13; 23; 8i
h3; 3; 8; 9; 10; 11; 13; 18; 23; 25i
Ce probleme est un classique de l’informatique. Il aete etudie en detail, cf. la moitie du livre de Knuth [29]. En tant qu’algorithme pratique, on le rencontre souvent. Par exemple, il faut etablir le classement de certains eleves, mettre en ordre un dictionnaire, trier l’index d’un livre, faire une sortie lisible d’un correcteur d’orthographe, ::: Il faudra bien faire la distinction entre le tri d’un grand nombre d’elements (plusieurs centaines), et le tri de quelques elements (un paquet de cartes). Dans ce dernier cas, la methode importe peu. Un algorithme amusant, bogo-tri, consiste a regarder si le paquet de cartes est deja ordonne. Sinon, on le jette par terre. Et on recommence. Au bout d’un certain temps, on risque d’avoir les cartes ordonnees. Bien s^ur, le bogo-tri peut ne pas se terminer. Une autre technique frequemment utilisee avec un jeu de cartes consiste a regarder s’il n’y a pas une transposition a eectuer. Des qu’on en voit une a faire, on la fait et on recommence. Cette methode marche tres bien sur une bonnedistribution de cartes.
1.1.1 Methodes de tri elementaires
Dans tout ce qui suit, on suppose que l’on trie des nombres entiers et que ceux-ci se trouvent dans un tableau a. L’algorithme de tri le plus simple est le tri par selection.Il consiste a trouver l’emplacement de l’element le plus petit du tableau, c’est-a-direl’entier m tel que ales elements a1et ai amm pour tout i. Une fois cet emplacement m trouve, on echange . Puis on recommence ces operations sur la suite ha ainsi on recherche le plus petit element de cette nouvelle suite et on l’echange avec a Et ainsi de suite ::: jusqu’au momentou on n’a plus qu’une suite composee d’un seul element ha N i.
………..
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours algorithme et programmation méthodes de tri (1719 Ko) (Cours PDF)
