Algorithmes, notions de base

Description

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