par Cormen, Thomas H.
Dunod
-
-
Disponible - 518 COR
Etage 3 - Santé, Sciences et Techniques - Sciences
Résumé
Explications du fonctionnement des algorithmes et de leur évaluation. L'ouvrage décrit également comment modéliser un problème de façon à ce qu'il puisse être résolu par ordinateur.
- Éditeur(s)
-
Date
- DL 2013
-
Notes
- La couv. porte en plus : "licence, IUT, écoles d'ingénieurs"
- Bibliogr. p. 220. Index
-
Langues
- Français
- , traduit de : Anglais
-
Description matérielle
- 1 vol. (X-229 p.) : ill., couv. ill. en coul. ; 22 cm
- Collections
- Titre(s) en relation
- Sujet(s)
-
ISBN
- 978-2-10-070151-3
-
Indice
- 518 Calcul et analyse numériques
-
Quatrième de couverture
-
Cet ouvrage s'adresse aux étudiants en informatique et de manière plus large à tous ceux qui veulent comprendre comment les ordinateurs résolvent les problèmes.
Et pourtant ce n'est pas un manuel «classique»...
Son objectif est de vous décrire la manière dont sont conçus les algorithmes, de vous expliquer les méthodes qui permettent de trier les informations ou de raisonner sur des problèmes simples qui peuvent être modélisés à l'aide de structures mathématiques appelées arbres.
Il vous aidera aussi à résoudre des problèmes qui reposent sur des chaînes de texte, vous expliquera les principes de base de la cryptographie et ceux de la compression des données.
Enfin vous comprendrez pourquoi et comment on sait à l'avance que certains problèmes seront longs et difficiles, voire impossibles, à résoudre à l'aide d'ordinateurs.
-
-
Tables des matières
-
Algorithmes
Notions de base
Thomas H. Cormen
Dunod
- Avant-propos VI
- Chapitre 1. Introduction aux algorithmes 1
- Exactitude2
- Utilisation des ressources4
- Algorithmes pour les non-informaticiens6
- Algorithmes pour les informaticiens6
- Lectures complémentaires8
- Chapitre 2. Décrire et évaluer des algorithmes 11
- Décrire des algorithmes informatiques11
- Caractériser les temps d'exécution18
- Invariants de boucle22
- Récursion23
- Lectures complémentaires25
- Chapitre 3. Algorithmes de tri et de recherche 27
- Recherche dichotomique30
- Tri par sélection34
- Tri par insertion37
- Tri par fusion41
- Tri rapide50
- Récapitulatif58
- Lectures complémentaires61
- Chapitre 4. Minorant pour le tri à battre 63
- Règles pour le tri63
- Minorant pour le tri par comparaison64
- Dépasser le minorant avec le tri par dénombrement65
- Tri par base71
- Lectures complémentaires73
- Chapitre 5. Graphes orientés acycliques 75
- Graphes orientés acyliques78
- Tri topologique79
- Représenter un graphe orienté82
- Temps d'exécution du tri topologique84
- Chemin critique dans un diagramme PERT85
- Plus court chemin dans un graphe orienté acyclique89
- Lectures complémentaires93
- Chapitre 6. Plus courts chemins 95
- Algorithme de Dijkstra97
- Algorithme de Bellman-Ford106
- Algorithme de Floyd-Warshall111
- Lectures complémentaires118
- Chapitre 7. Algorithmes sur les chaînes de caractères 121
- Plus longue sous-séquence commune122
- Transformer une chaîne en une autre127
- Recherche de chaîne de caractères135
- Lectures complémentaires142
- Chapitre 8. Bases de la cryptographie 143
- Chiffrement par simple substitution144
- Cryptographie à clé symétrique146
- Cryptographie à clé publique149
- Cryptosystème RSA151
- Cryptosystèmes hybrides160
- Générer des nombres aléatoires160
- Lectures complémentaires161
- Chapitre 9. Compression de données 163
- Codages de Huffman165
- Télécopieurs171
- Compression LZW172
- Lectures complémentaires183
- Chapitre 10. Complexité 185
- Camions marron185
- Classes de complexité N et NP, et NP-complétude189
- Problèmes de décision et réductions190
- Un problème mère194
- Échantillon de problèmes NP-complets195
- Stratégies générales211
- Perspectives214
- Problèmes indécidables216
- Conclusion218
- Lectures complémentaires219
- Bibliographie 220
- Index 221
-
-
Origine de la notice:
- FR-751131015
-
Disponible - 518 COR
Etage 3 - Santé, Sciences et Techniques - Sciences
