Epita:Algo:Course:Info-Spe
Contents |
Hash functions
Unlike tree search methods in the hash methods, the position of an element does not depend on its key value compared to other key values but only on the result of a calculation performed on this key.
The calculation is performed directly on the key using a function which converts the key to a value corresponding to a memory address or a table index. The interest is to obtain for all the manipulation algorithms (add, search, delete) a constant average complexity (not depending on the number of elements).
The graphs
Graphs are mathematical objects which can model many combinatoric problems. Without them, by conventional methods (mathematical analysis, for example), it would be complicated to tackle these problems.
But the graphs are not only that: they are also irreplaceable complex computer data structures when it's necessary to describe a set of objects and relationships between these objects. They are used, for example, to model a road, rail, air or communication network.
Among the major uses of the graphs, there are all the problems in determining connectivity and shortest paths calculations. Finally, the graphs are also used to describe dynamic systems (evolving in time) such as finite-state machines (finite-state automaton).
In short, for more, visit The Graphs.
The connectivities
In the caricatured manner, we can state the problem as follows: "I'm in Paris, I would really like to go to Nassau and I have the choice between car, train, boat or plane to make the journey. What kind of transport I can use? "
It could help to know if two points on a network are connected by a path. In the previous example, it is useless to search for a route between the two cities (Paris and Nassau) by car or by train. Indeed, the road or rail network does not connect them.
Using a graph, this problem consists in putting the same set all the vertices which are related to each other (directly or not). It may therefore be interesting to determine whether a graph is connected or not. Indeed, before transmitting data from one point to another or to find the shortest path from one element to another, knowing the two ends are connected can save us a lot of time.
For more details, let's look more closely at the graph connectivities ...
Shortest paths
Take our problem differently: "In second thought Nassau is overrated I'm still in Paris and I'd love (to put it mildly) to eat Cassoulet in Toulouse tonight. Could you please indicate or give me the shortest path (lowest mileage)? "
To understand the problem we can look at a map. If we disregard the implausible paths (through Dunkirk to go from Paris to Toulouse), there are still hundreds of thousands of possible paths. Among them, there are a few which deserve the title of shortest paths. The question is: how to spot them among all the others?
The answer is by using shortest path algorithms tailored to different constraints and possible cases.
The spanning tree
What is the connection between irrigating many parts of a valley with a single source of water, supplying several cities with a power plant, wiring an electronic circuit or interconnecting different Local networks as "economically" as possible?
Well, all these problems can be solved by with another classic application using graphs: the construction of the minimum spanning tree which is to be linked to the different nodes of a graph at a minimum accumulated cost.
(divide-and-conquer) Sorting algorithms
Coming soon ...
(Christophe "krisboul" Boullay)
