Algorithme
Exercices algorithme : Piles et Files attente
Exercice 1 :
Réimplanter la fonction fibr ci-dessous en utilisant une pile pour remplacer les appels récursifs.
long fibr(int n) {
assert((n>0) && (n<47) // les données dans cet intervalle sinon erreur
if ( (n = = 1) || (n = =2) return 1;
else return fibr(n-1) + fibr(n-2);
} // fin de la fonction
Exercice 2 :
Cours Algorithme : Introduction - Procédure - Fonctions - Tests - Boucles
Algorithme : Description en langage naturel de la suite des actions effectuées par un programme structuré. Un algorithme est écrit en utilisant un langage de description d’algorithme (LDA).
L’algorithme ne doit pas être confondu avec le programme proprement dit (tel que Pascal, C, ..)
LES ARBRES BINAIRES avec des Exemples
MODELISATION DE LA STRUCTURE
Introduction
Les tableaux sont des structures qui permettent un accès direct à un élément à partir de son indice. Par contre, l'insertion ou la suppression dans de telles structures d'un élément à une position donnée sont des opérations coûteuses. D'un autre côté, les listes chaînées facilitent les actions d'insertion et de suppression d'un élément, mais ne permettent pas l'accès direct à un élément.
FILES ATTENTE cours avec des exemples
MODELISATION DE LA STRUCTURE
Introduction
Une file d'attente est une structure qui stocke de manière ordonnée des éléments, mais rend accessible uniquement un seul d'entre eux, appelé la tête de la file. Quant on ajoute un élément, celui-ci devient le dernier élément qui sera accessible. Quant on retire un élément de la file, on retire toujours la tête, celle-ci étant le premier élément qui a été placé dans la file. Pour résumer, le premier élément ajouté dans la pile est le premier élément à en être retiré. Cette structure est également appelée une liste FIFO (First In, First Out).
LES PILES - LA TOUR DE HANOI
MODELISATION DE LA STRUCTURE
Introduction
Une pile est une structure qui stocke de manière ordonnée des éléments, mais rend accessible uniquement un seul d'entre eux, appelé le sommet de la pile. Quant on ajoute un élément, celui-ci devient le sommet de la pile, c'est-à-dire le seul élément accessible. Quant on retire un élément de la pile, on retire toujours le sommet, et le dernier élément ajouté avant lui devient alors le sommet de la pile. Pour résumer, le dernier élément ajouté dans la pile est le premier élément à en être retiré. Cette structure est également appelée une liste LIFO (Last In, First Out).
les tableaux avec les algorithmes de TRI
INTRODUCTION
Dans ce chapitre, nous allons présenter deux méthodes pour trier les éléments d'un tableau.
Nous ne présenterons pas les algorithmes les plus efficaces. Nous avons choisi de présenter tout d'abord la méthode de tri dite "par sélection". Il s'agit d'une méthode qui n'est pas très rapide. Ensuite, nous présenterons la méthode dite "par fusion" qui est beaucoup plus efficace. Dans ce chapitre, nous utiliserons la fonction PLUS_PETIT(a,b) pour trier. Cette fonction renvoie VRAI si l'élément a est plus petit que l'élément b.
Cours Algorithmique : Structures de Données - les tableaux - listes chaînées - piles - files - arbres binaires
STRUCTURES DE DONNÉES
INTRODUCTION
Ce document est un résumé concernant les structures les plus classiques rencontrées en informatique pour organiser des données. On suppose que le lecteur connait déjà les tableaux et les enregistrements (exemple: record en Pascal, struct en C). Pour aborder les différentes structures de données présentées ici, le lecteur devra également bien maîtriser la notion de pointeurs et de gestion dynamique de la mémoire.
Cours Algorithme
- Méthodes de libération automatique.
- Système semi-automatique.
1 Allocation et Libération d'espace
- Système semi-automatique.
Une allocation d'espace est nécessaire pour toute structure qui ne respecte pas les règles des variables locales des fonctions. De la même manière, une libération est aussi nécessaire lorsque la variable n’est plus utilisée, sinon une longue exécution du programme risque d'échouer, faute d'espace mémoire disponible .
Attention, libérer trop ou trop tôt une variable peut aussi être désastreux. La gestion de la mémoire peut être automatique, semi-automatique ou artisanale selon le langage de programmation et l'application.
Recherche d'occurrences d'une chaîne de caractères dans une autre
- L'algorithme de Knuth-Morris-Pratt.
- L'algorithme de Boyer et Moore.
1 Recherche d'occurrences d'une chaîne de caractères dans une autre
Si l’on considère une chaîne longue le texte dans un tableau T[1..n] et une chaîne courte le cible dans un tableau C[1..m] ; vérifier qu'une occurrence de C commence à T[i] prend un temps m. Donc, un algorithme simple en temps se retrouve avec la complexité O(mn).
- L'algorithme de Boyer et Moore.
1 Recherche d'occurrences d'une chaîne de caractères dans une autre
Si l’on considère une chaîne longue le texte dans un tableau T[1..n] et une chaîne courte le cible dans un tableau C[1..m] ; vérifier qu'une occurrence de C commence à T[i] prend un temps m. Donc, un algorithme simple en temps se retrouve avec la complexité O(mn).
Les Fonctions sur les nombres
- Génération de nombres.
- Génération des structures.
- Algorithmes probabilistes.
- Génération des structures.
- Algorithmes probabilistes.
Les Structures Complexes - Graph - Arbre - Sous-ensemble - Permutations
- Sous-ensemble d'un ensemble.
- Arbres (Binaires ou autres).
- Graphes.
- Permutations.
- Arbres (Binaires ou autres).
- Graphes.
- Permutations.
