Epita:Algo:Course:Info-Sup

De EPITACoursAlgo.
Version du 30 août 2012 à 10:51 par Christophe (discuter | contributions)
(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)

Sommaire

Abstract Data Types

The design of an algorithm can be done in two ways ( an alternative !):

  • The first and the most simple is that coding and considering only the data types created for the occasion in a particular programming language, their implementation will be done via type declarations and methods (procedures and functions) of their own language. In this case , it could be difficult to translate the algorithm easily to another language (from C to Caml for example, or vice versa ( I'm not exacting!).
  • The second method consists to define abstract data types. This means that we will define a data type name, its own usage syntax (operations, parameters, etc..) and its own properties while being detached ( algo washes whiter) from all contingencies of a programming language and/or computer. For example, if a problem requires the use of a graph, we will only think about solving the problem without worrying about the how the graph will be implemented in memory neither how will be handled its various components.

Les structures séquentielles

Nous présenterons dans ce chapitre les structures séquentielles "classiques", à savoir les listes, les piles et les files. Nous donnerons à chaque fois la définition du type abstrait correspondant accompagnée de quelques commentaires explicatifs. Puis nous fournirons les diverses implémentations de ces types ainsi que quelques algorithmes de manipulation. Les algorithmes seront fournis à chaque fois et dans la mesure du possible des deux manières: abstraite (en utilisant les opérations des types abstraits) et concrète (en utilisant le formalisme algorithmique vu en TD (voir en annexe le Mémo du langage algorithmique réalisé par Nathalie 'Junior' Bouquet).

les structures arborescentes

Un arbre est constitué d’éléments appelés noeuds organisés de façon hiérarchique. L’élément de base est la racine (Incroyable !). En informatique, comme dans la vraie vie, les arbres se rencontrent un peu partout : construction de répertoire, système d’exploitation, compilateur, etc.

Du à leur propriété structurelle récursive, les manipulations et les déclarations des arbres se font naturellement sous une forme récursive. Ce qui ne veut pas dire que la forme itérative ne leur soit pas applicable, mais elle est moins intuitive et souvent moins adaptée.

Les arbres se rencontrent à la base sous deux formes : les arbres binaires et les arbres généraux.

Les algorithmes de recherche

Le but même du stockage de données, est de pouvoir manipuler celles-ci. Evidemment plus le nombre de données est important, plus les temps de gestion (ajout, modification, suppression, etc .) le seront. Or, pour pouvoir manipuler ces données, il nous faut d’abord les trouver et donc les rechercher. C’est ce temps de recherche que nous devons réduire au maximum (à un minimum s'entend :D). Pour cela, il existe diverses méthodes algorithmiques adaptées à diverses structures de données.

Les premières, les plus simples et les plus intuitives, sont présentées dans la partie Algorithmes de recherche : Méthodes de base.

Les suivantes, plus sophistiquées et basées sur les structures arborescentes, sont présentées dans la partie Algorithmes de recherche : Les arbres.

les tris simples

A venir...



(Christophe "krisboul" Boullay)

Outils personnels
Cours d'algo EPITA :
Accès aux algorithmes :