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...

Réf Niv Langue Programmes en Auteur(s) TITRE Editeur
1 MOR * F Java MORAIN Les bases de l'Informatique et de la Programmation (Polytechnique)
2 BAM ** F Java BAPTISTE, MARANGET Programmation et Algorithmique (Polytechnique)
3 MST *** F Java,  Pseudo-Code MORAIN, STEYAERT Algorithmes et Programmation: du Séquentiel au Distribué (Polytechnique)
4 CLV * F Pascal, C CORI, LEVY Algorithmes et Programmation (Polytechnique)
5 LEV ** F Java LEVY Informatique Fondamentale (Polytechnique)
6 CHKS ***
(+)
F Pseudo-Code CORI, HANROT, KENYON, STEYAERT  Conception et Analyse d'Algorithmes (Polytechnique)

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...

Réf Niv Langue Programmes en Auteur(s) TITRE Editeur
1 BAL
* F Pseudo-Code, C BALKANSKI Cours IUT d'Orsay, 1-ère année
(IUT Orsay)
2 FIO1
*
F
Java
FIORENZI
Cours IUT d'Orsay, 2-ère année (IUT Orsay)
3 FIO2 ** F Pseudo-Code FIORENZI Cours Ingénieurs Réseaux, 1-ère année (Marne la Vallée)

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...

Pourquoi ne pas aller faire un peu de tourisme Mathématique sur mes pages?