Sommaire: Cours de formation gratuits pour apprendre l’algorithmique avec exercices corrigés

1 Comptages
1.1 Principes
1.2 Comptages elementaires
1.2.1 Nombre de mots de longueur k
1.2.2 Nombre de permutations de n elements
1.2.3 Nombre de mots de longueur k sans repetition
1.2.4 Nombre de mots croissants de longueur k, sans repetition
1.2.5 Nombre de mots croissants de longueur k, repetitions possibles
1.2.6 Calcul de S(n; k)
1.2.7 Calcul de Pn
1.3 Techniques d’enumerations i=1ik
1.3.1 Vecteurs binaires de longueur n
1.3.2 n! permutations de n objets
1.4 Denombrement
1.4.1 Methode de Polya
1.4.2 Exemples d’application
2 Relations de recurrence
2.1 Recurrences lineaires homogenes a coecients constants
2.2 Recurrences lineaires non homogenes a coecients constants
2.2.1 Transformation en une equation homogene.
3 Complexite
3.1 La notation de l’ordre de ou notation grand O
3.2 La notation Omega ( )
3.3 La notation Theta (_)
4 Algorithmes
4.1 Algorithmes de tri
4.1.1 Tri par s_election (Selection Sort)
4.1.2 Tri par insertion (Insertion Sort)
4.1.3 Tri par bulles (Bubble Sort)
4.1.4 Tri Shell (Shell Sort)
4.1.5 Quicksort
4.1.6 Tri par fusion (Merge Sort)
4.1.7 Tri par tas (Heap Sort)
4.2 Multiplication de grands entiers
5 Graphes
5.1 Introduction
5.1.1 Denitions
5.2 Les arbres
5.2.1 Arbres complets (ou parfaits) partiellement ordonnes
5.3 Representation des graphes
5.3.1 Representation matricielle
5.3.2 Representation par une table de successeurs
5.4 Parcours des graphes
5.4.1 Parcours en profondeur
5.4.2 Tri topologique
5.4.3 Arbre maximal de poids minimal
5.4.4 Le plus court chemin (Algorithme de Dijkstra)
5.5 Composantes connexes
5.5.1 2-connexite
5.5.2 Composantes fortement connexes
6 Exercices corriges
6.1 Propedeutique II – 12 juillet 2002
6.2 Test d’algorithmique – 7 juin 2002

Extrait du cours de formation gratuits pour apprendre l’algorithmique avec exercices corrigés

Chapitre 4 Algorithmes
4.1 Algorithmes de tri
Les algorithmes proposés dans cette section pourront etre utilisés comme brique de base pour d’autres algorithmes speciques aux donnees a traiter. L’algorithme de tri Shell mis a part, ces méthodes ne sont pas trés efficaces pour de tres grandes populations d’elements.
On distingue deux sortes de tris :
Tri interne. Tous les elements sont stockés en memoire et le tri s’opere donc exclusivement entre la memoire de donnees, la memoire d’instructions et le processeur.
Tri externe. Si les elements a trier sont trop volumineux, la memoire n’est pas en mesure de stocker tous les elements. Il est aussi probable que seule une petite partie de la description complete d’un enregistrement soit utile pour le tri. Dans ce cas, seule cette information, ou une partie de cette information, sera chargee en memoire. Le tri s’operera alors conjointement avec un support de stockage externe, comme une bande magnetique.
4.1.1 Tri par selection (Selection Sort)
Le tri par selection parcourt les elements a la recherche du plus petit. Une fois trouvé, il deplace en debut de liste, a la n de la partie triee. Il recommence a chercher le plus petit element dans la partie non encore triee.
4.1.2 Tri par insertion (Insertion Sort)
Le tri par insertion prend le premier element de la partie non triee et l’insere a la bonne place dans la partie triee. Ensuite il recommence jusqu’a n’avoir plus aucun element dans la partie non triee.
4.1.3 Tri par bulles (Bubble Sort)
Le tri par bulles consiste a parcourir plusieurs fois la liste a chaque fois depuis le debut, a prendre un element et a le deplacer vers la n de la liste en l’intervertissant avec son voisin jusqu’a ce que celui-ci soit a sa place denitive. La partie triee se construit donc en n de liste.
4.1.4 Tri Shell (Shell Sort)
Le tri Shell ameliore le tri par insertion en ne portant pas les echanges uniquement sur des elements adjacents. L’idee est de reorganiser le chier de facon a ce que les elements qui sont loin de leur position nale puissent arriver a cette position sans trop de comparaisons et d’echanges. Pour cela, on trie les sous-suites d’elements situes a une distance h les uns des autres. Puis on diminue h jusqu’a ce qu’il vaille 1. On a donc a chaque iteration des sous-suites triees entrelacees.
4.1.5 Quicksort
Algorithme de type Divide-and-Conquer (ie. Diviser pour regner), Quicksort opere selon le principe qu’il est plus simple de trier une petite liste qu’une grande.La premiere etape consiste donc a partager recursivement la liste a trier en deux sous-listes jusqu’a obtenir un ensemble d’elements a trier contenus dans une liste de taille raisonnable. A ce moment, toutes ces listes sont triees puis combinees deux a deux pour retrouver la liste initiale, mais triee. Quicksort porte le nom de tri par segmentation dans certains ouvrages.
Dans l’exemple, les parties en gras donnent l’etat de la memoire a la n de chaque passage dans la fonction de tri avec partitionnement, juste avant l’appel recursif sur les deux sous-listes, a gauche et a droite du pivot. Le pivot, par souci de simplicite, a ete choisi comme etant le dernier element de la liste a trier.

…….

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Cours de formation gratuits pour apprendre l’algorithmique avec exercices corrigés (386 KO) (Cours PDF)