Bibliographie Amoureuse
de
l'ALGORITHMIQUE
ATTENTION! Ce que
vous visitez est encore un CHANTIER, qui
évolue au rythme d'une actualisation hebdomadaire environ.
Certains tableaux sont incomplets, certaines présentations
absentes, des coquilles non corrigées... Une circulation hypertexte sera
également ajoutée.
Merci de votre patience.
(Edition du 30/06/09)
Avertissement
L'introduction de
nouveaux programmes en Seconde, en dépit de l'apparente (et
très regrettable) absence de conception globale sur
l'ensemble des classes de second cycle des lycées laisse
espérer une évolution notable et l'introduction
d'un enseignement de l'Algorithmique dans les cours de
Mathématiques. La présence
déjà effective d'un peu de théorie des
Graphes en filière ES, l'existence depuis 1996 d'une Option
Informatique en Mathématiques Supérieures MPSI et
Spéciales MP confortent cette idée.
Dès lors, il importe que les
enseignants disposent de
références solides dans ce domaine. Un des buts
de cette bibliographie est de répondre à cette
exigence. On
n'y trouvera pas de "solutions clés en main" pour ces classes,
et la plupart des ouvrages indiqués sont d'un niveau bien
trop élevé pour les classes secondaires: il
s'agit de livres ou de cours pour les enseignants, pas pour leurs
élèves! Mais ils
"donnent le la" sur la manière, le style, montrent
"où il faut aller", et leur esprit pourrait guider celui des
activités algorithmiques plus
élémentaires proposées aux
lycéens.
Ils sont de niveaux
suffisemment variés pour que
chacun y puise selon son temps, son goût, son
évolution. Grosso modo, je me suis limité
à des ouvrages autonomes (self-contained),
lisibles par des étudiants entre la première et
la troisième année de Licence, a fortiori par des
enseignants de lycée dont la référence
universitaire est au moins la licence. Le débutant pourrait
s'effrayer
à bon droit du volume de pages que cela
représente... Si cela est de nature à le
rassurer, je peux dire à titre personnel qu'en autodidacte
de cette discipline, j'ai fréquenté
assidûment beaucoup d'entre eux, mais que je n'ai pas tout
avalé en un jour, et que pour d'autres je n'en ai
étudié qu'une partie, et qu'il me paraît sage de
procéder ainsi. La plupart sont si bien faits
qu'après quelques chapitres incontournables, on peut y faire
son marché de manière sélective...
Un dernier conseil au néophyte: il faut parfois savoir
abandonner un livre, s'il est un peu trop dur au moment
considéré -et, bien sûr,
après avoir fait un minimum d'efforts pour s'accrocher. Et y
revenir un peu plus tard pour le trouver passionnant... ce n'est pas en
Informatique, mais en littérature que j'ai appris cela; j'en
ai fait un principe d'éducation pour ma fille,
dès son plus jeune âge, et, sans me vanter
exagérément, je crois que cela lui a fort bien
réussi et que j'ai contribué à en
faire une grande lectrice et une amoureuse des livres. Il n'y a pour
moi aucune différence avec les livres de science: ce qui
importe, c'est d'avoir le bon ouvrage au bon moment. On peut le
découvrir
seul, c'est parfois fort excitant car cela décuple la joie
de trouver l'élu de son cœur... on y perd aussi
pas mal de temps!
Mon but est donc de vous aider
à faire les
premiers pas pour conquérir plus vite votre autonomie. Et
-mais vous l'aurez deviné- à travers des ouvrages
que j'aime. D'accord? Pas d'accord? Un autre titre à
suggérer? N'hésitez pas à me
faire part de vos suggestions par mél:
ajuhel@nordnet.fr
Mode
d'emploi
À
côté des informations usuelles (Auteur/
Titre/éditeur),
j'ai pensé bien faire en indiquant de plus la langue de
rédaction (
Français
ou
English),
ainsi que le (ou les) langage(s) de programmation
employé(s). Il serait souhaitable que ces informations
colatérales influencent le moins possible le choix d'un
lecteur, mais il peut s'en trouver parmi eux qui y accordent plus
d'importance que moi; à qualité d'ouvrage
égale, cela peut être un critère de
choix pour une entrée en confiance dans le monde
de l'Algorithmique. Malgré le préfixe
Algo,
la douleur ne doit pas être de mise
(1), il est inutile de
s'imposer un environnement qu'on estime hostile; il sera toujours temps
de revenir ensuite vérifier qu'il n'en était rien!
J'ai également
attribué, avec tout ce que cela
comporte de subjectif, un niveau de difficulté, de *
(facile) à *** (demandant un maximum de participation de son
lecteur).
Certains livres
épuisés ont
été, à l'initiative de leurs
généreux auteurs, proposés en
téléchargement (dans la plus grande
légalité, donc). Pour ceux-là, j'ai
donné un lien direct vers le
téléchargement; c'est alors sans risque pour sa
bourse que le lecteur pourra les consulter, "à l'essai", en
quelque sorte. Pour beaucoup d'autres, copier/coller le titre dans un
moteur de recherche permettra souvent d'en avoir une idée
plus précise: table des matières,
chapitre-exemple...J'aurais pu indiquer ces liens; c'est
volontairement que je ne l'ai pas fait, car je voulais que ressortent
au premier coup d'œil ceux qui sont intégralement
téléchargeables. Dans le même esprit,
j'ai incorporé des cours d'universités, grandes
écoles...
(1)
Petit rappel plus sérieux: le mot
Algorithme est une déformation du nom du mathématicien Al-Khowarismi (780-850), latinisé en
Algorismi par les Italiens au
XII-ème siècle, puis francisé en
Algorithme.
Il s'appelait ainsi parce qu'il était originaire de la
région du Khorezm, en Asie Centrale -aujourd'hui, en
Ouzbékistan. [
Voir la page que j'ai dédiée à sa mémoire]
Sur le
Podium...
D'abord,
les 3 must,
les 3 livres dont on peut dire: si je n'ai
qu'un ouvrage de
référence, ce sera celui-là.
Que le débutant ne soit pas rebuté par leur
épaisseur: après un "socle commun" de quelques
chapitres,
la plupart des suivants peuvent être consultés
comme des
entités autonomes (ou par groupes de 2 ou3). Pour prendre
une
comparaison, la carte d'un restaurant gastronomique serait
décourageante s'il s'agissait de tout manger en une seule
fois,
mais ne vous proposez-vous pas, plus raisonnablement, de
l'explorer en plusieurs visites espacées? Le niveau *** ne leur
a
donc été attribué qu'en fonction de
l'ampleur de
leur matière, il serait plus exact de dire: * à
***,
selon ce qu'on lira.
En ce qui concerne le langage, noter
d'emblée
que [CLR] fait la démonstration impeccable du
caractère
accessoire de la question, avec le choix qui est, pour moi, le
meilleur, parce qu'il est intemporel. A contrario, les autres auteurs
ont modifié celui-ci avec les versions successives; on
méditera l'exemple de [SED]: 1-ère
édition en
Pascal, 2-ème en C, 3-ème en Java. Les comparer,
c'est une
autre façon de vous rendre compte que ce ne sont pas les
petites
misères des langages qui décideront du fait que
vous
comprenez un algorithme ou non; les bugs résultant des
traductions peuvent être agaçants, ils ne seront
jamais
des fautes graves de programmation.
Enfin, notez que vous trouvez une
version du
3-ème pour pas un rond, gracieusement mise à
disposition
par les auteurs, si vous n'êtes pas allergique à
la langue
d'Hemingway. Et franchement, dans ce qui suivra, cela vaudra souvent le
petit effort de plus...
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
CLR |
*** |
F |
Pseudo-Code |
CORMEN, LEISERSON, RIVEST, STEIN |
Introduction
à l'Algorithmique |
Dunod |
| 2 |
SED |
*** |
F |
Java |
SEDGEWICK |
Algorithmes
en Java |
Pearson |
| 3 |
AU |
** |
F |
Pascal |
AHO, ULLMAN |
Concepts
Fondamentaux de l'Informatique |
Dunod |
| 3 |
AU |
** |
E |
C |
AHO, ULLMAN |
Foundations
of Computer Science |
(Freeman) |
Approche
douce
It's more fun to
CompUte!
"It's more fun fun to compete!"
C'était écrit (triomphalement!) sur les flippers
qui
disposaient de plusieurs compteurs pour accueillir
simultanément
plusieurs joueurs; on n'hésitera donc pas à
reprendre le
slogan en lui changeant (malicieusement) une lettre. Car on vient
souvent à l'Informatique... à partir des
Mathématiques, par la mise en oeuvre des algorithmes qui
leur
sont spécifiques: quoi de plus naturel que de prolonger le
trop
maigre territoire des résolutions en formules exactes (closed formulas)
par des outils simples, efficaces de résolution
numérique?
Il
n'y a que des avantages! D'une part, équations,
systèmes, équations
différentielles peuvent être approchés
à des niveaux variés, depuis les
plus élémentaires, pour obtenir des
résultats tangibles. D'autre part, le Calcul Scientifique, c'est d'abord le Calcul Numérique, véritable pain quotidien d'un scientifique, d'un ingénieur,
voire d'un économiste,
ensuite, et loin derrière, le Calcul Formel.
(Cette observation pourrait être quantifiée de
manière bien plus précise, en termes de temps de calcul
sur machine, voire de secteurs d'activité.) il ne s'agit pas ici
de dénigrer les
systèmes de Calcul Formel (Maple, Mathematica,
XCas): ils ont
des mérites bien réels! Mais les employer trop
tôt, à mauvais escient, contribue à
donner au lycéen ou à l'étudiant une
vision tronquée, erronnée de ce qu'est le
monde du calcul scientifique, ainsi qu'à occulter les questions
centrales du temps de calcul et de l'organisation des données.
[ENG] est une merveille de
simplicité et de
développement de la curiosité; il n'est
hélas plus
disponible que dans des bibliothèques. [CHA] est une
excellente
référence historique, doublement utile: d'une
part, les
algorithmes y sont minutieusement retracés, avec des
extraits
pas trop longs -juste ce qu'il faut- des articles originaux; d'autre
part, quoiqu'il n'y ait pas une ligne de programme dans l'ouvrage, on y
trouvera beaucoup d'idées d'algorithmes à
écrire
soi-même... probablement la meilleure manière de
se
convaincre que l'algorithmique est la seconde nature du
mathématicien!
On trouvera plus loin,
pour prolonger celle-ci,
une liste d'ouvrages de référence
dédiés
à l'Analyse Numérique, en évitant une
spécialisation trop technique qui n'aurait pas sa place ici..
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
ENG |
* |
F |
Basic (?) |
ENGEL |
Mathématiques Élémentaires
d'un Point de Vue Algorithmique |
Cédic-Nathan |
| 2 |
CHA |
* |
F |
- |
CHABERT & Alias |
Histoire
d'Algorithmes |
Belin |
| 3 |
BPP |
** |
F |
Pascal |
BERSTEL,
PIN, POCCHIOLA |
Mathématiques
et
Informatique |
(Mac
Graw-Hill) |
Mais...pas que
ça, et pas n'importe comment!
Deux remarques s'imposent après ces premiers contacts.
D'une part, se limiter
à l'Analyse
Numérique, champ pourtant vaste et excitant, donnerait une
vision trop réductrice de ce qu'est aujourd'hui
l'Informatique.
Et de fait, on en trouvera fort peu dans les cours ou
traités
d'Algorithmique fondamentale ci-dessous. Entre autres, parce que les
domaines d'application justiciables d'un traitement
automatisé
ont, tout en étant très variés
(Optimisation
Combinatoire, CFAO, Bases de Données, Vision,
Cryptographie...)
engendrés des problèmes nouveaux, dont
l'étude a
dégagé des
fondements
communs, tant dans l'écriture d'algorithmes que dans la
manière de représenter les données
dans un
ordinateur: le cas des tris est sûrement
l'exemple le plus immédiat pour le néophyte.
C'est pourquoi on ira jusqu'à quelques titres dans ces
domaines plus éloignés.
D'autre part,
la
manière est importante:
l'idée qu'il suffit de "bidouiller" un programme est bien
trop
répandue! Or l'organisation méthodique est
rarement
innée, cela s'apprend, et la croissance des programmes rend
indispensables la
clarté, la modularité,
l'évolutivité dans leur
écriture. Il faut donc apprendre aussi à
bien programmer. Les
ouvrages qui suivront s'imposent aussi par leur style:
l'élégance commence avec la clarté et
la simplicité; ils bannissent l'astuce dont certains croient
qu'elle est le must de la programmation; ouvertement, ou dans l'esprit,
ils se réclament d'une programmation orientée
objet. Un petit livre "pour tous" proposait d'emblée
d'apprendre les bonnes manières, sur le ton dont on vous
aurait donné des conseils pour réussir votre
jardin
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
LED
|
* |
F |
|
LEDGARD
|
Proverbes de Programmation
|
Bordas |
Il n'est hélas plus édité, mais vous
trouverez chacun des proverbes (qu'un bref et alerte chapitre
illustrait) en suivant ce lien:
Proverbes
de Ledgard
Son esprit survit, pour ne pas dire se réincarne dans [BEN]
(voir le § "Algorithmique Fondamentale")
Sur la
Toile, ou comment s'initier sans risque pour sa bourse!
Les Cours de l'X...
what else?
Ecole
Polytechnique, aïe, aïe, aïe...
Vraiment, croyez-vous? Eh bien,
pas du tout, car encore en ce début de
XXI-ème siècle, une grande partie de ceux qui y
rentrent sont d'une déplorable, mais réelle
virginité algorithmique -au grand dam de leurs enseignants.
Mais pour celui qui cherche une progression bien pensée, du
b-a-ba à un niveau très solide, ce sera
l'aubaine... Profitez-en,
rien ne dit que ces cours seront éternellement disponibles
en ligne! (L'école édite certains de ses cours,
et, si cela advenait pour une des références
ci-dessous, cela pourrait être une bonne raison pour ne plus
en laisser l'accès gratuit via Internet...)
Les trois premiers sont les plus récents, et correspondent
à la progression actuellement suivie. Vous pouvez
même suivre des amphis en vidéo!
Mais les autres ne sont pas périmés pour autant...
Mais pourquoi pas
ailleurs!
Voici par exemple
des supports de cours très clairs, partant de
zéro: ils
vous expliquent pour commencer qu'en suivant une recette de cuisine,
vous faites, renouvelant l'expérience de M. Jourdain, de
l'Algorithmique sans le savoir... Or, vous réussissez de
bonnes
choses tout en sachant que vous êtes très loin des
grands
chefs, et vous n'êtes pas complexés pour autant?
Vous avez
bien raison! Simplement, on pourrait dire, paraphrasant ce que le
regretté Alain Chapel disait de la cuisine:
L'Informatique, c'est autre chose et beaucoup
plus que des recettes!
et c'est bien pourquoi
il faut travailler avec des gens
expérimentés, puis les grands maîtres...
Algorithmique
Fondamentale
Cette rubrique développe le thème de
l'Algorithmique Générale en une gamme
variée: chacun sait que lors d'une compétition,
il y a, derrière les trois du podium, de talentueux
compétiteurs... Il est évident qu'on pourrait
dresser une liste immense, je l'ai voulue resserrée aux
essentiels, en privilégiant des ouvrages récents,
le plus possible en Français, coçus par leurs
auteurs avec un souci pédagogique sincère et
réussi: il s'agit, à chaque fois, de prendre par
la main un lecteur à qui l'on ne demande aucun
prérequis. Tous obéissent au paradigme
fondamental de Nicklaus WIRTH:
ALGORITHMS + DATA STRUCTURES =
PROGRAMS
Or, lorsqu'on parle
d'algorithmes, on oublie encore trop souvent la question, pourtant
essentielle, de l'organisation des données: le temps et la place sont
indissociables, et, de surcroît, antagonistes -donc peuvent
demander de la part de l'informaticien des compromis soigneusement
réfléchis. On se tromperait lourdement en y
voyant des problèmes datés, voire
archaïques, sous prétexte de la fabuleuse
évolution technologique récente: bien
sûr, on dispose aujourd'hui de bien plus de place; seulement
les applications sont beaucoup plus exigentes, ou, pour le dire
lapidairement: "Plus on en a, plus on en veut".
Les deux premiers livres sont
un peu à part, en ce sens qu'ils procèdent plus
par morceaux choisis que par exposé
systématique: [WIL] réussit, dans un
volume plutôt restreint (moins de 200 pages!), à
faire appréhender les enjeux de la
complexité... de la façon la plus simple qui
soit, le tout avec des illustrations vraiment non triviales, en variant
les champs d'intervention: arithmétique, tris, graphes,
réseaux. [BEN] a réuni et classé de
façon raisonnée des articles écrits
pour une revue: on peut donc les lire indépendamment, mais
le lecteur découvrira vite la cohérence de
l'ensemble, qui est bien plus qu'une juxtaposition. Et, là
encore, la taille est du même ordre que celle de [WIL].
Les ouvrages qui suivent ont
été conçus pour des
étudiants de niveau Bac+1 ou Bac+2, ce qui garantit un
niveau d'accessibilité tout à fait raisonnable:
[CK1], [CK2], [FOU] sont issus d'enseignement en DUT, [ALB] de celui de
l'Option Informatique en Classes Préparatoires. [VEI],
conçu pour un Premier Cycle Universitaire, offre
l'originalité d'une triple approche: algorithmes abstraits,
programmation impérative (C) et fonctionnelle (Caml). Ils
illustrent aussi "ce qui attend" les lycéens au
delà de leur baccalauréat, ce qui peut contribuer
à mieux orienter leur formation algorithmique, dans le
respect des programmes -ce n'est en rien antinomique. On notera enfin
le choix déclaré de l'approche objet de [FOU] et
[CDA]
Avec [BBC], [FGS], et [AHU], on entre
dans le domaine des ouvrages à la fois progressifs et
traités de référence, comme ceux de
notre podium -avouons-le, ils l'ont raté de peu! D'ailleurs,
[AHU] préfigure [AU]...étonnant, non? On en
tirera donc un grand profit sans pour autant pratiquer une
lecture exhaustive; prenons pour exemple [BBC], puisque vous pouvez le
consulter librement. La lecture des chapitres 1 à 3 donnera
les bases indispensables; on pourra ultérieurement la
compléter par la lecture séparée des
chapitres 4, 5, et 10... on aura alors appris beaucoup de choses, selon
un rythme librement choisi, en ne profitant pourtant que d'une
moitié de l'ouvrage!
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
WIL |
* |
F |
Pseudo-Code |
WILF |
Algorithmes
et Complexité |
Masson |
| 2 |
WIL |
* |
E |
Pseudo-Code |
WILF |
Algorithms
and Complexity |
(Prentice-Hall) |
| 3 |
BEN |
* |
E |
Pseudo-Code |
BENTLEY |
Programming
Pearls |
Addison-Wesley |
| 4 |
CK1 |
* |
F |
Pseudo-Code |
COURTIN,
KOWALEWSKI |
Initiation à
l'Algorithmique et aux Structures de Données, t1 |
Dunod |
| 5 |
CK2 |
** |
F |
Pseudo-Code |
COURTIN,
KOWALEWSKI |
Initiation à
l'Algorithmique et aux Structures de Données, t2 |
Dunod |
| 6 |
FOU |
* |
F |
Pseudo-Code |
FOURNIER |
Passeport pour l'Algorithmique
Objet |
Vuibert |
| 7 |
CDA |
** |
F |
Pseudo-Code,
C, Java |
CARDON,
DABANCOURT |
Initiation l'Algorithmique
Objet |
Eyrolles |
| 8 |
GRA |
** |
F |
Pseudo-Code,
Java |
GRANET |
Algorithmique et Programmation en Java |
Dunod |
| 9 |
VEI |
* |
F |
Pseudo-Code,
C, Caml |
VEIGNEAU |
Approches Impérative
et Fonctionnelle de l'Algorithmique |
Springer-Verlag |
| 10 |
ALB |
* |
F |
Caml |
ALBERT
& alias |
Cours et Exercices d'Informatique |
Vuibert |
| 11 |
BBC |
** |
F |
Pseudo-Code |
BEAUQUIER,
BERSTEL, CHRETIENNE |
Elements
d'Algorithmique |
(Masson) |
| 12 |
FGS |
** |
F |
Pascal |
FROIDEVAUX,
GAUDEL, SORIA |
Types de Données et
Algorithmes |
Edisciences |
| 13 |
AHU |
** |
E |
Pascal |
AHO,
HOPCROFT, ULLMAN |
Data Structures and Algorithms |
Addison-Wesley |
Algorithmique
"Appliquée"
Les sujets "plus
spécialisés" que l'on
aborde maintenant sont souvent gratifiés d'un ou plusieurs
chapitres dans les ouvrages d'Algorithmique Fondamentale, et l'exemple
vient de haut, c'est à dire de la première marche
du
podium... Pour fixer les idées, une petite moitié
de
[CLR] est dévolue à un panorama des diverses
rubriques
qui vont suivre.
Codes et Cryptologie
Un des plus
savoureux cocktails de Mathématiques et d'Informatique,
puisqu'il requiert une bonne dose d'Arithmétique... sans
pour autant être nécessairement délicat
à
préparer, car on peut faire énormément
de choses
avec un bagage restreint dans la "Reine des Sciences".: du
lycéen au chercheur, chacun peut y trouver du plaisir.
Les deux
premiers ont l'intérêt d'offrir une vision assez
large,
mêlant Cryptologie et Codes Correcteurs, deux domaines bien
distincts qu'il ne faut pas confondre. Comme le suggère le
***
accordé à [DEM] , qui est au demeurant aussi
clair que
recommandable, le sujet des codes correcteurs requiert vite un bagage
algébrique plus important (Théorie des Corps).
Dans les
titres relatifs à
la Cryptologie, chacun choisira en fonction du critère qu'il
privilégie: élémentarité
agréable
de [BEC], concision de [ZEM] -mais pas au
détriment de
la clarté: cet ouvrage montre beaucoup de choses dans un
petit
volume, encyclopédisme fascinant de [SCH]
-à
déguster en plusieurs fois, évidemment.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
DRTV |
** |
F |
Pseudo-Code |
DUMAS, ROCH, TANNIER, VARRETTE |
Théorie
des Codes: Compression, Cryptage, Correction |
Dunod |
| 2 |
DEM |
*** |
F |
C (Peu!) |
DEMAZURE |
Cours
d'Algèbre |
Cassini |
| 3 |
BEC |
* |
F |
Pascal |
BECKETT |
Introduction
aux Méthodes de la Cryptologie |
Masson |
| 4 |
ZEM |
** |
F |
- |
ZEMOR |
Cours de Cryptographie
|
Cassini |
| 5 |
STI |
** |
F |
Pseudo-Code |
STINSON |
Cryptographie,
Théorie et pratique |
Vuibert |
| 6 |
SCH |
*** |
F |
C |
SCHNEIER |
Cryptographie
Appliquée |
Vuibert |
| 7 |
MOV |
*** |
E |
Pseudo-Code |
MENEZES,
OORSCHOT, VANSTONE |
Handbook of Applied Cryptography |
(CRC Press) |
Graphes
Difficile de ne pas trouver à ce sujet un chapitre, voire
plusieurs, dans les ouvrages fondamentaux! Et je conseille fortement, pour assurer une bonne progressivité, d'intercaler la lecture de leurs chapitres dédiés ([CLR], [SED], [AU], [FGS], [BBC]
notamment), entre les ouvrages * de la liste ci-dessous et les
suivants. C'est un domaine merveilleux, surprenant -ainsi, un
algorithme peut "participer" à une démonstration-
où le bon sens pratique et l'esprit ludique se mêlent aux
preuves rigoureuses, et d'une immense utilité "de terrain";
aussi convient-il de l'aborder avec rigueur et simplicité, en
reportant l'étude des traités les plus abstraits lorsque
le besoin de compléments théoriques se fera sentir.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
TAN |
* |
F |
Pseudo-Code |
TANGENTE, Hors Série n°12
(LEHNING, RITTAUD & alias) |
Les Graphes, de la Théorie des Jeux à l'Intelligence Artificielle |
|
| 2 |
COR |
* |
F |
Pseudo-Code |
COGIS, ROBERT |
Théorie
des Graphes: Problèmes,
Théorèmes, Algorithmes |
Vuibert |
| 3 |
ROU |
* |
F |
|
ROUX |
Initiation à la Théorie des Graphes |
Ellipses |
| 4 |
DHL |
* |
F |
|
DROESBEKE, HALLIN, LEFEBVRE
|
Les Graphes par l'Exemple |
Ellipses |
| 5 |
LPS
|
**
|
F
|
Pseudo-Code,
Delphi |
LACOMME, PRINS, SEVAUX |
Algorithmes
de Graphes |
Eyrolles |
| 6 |
GIB |
** |
E |
Pseudo-Code |
GIBBONS |
Algorithmic Graph Theory |
Cambridge |
| 7 |
PRS |
** |
E |
Pseudo-Code |
PRÖMEL, STEGER |
The Steiner Tree Problem |
Vieweg |
| 8 |
JUN |
** |
E |
Pseudo-Code |
JUNGNICKEL |
Graphs, Networks and Algorithms |
Springer-Verlag |
| 9 |
BOL |
*** |
E |
- |
BOLLOBAS
|
Modern
Graph Theory
|
Springer-Verlag |
| 10 |
DIE |
*** |
E |
- |
DIESTEL |
Graph Theory |
Springer-Verlag |
Il est
devenu presque banal de dire que le Web est un graphe! Il parait donc
opportun de présenter une petite section à ce sujet, car
si les ouvrages qui traitent du fonctionnement de réseaux sont
amenés à aborder des sujets très variés,
chacun recelle une partie, plus ou moins étendue,
dédiée aux algorithmes de routage, qui sont des
applications directes des algorithmes de graphes. Sauf que... ce
doivent être des
algorithmes distribués (on ne peut pas exécuter le programme dans un serveur
Big Brother central,
il doit être réparti dans le réseau), ce qui peut
modifier complétement la hiérarchie usuelle des
algorithmes.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
KUR
|
** |
F |
Pseudo-Code |
KUROSE, ROSS
|
Analyse Structurée des Réseaux
|
Pearson |
| 2 |
HUI
|
***
|
E
|
Pseudo-Code
|
HUITEMA
|
Routing on the Internet
|
Prentice-Hall |
| 3 |
BON
|
** |
E |
|
BONATO
|
A
Course on the Web Graph
|
AMS |
Géométrie
Algorithmique
Ce deuxième
cocktail mélange Informatique et
Géométrie. Le
domaine est foisonnant, et les motivations de l'Infographie conduisent
vers de nouvelles façons d'appréhender courbes et
surfaces (les paramétrages les plus utiles à
l'informaticien ne sont pas nécessairement ceux qui avaient
auparavant la faveur des géomètres), quand ce
n'est pas
à réhabiliter pour un essor triomphal
des objets et
méthodes que certains se plaisaient à dire
obsolètes (Géométrie Projective,
Quadriques,
Cyclides de Dupin!). C'est dire combien introduire
de l'Algorithmique dans l'Enseignement Secondaire au
détriment
de la Géométrie est un contresens absolu
qui
laisse perplexe quant à la vision d'ensemble des concepteurs
de
programmes. Espérons qu'ils entr'ouvrent un jour l'un des
ouvrages ci-dessous...
[MAL] et [ROG] ont
été conçus
pour des étudiants de première (ou
deuxième)
année, les prérequis sont vraiment minimaux. Du
second,
un peu ancien (1997) on oubliera les organigrammes (plutôt
datés!) pour lire les algorithmes clairs qui sont les
fondamentaux du sujet, toujours d'actualité.
Avec [ORO] et
[BKOS], le niveau s'élève évidemment
progressivement, pas en termes de prérequis, mais
d'attention
demandée au lecteur; [BKOS] a
l'originalité de
partir de problèmes concrets (un chapitre par
problème,
donc une certaine indépendance), rapidement
"épurés" pour aller vers l'algorithme
associé, et
qui doute de l'utilité des diverses structures de
données
est inviter à le feuilleter!
David Salomon est, à mon
sens, une
espèce de magicien qui nous livre trois ouvrages
à la
fois plaisants et instructifs, de ces livres qui donnent envie de les
dévorer; le fait de ne pas avoir de familiarité
particulière avec Mathematica n'empêchera
aucunement de
les apprécier. [FVD] reste un sommet du
genre, mais de
nouveaux ouvrages de qualité apparaissent
régulièrement...
Il serait injuste de ne pas mentionner,
dans cette
revue d'une Géométrie revisitée par
l'Informatique, le nom et les apports de Pierre Bézier.
D'autant
que les courbes de Bézier peuvent être
abordées
dès le lycée... et jusqu'à la
recherche! On a donc
ajouté, quoiqu'il ne contienne pas de programmes, un ouvrage
entièrement dédié au sujet:
[DEP], en
complément aux chapitres que leur consacrent [SA1]
et [SA2].
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
MAL
|
* |
F |
C
|
MALGOUYRES
|
Algorithmes
pour la Synthèse d'Images et l'Animation 3D
|
Dunod |
| 2 |
ROG |
* |
F |
Pseudo-Code |
ROGERS |
Algorithmes pour l'Infographie |
Edisciences |
| 3 |
ORO |
** |
E |
C |
O'ROURKE |
Computational Geometry in C |
Cambridge |
| 4 |
BKOS |
*** |
E |
Pseudo-Code |
De BERG,
Van KREVELD, OVERMARS, SCHWARZKOPF |
Computational Geometry |
Springer-Verlag |
| 5 |
DEP |
** |
F |
- |
DEMENGEL,
POUGET |
Modèles de
Bézier, des B-Splines et des NURBS |
Ellipses |
| 6 |
SAL1
|
**
|
E
|
Pseudo-Code
|
SALOMON
|
Computer
Graphics and Geometric Modeling
|
Springer-Verlag |
| 7 |
SAL2 |
** |
E |
Mathematica |
SALOMON |
Curves and Surfaces for Computer
Graphics |
Springer-Verlag |
| 8 |
SAL3 |
** |
E |
Mathematica |
SALOMON |
Transformations and Projections
in Computer Graphics |
Springer-Verlag |
| 9 |
FVD |
*** |
E |
C |
FOLEY, VAN
DAM |
Computer Graphics |
Addison
Wesley |
Algorithmique du texte
et Compression
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
NEL
|
** |
F |
C |
NELSON
|
La Compression de
Données
|
Dunod |
| 2 |
CHL
|
**
|
F
|
Pseudo-Code
|
CROCHEMORE, HANCART, LECROQ
|
Algorithmique
du texte
|
Vuibert |
| 3 |
SAL4
|
*** |
E |
|
SALOMON |
Data Compression |
Springer-Verlag |
Intelligence
Artificielle
Les modes sont
toujours injustes: une expression fleurit, fait fureur, puis passe pour
ringarde... sans qu'il y ait beaucoup de rationnalité dans
tout
cela. En dépit des vicissitudes, espoirs,
déceptions et
recadrages, un ensemble de techniques algorithmiques diverses, mais
ayant fait la preuve de leur efficacité ([DPST] fournit des
études de cas issues du monde réel) peuvent se
regrouper
sous cette bannière. Un de leur points communs est souvent
de
puiser l'idée de leur méthode dans une analogie
extérieure: Physique (recuit simulé), Biologie
(algorithmes génétiques), "Sociale" (colonies de
fourmis); c'est pourquoi on les dénomme aussi heuristiques.
Le sujet peut paraître
éloigné
de l'algorithmique de base; mais d'une part il en constitue une
application et une illustration originale, d'autre part bon nombre de
ces techniques peuvent être abordées de
façon
relativement élémentaire -et autonome. On s'est
donc
limité à deux références
introductives et
un ouvrage [RUN] faisant un point relativement
exhaustif sur
l'état de l'art. Les réseaux de neurones sont un
peu
à part, mais constituent un champ abordable à un
niveau
élémentaire.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
DPST
|
** |
F |
Pseudo-Code |
DREO, PETROWSKI, SIARRY, TAILLARD
|
Métaheuristiques pour
l'Optimisation Difficile
|
Eyrolles
|
| 2 |
NEG
|
**
|
E
|
Pseudo-Code
|
NEGNEVITSKY
|
Artificial
Intelligence
|
Addison
Wesley |
| 3 |
DRE |
** |
F |
Pseudo-Code,
Delphi |
DREYFUS |
Réseaux de Neurones |
Eyrolles |
| 4 |
RUN |
*** |
E |
Pseudo-Code |
RUSSEL,
NORWIG |
Artificial Intelligence: a
Modern Approach |
Prentice
Hall |
Algorithmique
en Analyse Numérique
Ce sont des
références, mais
destinées à
un lecteur
n'ayant aucune connaissance particulière dans
ce domaine
spécifique; on y trouvera les principes
mathématiques,
mais souvent pas une ligne de programme: le fondement
mathématique des algorithmes y est décrit avec
suffisamment de précision pour que la traduction soit
facile.
Sauf mention explicite dans le titre (
[DEM], [LT1], [LT2]) , ils présentent un
panorama dans divers "secteurs".
Les deux ouvrages Américains
[HAM], [ACT]
méritent une mention spéciale par leur
simplicité
d'approche, l'indépendance des chapitres, la
qualité des
exemples et par dessus tout un style léger: la profondeur
dégagée de toute technicité. L'exergue
de [HAM] est à elle seule un sujet de
méditation qui
donne le ton:
"The purpose of Computing is
Insight, not Numbers"
[HHU1] et [HHU2]
sont
à remarquer par des programmes alternativement
rédigés pour un logiciel dédié au calcul
numérique et dans un dans un langage de calcul
formel. [LT1]
et [LT2]
montrent -si besoin était- tout ce que l'on peut
faire de non trivial avec des boucles et des tableaux... mais, par
définition, dans un domaine très typé,
encore loin de l'enseignement secondaire. (excellent au niveau L1-L2 ou
Classes Préparatoires). Par contre, les
équations différentielles peuvent être
abordées numériquement avec fruit "dès
le plus jeune âge": rien n'est plus simple ni plus
géométrique que la méthode d''Euler,
et l'approche qualitative procure des émotions certaines et
des questionnements fructueux!
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
BREZ |
* |
F |
|
BREZINSKI |
Algorithmique Numérique |
Ellipses |
| 2 |
THE |
* |
F |
Pseudo-Code |
THEODOR |
Initiation
à l'Analyse Numérique |
ESI |
| 3 |
DEM |
* |
F |
- |
DEMAILLY |
Analyse Numérique et
Équations Différentielles |
PUG |
| 4 |
GUI |
** |
F |
C (site
compagnon) |
GUILPIN |
Manuel de Calcul
Numérique Appliqué |
EDP
Sciences |
| 5 |
HAM |
* |
E |
- |
HAMMING |
Numerical Methods for Scientists
and Engineers |
Dover |
| 6 |
ACT |
** |
E |
- |
ACTON |
Numerical Methods That (usually)
Work |
MAA |
| 7 |
HHO |
** |
E |
- |
HÄMMERLIN,
HOFFMANN |
Numerical Methods |
Springer-Verlag |
| 8 |
LT1 |
** |
F |
Pseudo-Code |
LASCAUX,
THEODOR |
Analyse Numérique
Matricielle Appliquée à l'Art de
l'Ingénieur, tome
1 |
Dunod |
| 9 |
LT2 |
** |
F |
Pseudo-Code |
LASCAUX,
THEODOR |
Analyse Numérique Matricielle Appliquée
à l'Art de l'Ingénieur, tome
2 |
Dunod |
| 10 |
HHU1 |
** |
F |
Maple,
Matlab |
HUBERT,
HUBBARD |
Manuel de Calcul Scientifique,
tome1: Equations Algébriques |
Vuibert |
| 11 |
HHU2 |
** |
F |
Maple,
Matlab |
HUBERT,
HUBBARD |
Manuel de Calcul
Scientifique , tome 2: Equations Différentielles |
Vuibert |
Algorithmique
Algébrique et Calcul Formel
Du Calcul Formel pour
Comprendre les Mathématiques...
Excellents outils pour
les Mathématiques -on l'a déjà dit-
ces logiciels peuvent évidemment être
employés pour rédiger des programmes
élémentaires, tout en proposant des sorties
graphiques plus ou moins agréables. Par contre, la multitude
de fonctions disponibles laisse souvent perplexe celui qui fait ses
premiers pas... C'est là l''intérêt des
ouvrages ci-dessous, conçus pour guider le lecteur
vers une utilisation efficace tout en limitant et en organisant les
bases à mémoriser (Mais, soyons franc, il faut de
toute façon beaucoup travailler avec l'aide en ligne du
logociel et ses exemples). Parce qu'ils partent tous de
zéro, nous leur avons attribué le nieau *, mais
de nombreuses illustrations seront plutôt de niveau **.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
COT |
* |
F |
Maple |
CORNIL,
TESTUD |
Maple V Release 4 |
Springer-Verlag |
| 2 |
DUG |
*
|
F
|
Maple |
DUMAS,
GOURDON
|
Maple,
Son bon Usage en Mathématiques |
Springer-Verlag |
| 3 |
GSZ |
* |
F |
Maple |
GOMEZ,
SALVY, ZIMMERMANN |
Calcul Formel: Mode d'Emploi |
(Masson) |
| 4 |
HEC |
* |
E |
Maple |
HECK
|
Introduction to Maple |
Springer-Verlag |
| 5 |
ABB |
* |
E |
Mathematica |
ABELL,
BRASELTON
|
Mathematica by Example |
Academic
Press |
| 6 |
BLW |
* |
E |
Mathematica |
BLACHMAN,
WILLIAMS |
Mathematica: a Practical Approach |
Prentice-Hall |
| 7 |
WGK |
* |
E |
Mathematica |
WELLIN,
GAYLORD, KAMIN |
An Introduction to Programming with
Mathematica |
Cambridge |
A noter, 1: De
larges extraits de [COT], [DUG], et [HEC] pour
Maple, de [ABB] et
[WGK] pour
Mathematica,
sont consultables en ligne, via GoogleBooks. Il y a de quoi se faire
une idée...
A noter, 2: Maple est cher...
mais il est possible de se procurer gtratuitement une ancienne version,
bien suffisante pour commencer,
sur
le site Dynamath.
Des Mathématiques pour
Comprendre le Calcul Formel...
Pour comprendre ce que
manipule un système de calcul formel,
et comment il le manipule, il faut s'être initié
aux structures de données (un peu), et à
l'Algèbre, d'un point de vue algorithmique... beaucoup.
C'est pourquoi on a placé ici le très riche
[NAQ], quoiqu'il ne fasse pas de référence
directe à ces systèmes! (Un
Cours
de Calcul Formel, qui s'en inspire... devrait vous convainvre
qu'il est bien à sa place.) Quoiqu'un peu ancien,
[DST] a l'avantage de proposer une introduction au traitement de
l'intégration et des équations
différentielles.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
NAQ |
** |
F |
Ada |
NAUDIN, QUITTÉ
|
Algorithmique
Algébrique |
Masson |
| 2 |
SAU |
*
|
F
|
Maple |
SAUX-PICART
|
Cours
de Calcul Formel: Algorithmes
Fondamentaux |
Ellipses |
| 3 |
SAR |
** |
F |
Maple |
SAUX-PICART,
RANNOU |
Cours de Calcul Formel: Corps Finis,
Systèmes Polynomiaux, Applications |
Ellipses |
| 4 |
DST |
** |
F |
Macsyma |
DAVENPORT,
SIRET, TOURNIER
|
Calcul Formel: Systèmes et
Algorithmes de Manipulations Algébriques |
Masson |
Ces
Merveilleux Fous Calculants et leurs Drôles de Machines
Dans le Ventre de la
Bête...
Comment votre ordinateur
calcule-t-il, qu'il s'agisse d'opérations ordinaires ou de
fonctions évoluées? Les algorithmes "de force
brute" ou
de première naïveté (un exemple pourrait
être:
"sin
x est développable en série entière,
il n'y a plus
qu'à câbler ça dans la machine...")
sont inopérants. Car, de même que le
paramétrage en
cos et sin cher aux Géomètres fait grimacer
l'Informaticien pour tracer un cercle (voir le §: Géométrie
Algorithmique),
le concepteur de puce peut préférer, à
nos bonne
vieilles séries, des algorithmes plus économes,
en temps
comme en espace. Pour les comprendre ou les tester, une
écriture logicielle reste une premère
étape
obligée. Voici, en déclinaison multiple, LA
référence:
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
MUL
|
* |
F |
Pseudo-Code |
MULLER
|
Arithmétique des
Ordinateurs
|
Masson
|
| 1 |
MUL
|
*
|
F
|
Pseudo-Code
|
MULLER |
Arithmétique des
Ordinateurs |
(Masson) |
| 2 |
MUL |
** |
E |
Pseudo-Code,
Maple |
MULLER |
Elementary
Functions, Algorithms and Implementation |
Birkhaüser |
Dans la Tête
de la
Bête...
La théorie
de la Complexité Algorithmique repose sur un
modèle de
machine imaginé par TURING. Un modèle
indémodable... parce qu'il est du type "papier, crayon" et
donne
un fondement intrinsèque à ce qu'est un
algorithme, et
à ce qu'est la difficulté à
résoudre un
problème. [WOL] est certainement la manière la
plus
raisonnable d'aborder ce sujet difficile, dont [DEL] donne une
excellente vision débarassée d'une
technicité que
le débutant non prévenu risque trouver aride: le
sujet
rebute ou passionne, il laisse rarement indifférent! [GIT] a
l'avantage de faire lire le texte original en l'accompagnant de
façon substantielle. Dernier paru, [COR] innove par une
approche
mêlant le sujet à celui des automates cellulaires,
qui a
connu une vogue certaine.
|
Réf |
Niv |
Langue |
Programmes en |
Auteur(s) |
TITRE |
Editeur |
| 1 |
DEL |
* |
F |
- |
DELAHAYE |
Logique, Informatique et
Paradoxes |
Belin |
| 2 |
GIT
|
* |
F |
- |
GIRARD, TURING
|
La Machine de
Turing |
Points-Sciences
|
| 3 |
WOL
|
*
|
F
|
Pseudo-Code
|
WOLPER
|
Introduction à la
Calculabilité
|
Dunod |
| 4 |
COR |
** |
F |
Pseudo-Code |
CORGE |
Machines de Turing et Automates
Cellulaires |
Ellipses |
| 5 |
FBE |
*** |
F |
Pseudo-Code |
FLOYD,
BEIGEL |
Le Langage des Machines |
Vuibert |
Et pour se rafraîchir un peu...