Hi. In this part on
algorithmics, we've seen tasks,
the division of an algorithm
into small simple tasks.
Then, we've seen variables and the
complete list of elementary instructions
allowing to write every algorithm.
We'll now take a step back from
algorithmics as a science
to show you what else we
can do, more generally.
Particularly concerning data structures,
there are many much more complex
structures existing in computer science,
I'll give you a non-exhaustive list.
There are the lists Brice talked about
in the data organization sequence;
more complex, doubly linked lists,
where there are links from one to
the next, but also to the previous;
the stacks and queues that are especially
used to store tasks to carry out;
hash tables to represent sets;
trees and heaps that are
more complex structures,
but with many underlying structures;
the graphs I'll talk about a bit later;
and the databases on
which you also have a sequence.
I'll talk about graphs.
The drawing on this
slide is a graph.
They are boxes called nodes and edges,
so arrows from a node to another.
They're used to represent many things.
For instance, a network, Internet network,
electrical network, water network.
They can represent dependencies.
I need to have done C to do B,
or relationships, A and B know each other.
There are different types of graphs.
This graph has arrows,
but there are graphs without arrows,
called undirected graphs.
How do we represent that with data structures?
There are several options.
One is the adjacency graph,
there's a Boolean that indicates
if two nodes are linked.
When given two nodes,
for instance A and C,
it'll answer true because
A is linked to C.
Another way to represent graph is
with a neighbor list.
Graph A has two neighbors, B and C.
Graph C has no neighbor.
Now, I'll show you a graph
that is a bit more complex
which represents this part of the course.
The "computer science and its foundations"
part is represented by this graph.
Each node is a sequence.
Then, the arrows
represent the dependencies.
For instance, I1 and I2,
that are sequences of the
binary coding of information part,
you need to have watched I1, so
I1.1 to watch sequence I1.2.
Similarly, all I1 represent the
binary coding of information courses,
I2 are the algorithmics courses,
where you are now.
I3 is programming, and I4 is
computer and networks architecture.
The dependency graph is here.
Say you want to watch
a given sequence,
how will you know which
sequences you need to watch before?
I can give you an algorithm
I'll unfold right after.
As input, you have a dependency graph
that is exactly the drawing
on the previous slide
where neighbors are
stored as a list.
I have a start node n which is the
sequence I'd really like to watch,
and the input is the list
of the dependencies of n,
so the sequences I need to
watch to watch the sequence n.
You have several variables.
The first variable is "res" that
will be the result, initialized as empty.
"to_process" is a temporary variable,
it's all I have to process.
I initialize as empty, then I add n in it
since n is the initialization,
what do I have to process?
I need to process n for now.
Then, I look at the "to_process" variable
that can be represented with several
different data structures, by the way.
As long as it's not empty, I take a value
out of this list or data structure.
I extract it completely.
I retrieve x and "to_process" is the previous
"to_process" without this x variable.
I add x in the result
since I'll depend on x.
Then, I add all the children of x
to the list of things "to_process".
What does it look
like, with an example?
Say I want to watch the sequence I4.2,
what do I have to watch before?
I have colors to represent
the different variables.
"to_process" will be in red,
the result in green,
and x, the one I'm working on
at a given moment, will be in blue.
At the beginning, I start from I4.2,
so I need to process I4.2.
So I4.2 is indeed the x I'm working on.
Then, I examine all its children,
and I put them in "to_process".
Now, I4.2, which was the x, has gone
into the results since I depend on it.
I have a list of things to process,
so the three red nodes.
Then I take a red node, any one,
the data structure will give
me one, it doesn't matter.
Say I take I3.2.
It's the new x.
It's the one I'm looking at.
I take all its children.
It only has one, I3.1,
which is added to "to_process".
I've I3.2 that I've added into the results.
I'll iterate like this.
Each time, I'll add the children in red
and each time, I'll take a red one
and add all its children.
This is what we get.
To watch I4.2, I have to watch
all these sequences.
So you've seen an
example of path in a graph.
Of course, algorithmics is
not just about graphs.
There are many other data
structures, many other algorithms.
Here's a non-exhaustive list of books
and references you can have a look at.
There are three books in English,
by Sedgewick and Knuth,
and then several references in French,
one in OCaml, one in Python, one in Java.