Epita:Algo:Course:Info-Sup
Contents |
Abstract Data Types
The design of an algorithm can be done in two ways (only once alternative !):
- The first and the most simple way consists in coding and considering only data types created for the occasion in a particular programming language. Their implementation will be done via type and method (procedures and functions) declarations in their own language. In this case , it can be difficult to translate the algorithm easily to another language (from C to Caml for example, or vice versa (I'm not picky !).
- The second method consists in defining abstract data types. This means that we will define a data type name, its own usage syntax (operations, parameters, etc..) and its own properties without considering anything related to its implementation (contingencies of a programming language and/or a computer). For example, if a problem requires the use of a graph, we will only think about solving the problem, neither worrying about the how the graph will be implemented in memory, nor how its various components will be handled .
Elementary Data Structures (linear)
This chapter will introduce the "sequential" elementary data structures, that is, the lists, stacks and queues. We will give the corresponding abstract type definition accompanied by some explanatory comments. Then we will provide various implementations of these data structures as well as some kinds of algorithms using them. Algorithms will be provided whenever possible in two ways: Abstract (using abstract types operations) and "concrete" (using algorithm formalism seen in TD (see annex algorithm language memo made by Nathalie 'Junior' Bouquet).
The sets
Unlike sequential structures such as lists where the order of items is fundamental, for the sets it is an unimportant concept. What is important is that element is present in the structure or not . This chapter will not recall the definitions and properties of sets that are assumed to be known. However it also present bags (multi-sets) that accept repeated elements in a set.
Trees
A tree is a collection of elements called nodes organized in a hierarchical structure. The basic element is the root (Amazing!). In computer science, as in real life, you can encounter trees everywhere: file directory, operating system, compiler, and so on. Due to their natural recursive structure, manipulation and statement trees are naturally recursively defined. This doesn't mean that the iterative form aren't used, but it is less intuitive and often less suitable. Trees are found basically in two forms: Binary trees and Trees.
Searching Algorithms
The very purpose of data storage is to manage them. Obviously the more you've got data, the more you need time to manage (insert, modify, delete, and so on..) them. However, to be able to manipulate these data, we must first find them and then search for them. It's this search time of research we have to minimize. For this, there are various algorithmic's methods adapted to different data structures.
The first, easiest and most intuitive, are presented in the Searching Algorithms: Basic Methods.
The following, more sophisticated and based on trees structures, are presented in the Searching Algorithms: Trees.
Basic Sorting Algorithms
Under construction...
(Christophe "krisboul" Boullay)
