[Livre] Algorithmique Cours avec 957 exercices et 158 problèmes

[Djug]

Bonjour,

La rédaction de DVP a lu pour vous l'ouvrage suivant:
Algorithmique -Cours avec 957 exercices et 158 problèmes, de Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein

RÉSUMÉ DE L'ÉDITEUR

Introduction complète à l'algorithmique, cette 3ème édition, révisée et mise à jour, comporte deux nouveaux chapitres, l'un sur les arbres de Van Emde Boas et l'autre sur les algorithmes multithreads. Plusieurs nouveaux énoncés d'exercices et de problèmes ont été ajoutés. Au total, plus de 920 exercices et 140 problèmes sont proposés. Cet ouvrage s'est aujourd'hui imposé comme une référence mondiale pour l'enseignement de l'algorithmique. Exhaustif et facile d'accès c'est un outil de travail complet et indispensable pour les étudiants et les professionnels de l'informatique.

L'éventail des algorithmes étudiés va des plus classiques, comme les algorithmes de tri et les fonctions de hachage, aux plus récents, comme ceux de la cryptographie, permettant ainsi de passer progressivement des notions élémentaires aux thèmes les plus pointus.

Les algorithmes sont rédigés en français et dans un pseudo-code proche des langages Pascal, C et Fortran. Ils sont analysés en profondeur et toujours complétés par des preuves mathématiques. De nombreux exemples, figures, études de cas et exercices de difficulté graduée viennent compléter les explications. Au total ce sont les énoncés de plus de 955 exercices et 155 problèmes qui sont proposés. Les solutions de 80 d'entre eux sont accessibles en ligne

L'avez-vous lu? Comptez-vous le lire bientôt?

Quel est votre avis?

[Franck Dernoncourt]

Effectivement ce livre est incontournable pour quiconque voulant comprendre l'algorithmique. Beaucoup de questions posées sur ce forum (sur la complexité notamment) y ont d'ailleurs leur réponse.

Quelques précisions concernant la critique :

Envoyé par Benwit

Vendu à plus de 20 000 exemplaires

Ca c'est pour la version française, la version anglaise en est à 500,000 (toutes versions confondues) en 20 ans, annonce fêtée il y a justement une semaine : Milestone for MIT Press’s bestseller.

Envoyé par Benwit

Il est probable que ceux qui bloquent sur des problèmes leur reprocheront ce choix.

Le manuel des solutions de la seconde version est disponible en ligne (je remercie celui qui a pris le temps de le faire car personnellement je n'apprécie vraiment pas les exercices non corrigés). Je n'ai pas encore lu la troisième version, mais probablement la plupart des exercices sont les mêmes (Benwit, confirmes-tu ?).

Envoyé par Benwit

Je me suis étonné de l'utilisation du français dans le pseudo-code à l'heure des langages de développement majoritairement anglophones. Finalement, ce choix se comprend pour un ouvrage didactique destiné à un public francophone.

Je lis rarement des ouvrages informatiques en français, mais cela ne me choque pas... je dirais que tu l'as bien mérité

[Acrim]

Sans le message de Franck je ne me serai pas rendu compte qu'il s'agit de la version française de "Introduction to Algorithms". Si le contenu est effectivement le même, c'est un peu une bible de l'algorithmique (complet, bien illustré).

[benwit]

@Acrim, oui, j'ai oublié de le préciser.
Même si le nombre d'algorithmes est infini, je comprend que le terme d'introduction ait été retiré (vis à vis d'autres ouvrages)

@Franck
Il y a à priori les exercices de la version précédente.
Ils ont ajoutés 100 nouveaux exercices et 28 problèmes.

Pour ce qui est de la langue, c'est vrai qu'en tant qu'informaticiens, on sait l'importance de l'anglais et d'autant plus pour les chercheurs et les publications.
C'est vrai qu'il n'y a rien de pire qu'une mauvaise traduction ou une traduction inusité par les pros. J'ai trouvé l'ouvrage bien traduit. C'est juste qu'ils ont poussé la traduction jusqu'aux algos et quand on voit le volume, cela leur a fait du travail en plus. D'ailleurs, j'ai moi même appris l'algo avec ce genre de pseudo code français, c'est juste que depuis, à force de développer en anglais, j'avais oublié.
Et puis pour répondre à ton smiley , je dirai que je défend notre langue française !

[kdmbella]

Envoyé par Acrim

Sans le message de Franck je ne me serai pas rendu compte qu'il s'agit de la version française de "Introduction to Algorithms". Si le contenu est effectivement le même, c'est un peu une bible de l'algorithmique (complet, bien illustré).

c'est un livre à avoir absolument dans sa bibliothèque perso!
quand je pense aux difficultés par lesquelles je suis passé pour comprendre certain concept et que j'avais pas une bonne bibliographie j'en ai encore les yeux tout rouge donc moi aussi je le conseil autant au débutant qu'au expert et en particulier pour les enseignants.

[zuymanto]

Envoyé par Franck Dernoncourt

[…]
Le manuel des solutions de la seconde version est disponible en ligne (je remercie celui qui a pris le temps de le faire car personnellement je n'apprécie vraiment pas les exercices non corrigés). Je n'ai pas encore lu la troisième version, mais probablement la plupart des exercices sont les mêmes (Benwit, confirmes-tu ?). […]

Bonjour aurais tu les corrigés de la seconde édition en main? Ca peut être frustrant de ne pas avoir la correction de ces exercices.

Merci d'avance.

[Franck Dernoncourt]

Envoie-moi un email à franck.dernoncourt (at) gmail (dot] com et je t'envoie ça.

[kdmbella]

juste pour ceux qui veulent les corrections voici le lien :
http://www.dunod.com//document/97821..._Solutions.pdf
NB: il s'agit juste de la correction de 80 exercices

[Aspic]

Bonjour,

J'ai aussi flashé sur ce livre mais j'ai peur que ce soit trop dur pour moi.
Je rentre en 4eme année d'ingénieur dans l'informatique et l'électronique. J'ai d'excellente notion de programmation dans la plupart des langages (C, C++, C#, Java, Vb.net, php, html...) mais en algorithmie je suis un peu nul ^^ (c'est à peine si je sais trouvé la complexité d'un algorithme). J'ai un bon niveau mathématique sauf sur la théorie ensembliste (pas de chance, je pense que c'est le plus important)

Je voudrais donc apprendre à travers un livre comment étudier un problème sous tous ses angles afin de trouver le meilleur algo possible. Mon but ultime est d'utiliser ces connaissances pour créer des l'IA pour résoudre des problèmes allant du simple jeu (morpion...) à des problèmes très compliqués (mario subokan, jeu de go...) en passant par les réseaux de neurones, colonies de fourmis...

Voilà, me conseillez vous d'acheter ce livre au risque de ne rien comprendre ?

Merci

[kdmbella]

Envoyé par Aspic

Bonjour,

J'ai aussi flashé sur ce livre mais j'ai peur que ce soit trop dur pour moi.
Je rentre en 4eme année d'ingénieur dans l'informatique et l'électronique. J'ai d'excellente notion de programmation dans la plupart des langages (C, C++, C#, Java, Vb.net, php, html...) mais en algorithmie je suis un peu nul ^^ (c'est à peine si je sais trouvé la complexité d'un algorithme). J'ai un bon niveau mathématique sauf sur la théorie ensembliste (pas de chance, je pense que c'est le plus important)

Je voudrais donc apprendre à travers un livre comment étudier un problème sous tous ses angles afin de trouver le meilleur algo possible. Mon but ultime est d'utiliser ces connaissances pour créer des l'IA pour résoudre des problèmes allant du simple jeu (morpion...) à des problèmes très compliqués (mario subokan, jeu de go...) en passant par les réseaux de neurones, colonies de fourmis...

Voilà, me conseillez vous d'acheter ce livre au risque de ne rien comprendre ?

Merci

a mon avis et à la lecture du résumé de l'éditeur et de la critique de la rédaction c'est pile le livre qu'il vous faut

[oodini]

Je crois que je vais garder ma seconde édition.

La couverture est bien plus sobre. :-)

[Franck Dernoncourt]

Il suffit de commander la version anglais alors http://www.amazon.fr/gp/product/0262033844/ref=as_li_tf_tl?ie=UTF8&tag=patheticcockr-21&linkCode=as2&camp=1642&creative=6746&creativeASIN=0262033844

[kdmbella]

Envoyé par oodini

Je crois que je vais garder ma seconde édition.

La couverture est bien plus sobre. :-)

c'est le contenu qui t'intéresse ou bien c'est la couverture? et puis lorsqu'on publie une nouvelle édition il y a toujours des améliorations des ajouts, et des corrections donc a toi de voir !

[rkade]

Je viens de l'acheter en anglais. Et pour le moment, l'anglais est très simple, un peu technique (mais qui n'a jamais lu de l'anglais technique ? ), et le bouquin bien ficelé.

Je donnerai mon avis sur la globalité du bouquin lorsque j'en aurai un peu plus lu.

[champomy62]

Salut,

J'ai acquis ce livre il y a quelques mois et je vais commencer l'aventure maintenant... Mais avant de commencer j'aurai voulu savoir avec quel langage de programmation vous conseillez de l'aborder ?

Je pensais implémenter le pseudo code en python ? Est-ce possible pour l'ensemble du livre étant donnée les listes chainées ?

Merci,

EDIT : Pour les piles et files, je ne me fais pas de soucis en python étant donné que j'ai trouvé des exemples...

[champomy62]

Je pense que j'ai la réponse à ma question :
Dans la section 10.3 du livre je cite : " Comment pointeurs et objets peuvent ils être implémentés dans un langage qui ne les proposent pas en standards ? Dans cette section, nous verrons deux manières d'implementer des structures de données chainées sans faire appel à un type de pointeur explicite. Nous créerons objets et pointeurs à partir de tableaux et d'indices de tableaux. "

Donc python est ok pour ce bouquin surtout que python propose la notion d'objets.

EDIT : j'ai trouvé aussi les listes chainées pour python sur le net.

Désolé du dérangement.

[Franck Dernoncourt]

Si intéressé, voici comment le livre de référence introduction à l'intelligence artificielle implémente les queues en python (malheureusement à ma connaissance il n'implémente pas les listes chaînées): http://aima.cs.berkeley.edu/python/utils.html (readme).
Bon sinon effectivement il existe beaucoup de librairies en python implémentant les listes chaînées.

Concernant le choix du langage de programmation, à mon avis comme souvent le meilleur choix est le langage que tu maîtrises le mieux
Enfin plutôt de l'impératif (C++, PHP, python, etc) histoire d'être assez proche du pseudocode tout de même.

J'en profite pour indiquer la page Introduction to Algorithms, Third Edition - Supplemental Content sur le site officiel de MIT Press.


Code : http://aima.cs.berkeley.edu/python/utils.py

Code python :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#______________________________________________________________________________
# Queues: Stack, FIFOQueue, PriorityQueue
 
class Queue:
    """Queue is an abstract class/interface. There are three types:
        Stack(): A Last In First Out Queue.
        FIFOQueue(): A First In First Out Queue.
        PriorityQueue(lt): Queue where items are sorted by lt, (default <).
    Each type supports the following methods and functions:
        q.append(item)  -- add an item to the queue
        q.extend(items) -- equivalent to: for item in items: q.append(item)
        q.pop()         -- return the top item from the queue
        len(q)          -- number of items in q (also q.__len())
    Note that isinstance(Stack(), Queue) is false, because we implement stacks
    as lists.  If Python ever gets interfaces, Queue will be an interface."""
 
    def __init__(self): 
        abstract
 
    def extend(self, items):
        for item in items: self.append(item)
 
def Stack():
    """Return an empty list, suitable as a Last-In-First-Out Queue."""
    return []
 
class FIFOQueue(Queue):
    """A First-In-First-Out Queue."""
    def __init__(self):
        self.A = []; self.start = 0
    def append(self, item):
        self.A.append(item)
    def __len__(self):
        return len(self.A) - self.start
    def extend(self, items):
        self.A.extend(items)     
    def pop(self):        
        e = self.A[self.start]
        self.start += 1
        if self.start > 5 and self.start > len(self.A)/2:
            self.A = self.A[self.start:]
            self.start = 0
        return e
 
class PriorityQueue(Queue):
    """A queue in which the minimum (or maximum) element (as determined by f and
    order) is returned first. If order is min, the item with minimum f(x) is
    returned first; if order is max, then it is the item with maximum f(x)."""
    def __init__(self, order=min, f=lambda x: x):
        update(self, A=[], order=order, f=f)
    def append(self, item):
        bisect.insort(self.A, (self.f(item), item))
    def __len__(self):
        return len(self.A)
    def pop(self):
        if self.order == min:
            return self.A.pop(0)[1]
        else:
            return self.A.pop()[1]

[champomy62]

Disons que les langages que je maitrise le mieux actuellement sont le c# et vb.net (plateforme .net en l'état) mais étant passé sur mac, je me suis mis à python depuis 2 ou 3 mois et je trouve que c'est un langage très puissant et souple. (j'ai pas envie de faire du c# sur mac)

Pour information voici un lien pour les listes chainées en python :
http://kkthegeek.wordpress.com/2010/...ion-in-python/

En effet j'aimerai au maximum éviter le c (que je connais) ou c++ pour me concentrer uniquement sur l'algorithmique, et non sur les pointeurs ! lol

[Franck Dernoncourt]

Au passage si intéressé le cours online & gratuit https://www.coursera.org/algo commence bientôt (12th Mar, 2012 normalement - et durera 5 semaines).

Envoyé par champomy62

En effet j'aimerai au maximum éviter le c (que je connais) ou c++ pour me concentrer uniquement sur l'algorithmique, et non sur les pointeurs ! lol

Je comprends

Why Python?

cs101_oo1_02_l_Why-Python - YouTube

cs101_oo1_02_l_Why-Python - YouTube

Envoyé par champomy62

Pour information voici un lien pour les listes chainées en python :
http://kkthegeek.wordpress.com/2010/...ion-in-python/

Merci, cela peut toujours nous être utile ! Perso dans mes souvenirs je n'en ai jamais eu besoin jusqu'à présent car Python est assez haut niveau, mais c'est toujours bon de l'avoir sous la main.

[champomy62]

Pourquoi python ?

Langage de haut niveau qui me permet de me concentrer sur les fonctionnalisées, qui est demandé sur le marché de l'emploi...
Multiplateforme, libre et gratuit. Librairie à foison(aussi important que la qualité de langage), la communauté, beaucoup d'articles...

Et puis python est suffisant performant pour répondre à beaucoup de tâches quotidiennes. Avec toutes les implémentations (pypy, cpython), je pense qu'on peut se faire plaisir. Et si ça coince au niveau des performances, une bonne lib en C et ça roule.

Qu'en pensez vous ?