Algorithmes, notions de base

Couverture
Avant-propos
Chapitre 1. Introduction aux algorithmes
	Exactitude
	Utilisation des ressources
	Algorithmes pour les non-informaticiens
	Algorithmes pour les informaticiens
	Lectures complémentaires
Chapitre 2. Décrire et évaluer des algorithmes
	Décrire des algorithmes informatiques
	Caractériser les temps d'exécution
	Invariants de boucle
	Récursion
	Lectures complémentaires
Chapitre 3. Algorithmes de tri et de recherche
	Recherche dichotomique
	Tri par sélection
	Tri par insertion
	Tri par fusion
	Tri rapide
	Récapitulatif
	Lectures complémentaires
Chapitre 4. Minorant pour le tri à battre
	Règles pour le tri
	Minorant pour le tri par comparaison
	Dépasser le minorant avec le tri par dénombrement
	Tri par base
	Lectures complémentaires
Chapitre 5. Graphes orientés acycliques
	Graphes orientés acyliques
	Tri topologique
	Représenter un graphe orienté
	Temps d'exécution du tri topologique
	Chemin critique dans un diagramme PERT
	Plus court chemin dans un graphe orienté acyclique
	Lectures complémentaires
Chapitre 6. Plus courts chemins
	Algorithme de Dijkstra
	Algorithme de Bellman-Ford
	Algorithme de Floyd-Warshall
	Lectures complémentaires
Chapitre 7. Algorithmes sur les chaînes de caractères
	Plus longue sous-séquence commune
	Transformer une chaîne en une autre
	Recherche de chaîne de caractères
	Lectures complémentaires
Chapitre 8. Bases de la cryptographie
	Chiffrement par simple substitution
	Cryptographie à clé symétrique
	Cryptographie à clé publique
	Cryptosystème RSA
	Cryptosystèmes hybrides
	Générer des nombres aléatoires
	Lectures complémentaires
Chapitre 9. Compression de données
	Codages de Huffman
	Télécopieurs
	Compression LZW
	Lectures complémentaires
Chapitre 10. Complexité
	Camions marron
	Classes de complexité N et NP, et NP-complétude
	Problèmes de décision et réductions
	Un problème mère
	Échantillon de problèmes NP-complets
	Stratégies générales
	Perspectives
	Problèmes indécidables
	Conclusion
	Lectures complémentaires
Bibliographie
Index