==== Volume 1 ====

Note de l'auteur

Partie 1 : Premiers pas dans le dépannage
__enquête

Chapitre 1 : Concours de résolution de problèmes et de programmation
1.1 Introduction
__1.2 Concours de programmation
1.3 Comment lire ce livre
1.4 Concours de programmation auxquels vous pouvez participer au niveau national
1.5 Conseils pour se préparer à la compétition
1.6 Lectures complémentaires

Chapitre 2 : Aperçu de la résolution de problèmes
__2.1 Introduction
2.2 Processus de résolution de problèmes
__2.3 Stratégies de résolution de problèmes
2.4 Lectures complémentaires

Chapitre 3 : Programmation et débogage
3.1 Introduction : Ne sous-estimez pas l'importance du codage
3.2 Principes pour écrire du bon code
3.3 Erreurs courantes
3.4 Débogage et tests
__3.5 Comprendre la portée des variables
__3.6 Comprendre les types de données réels (facultatif)
3.7 Lectures complémentaires

Partie 2 Analyse de l'algorithme
enquête

Chapitre 4 : Analyse de la complexité temporelle des algorithmes
4.1 Introduction
4.2 Algorithmes à temps linéaire
__4.3 Algorithmes à temps sous-linéaire
__4.4 Algorithme à temps exponentiel
complexité temporelle de 4,5
4.6 Estimation du temps d'exécution
4.7 Classes de complexité algorithmique : P, NP, NP-complet
4.8 Lectures complémentaires

Chapitre 5 Preuve de la validité de l'algorithme
5.1 Introduction
5.2 Induction mathématique et invariants de boucle
__5.3 La loi de la réduction à l'absurde
5.4 Autres technologies
5.5 Lectures complémentaires

Partie 3 : Paradigmes de conception d'algorithmes
__enquête

Chapitre 6 : Résoudre de façon idiote
6.1 Introduction
6.2 Appels récursifs et recherche exhaustive
__6.3 Problème : Pique-nique (Difficulté : Facile, ID du problème : PICNIC)
__6.4 Solution : Pique-nique
__6.5 Problème : Couvrir le tableau (Difficulté : Facile, ID du problème : BOARDCOVER)
__6.6 Solution : Recouvrir le plateau de jeu
6.7 Problème d'optimisation
__6.8 Problème : Synchronisation d’horloge (Difficulté : Moyenne, ID du problème : CLOCKSYNC)
__6.9 Solution : Réglage de l'horloge
6.10 Types de recherche complète fréquemment rencontrés

Chapitre 7 Diviser pour mieux régner
__7.1 Introduction
__7.2 Problème : Inversion d’un quadtree (ID du problème : QUADTREE, Difficulté : Facile)
__7.3 Solution : Inversion d’un arbre quadrangulaire
__7.4 Problème : Couper la clôture (ID du problème : CLÔTURE, Difficulté : Moyenne)
__7.5 Solution : Couper la clôture
__7.6 Problème : Réunion de fans (ID du problème : FANMEEETING, Difficulté : Élevée)
__7.7 Solution : Réunion des fans

Chapitre 8 Programmation dynamique
8.1 Introduction
__8.2 Problème : Wildcard (ID du problème : WILDCARD, Difficulté : Moyenne)
__8.3 Solution : Caractère générique
8.4 Problèmes d'optimisation traditionnels
__8.5 Problème : LIS combiné (ID du problème : JLIS, Difficulté : Facile)
8.6 Solution : SIL combiné
__8.7 Problème : Mémoriser Pi (ID du problème : PI, Difficulté : Facile)
__8.8 Solution : Mémoriser Pi
__8.9 Problème : Quantification (ID du problème : QUANTIZE, Difficulté : Moyenne)
__8.10 Solution : Quantification
8.11 Nombre de cas et probabilité
__8.12 Problème : Pavage asymétrique (ID du problème : ASYMTILING, Difficulté : Facile)
__8.13 Solution : Pavage asymétrique
__8.14 Problème : Polyominos (ID du problème : POLY, Difficulté : Moyenne)
__8.15 Solution : Polyomino
__8.16 Problème : L'évasion du Dr Dunibal (ID du problème : NUMB3RS, Difficulté : Moyenne)
Solution 8.17 : L'évasion du Dr Dunibal

Chapitre 9 Techniques de programmation dynamique
9.1 Calcul de la solution réelle d'un problème d'optimisation
__9.2 Problème : Préparer ses bagages pour un voyage (ID du problème : PACKING, Difficulté : Moyenne)
__9.3 Solution : Préparer ses bagages pour un voyage
__9.4 Problème : Reconnaissance optique de caractères (ID du problème : OCR, Difficulté : Élevée)
__9.5 Solution : Reconnaissance optique de caractères
__9.6 Calcul de la k-ième réponse
__9.7 Problème : La k-ième sous-suite croissante maximale (ID du problème : KLIS, Difficulté : Élevée)
__9.8 Solution : k-ième sous-séquence croissante
__9.9 Problème : Courbe du dragon (ID du problème : DRAGON, Difficulté : Moyenne)
Solution 9.10 : Courbe du dragon
__9.11 Mémorisation pour les entrées non entières
__9.12 Problème : Webbazym (ID du problème : ZIMBABWE, Difficulté : Élevée)
__9.13 Solution : Webbajim
__9.14 Problème : Restauration des données expérimentales (ID du problème : RESTORE, Difficulté : Moyenne)
__9.15 Solution : Récupération des données expérimentales
Jeu combiné __9.16
__9.17 Problème : Jeu de nombres (ID du problème : NUMBERGAME, Difficulté : Facile)
Solution 9.18 : Jeu des nombres
__9.19 Problème : Jeu de blocs (ID du problème : BLOCKGAME, Difficulté : Moyenne)
Solution 9.20 : Jeu de blocs
__9.21 Programmation dynamique itérative
__9.22 Problème : Tapis roulant à sushis (ID du problème : SUSHI, Difficulté : Moyenne)
Solution 9.23 : Sushi sur tapis roulant
__9.24 Problème : Génie (ID du problème : GENIUS, Difficulté : Moyenne)
__9.25 Solution : Génial
__9.26 Lectures complémentaires

Chapitre 10 : La loi de l'avidité
__10.1 Introduction
__10.2 Problème : Réchauffer une boîte à lunch (ID du problème : LUNCHBOX, Difficulté : Facile)
__10.3 Solution : Réchauffer une boîte à lunch
__10.4 Problème : Assemblage de chaînes de caractères (ID du problème : STRJOIN, Difficulté : Moyenne)
__10.5 Solution : Concaténation de chaînes de caractères
__10.6 Problème : Minas Anor (ID du problème : MINASTIRITH, Difficulté : Élevée)
__10.7 Solution : Minas Anor

Chapitre 11 Exploration combinatoire
__11.1 Introduction
11.2 Techniques de recherche combinatoire
__11.3 Problème : Couverture du plateau 2 (ID du problème : BOARDCOVER2, Difficulté : Facile)
__11.4 Solution : Couvrir le plateau de jeu 2
__11.5 Problème : Amis souffrant d’allergies graves (ID du problème : ALLERGIE, Difficulté : Moyenne)
__11.6 Solution : Amis souffrant d'allergies graves
__11.7 Problème : Kakuro (ID du problème : KAKURO2, Difficulté : Moyenne)
__11.8 Solution : Kakuro
__11.9 Lectures complémentaires

Chapitre 12 : Transformer les problèmes d’optimisation en problèmes de décision
__12.1 Introduction
__12.2 Problème : Base antarctique (ID du problème : ARCTIC, Difficulté : Facile)
__12.3 Solution : Base antarctique
__12.4 Problème : Voyage au Canada (ID du problème : CANADATRIP, Difficulté : Moyenne)
__12.5 Solution : Voyager au Canada
__12.6 Problème : Abandon d’un cours (ID du problème : WITHDRAWAL, Difficulté : Élevée)
__12.7 Solution : Retrait du cours

Partie 4 : Algorithmes célèbres
__enquête

Chapitre 13 Analyse numérique
__13.1 Introduction
__13.2 Dichotomie
__13.3 Problème : Augmenter le taux de victoire (ID du problème : RATIO, Difficulté : Facile)
__13.4 Solution : Augmenter les chances de gagner
__13.5 Recherche tripartite
__13.6 Problème : Fossiles de pollen (ID du problème : FOSSILE, Difficulté : Élevée)
__13.7 Solution : Fossile de pollen
__13.8 Autres sujets

Chapitre 14 Théorie des nombres
__14.1 Introduction
__14.2 nombres premiers
__14.3 Problème : Mot de passe 486 (ID du problème : PASS486, Difficulté : Moyenne)
__14.4 Solution : Mot de passe 486
__14.5 Algorithme d'Euclide
__14.6 Problème : Potion magique (ID du problème : POTION, Difficulté : Moyenne)
__14.7 Solution : Potion magique
__14.8 Opérations modulaires
__14.9 Lectures complémentaires (facultatives)

Chapitre 15 Géométrie algorithmique
__15.1 Introduction
__15.2 Outils de géométrie algorithmique
15.3 Intersection, distance et aire
__15.4 Problème : Simulation de flipper (ID du problème : PINBALL, Difficulté : Élevée)
Solution 15.5 : Simulation de flipper
__15.6 Polygon
__15.7 Problème : L’Île au trésor (ID du problème : TRÉSOR, Difficulté : Élevée)
__15.8 Solution : L'Île au Trésor
__15.9 Problème : Intello ou pas intello ? (ID du problème : NERDS, Difficulté : Moyenne)
__15.10 Solution : Intello ou pas ?
__15.11 Modèles de conception d'algorithmes de géométrie algorithmique
__15.12 Erreurs courantes et points de vigilance
__15.13 Lectures complémentaires

==== Volume 2 ====

Partie 5 : Structures de données de base
__enquête

Chapitre 16 Masque de bits
__16.1 Introduction
__16.2 Implémentation d'ensembles à l'aide de masques de bits
__16.3 Exemple d'application de masque de bits
__16.4 Problème : Semestre de remise des diplômes (ID du problème : REMISE DES DIPLÔMES, Difficulté : Moyenne)
__16.5 Solution : Semestre de remise des diplômes
__16.6 Lectures complémentaires

Chapitre 17 Somme partielle
__17.1 Introduction
__17.2 Problème : Poupée de Noël (ID du problème : NOËL, Difficulté : Moyenne)
__17.3 Solution : Poupée de Noël
17.4 Études complémentaires

Chapitre 18 Structures de données linéaires
18.1 Introduction
__18.2 Tableaux dynamiques
__18.3 Liste chaînée
18.4 Comparaison des tableaux dynamiques et des listes chaînées
__18.5 Problème : Problème de Josèphe (Identifiant du problème : JOSEPHUS, Difficulté : Facile)
__18.6 Solution : Problème de Josèphe
18.7 Lectures complémentaires

Chapitre 19 : Files d’attente, piles et paquets
__19.1 Introduction
__19.2 Implémentation des files d'attente, des piles et des paquets
__19.3 Utilisation des piles et des files d'attente
__19.4 Problème : Parenthèses mal appariées (ID du problème : BRACKETS2, Difficulté : Facile)
__19.5 Solution : Parenthèses mal appariées
__19.6 Problème : Analyse des signaux extraterrestres (Identifiant du problème : ITES, Difficulté : Moyenne)
__19.7 Solution : Analyse des signaux extraterrestres

chaîne de 20 caractères
__20.1 Introduction
__20.2 Recherche de chaînes
__20.3 Problème : Le coffre-fort de Jaeha (ID du problème : JAEHASAFE, Difficulté : Moyenne)
__20.4 Solution : Le coffre-fort de Jaeha
Tableau de suffixes __20.5
__20.6 Problème : Habitudes (ID du problème : HABIT, Difficulté : Moyenne)
__20.7 Solution : Habitudes
__20.8 Lectures complémentaires

Partie 6 Arbre
__enquête

Chapitre 21 : Implémentation et parcours de l'arbre
__21.1 Introduction
__21.2 Parcours d'arbre
__21.3 Problème : Modification de l’ordre de parcours de l’arbre (ID du problème : TRAVERSAL, Difficulté : Facile)
__21.4 Solution : Modification de l’ordre de parcours de l’arbre
__21.5 Problème : Forteresse (ID du problème : FORTERESSE, Difficulté : Moyenne)
__21.6 Solution : Forteresse

Chapitre 22 Arbres binaires de recherche
__22.1 Introduction
__22.2 Définition et manipulation des arbres binaires de recherche
__22.3 Analyse de la complexité temporelle et arbres de recherche binaire équilibrés
__22.4 Problème : Intello ou pas Intello ? 2 (ID du problème : NERD2, Difficulté : Moyenne)
__22.5 Solution : Intello ou pas intello ? 2
__22.6 Implémentation d'un arbre binaire de recherche équilibré : Voyage
__22.7 Problème : Inversion du tri par insertion (ID du problème : INSERTION, Difficulté : Moyenne)
__22.8 Solution : Tri par insertion inversé

Chapitre 23 : Files d’attente prioritaires et tas
__23.1 Introduction
__23.2 Définition et implémentation du tas
__23.3 Problème : Changement de médiane (ID du problème : RUNNINGMEDIAN, Difficulté : Facile)
__23.4 Solution : Modification des valeurs intermédiaires

Arbre d'intervalles à 24 chapitres
__24.1 Arbre d'intervalles : Répondre aux questions sur les intervalles
__24.2 Problème : Sentier de randonnée (ID du problème : MORDOR, Difficulté : Moyenne)
__24.3 Solution : Sentier de randonnée
__24.4 Problème : Exploration de l’arbre généalogique (ID du problème : FAMILYTREE, Difficulté : Élevée)
__24.5 Solution : Explorer la généalogie
__24.6 Arbre de Fenwick : Sommes d’intervalles rapides et simples
__24.7 Problème : Mesure du temps de tri par insertion (ID du problème : MEASURETIME, Difficulté : Moyenne)
__24.8 Solution : Mesure du temps de tri par insertion

Chapitre 25 Ensembles mutuellement exclusifs
__25.1 Introduction
__25.2 Problème : Guerre des éditeurs (ID du problème : EDITORWARS, Difficulté : Moyenne)
__25.3 Solution : Guerre des éditeurs

Chapitre 26 Essayez
__26.1 Introduction
__26.2 Problème : Au revoir, et merci pour le poisson ! (ID du problème : SOLONG, Difficulté : Moyenne)
__26.3 Solution : Au revoir, et merci pour le poisson !
__26.4 Recherche de plusieurs chaînes à l'aide d'un trie
__26.5 Problème : Terminator de sécurité (ID du problème : NH, Difficulté : Élevée)
__26.6 Solution : Terminator de sécurité

Graphique de la partie 7
__enquête

Chapitre 27 : Représentation et définition des graphes
__27.1 Introduction
__27.2 Exemple d'utilisation de graphiques
__27.3 Structures de graphes implicites
__27.4 Comment représenter des graphiques

Chapitre 28 : Recherche en profondeur d’abord dans les graphes
__28.1 Introduction
__28.2 Problème : Dictionnaire ancien (ID du problème : DICTIONNAIRE, Difficulté : Facile)
__28.3 Explication : Dictionnaire des langues anciennes
__28.4 Circuit d'Euler
__28.5 Problème : Chaîne de mots (ID du problème : WORDCHAIN, Difficulté : Facile)
__28.6 Solution : Jeu final à limite de mots
__28.7 Fondements théoriques et applications
__28.8 Problème : Installation d’une caméra de surveillance (ID du problème : GALLERY, Difficulté : Moyenne)
__28.9 Solution : Installation d'une caméra de surveillance
__28.10 Problème : Attribution de salles de réunion (ID du problème : MEETINGROOM, Difficulté : Élevée)
__28.11 Solution : Attribution de la salle de conférence

Chapitre 29 : Recherche en largeur dans les graphes
__29.1 Introduction
__29.2 Problème : Jeu de tri (ID du problème : SORTGAME, Difficulté : Moyenne)
__29.3 Solution : Jeu de tri
__29.4 Problème : Journée des enfants (ID du problème : CHILDRENDAY, Difficulté : Élevée)
__29.5 Explication : Journée des enfants
__29.6 Stratégie du chemin le plus court
__29.7 Problème : Tours de Hanoï (ID du problème : HANOI4B, Difficulté : Moyenne)
Solution 29.8 : Tour de Hanoï

Chapitre 30 : Algorithme du plus court chemin
__30.1 Introduction
__30.2 Algorithme de Dijkstra pour le plus court chemin
__30.3 Problème : Routage des signaux (ID du problème : ROUTING, Difficulté : Facile)
__30.4 Solution : Routage des signaux
__30.5 Problème : Camion de pompiers (ID du problème : FIRETRUCKS, Difficulté : Moyenne)
__30.6 Solution : Camion de pompiers
__30.7 Problème : Ironman N-Trial (ID du problème : NTHLON, Difficulté : Élevée)
__30.8 Solution : Course Ironman N-Trial
__30.9 Algorithme de Bellman-Ford pour le plus court chemin
__30.10 Problème : Voyage dans le temps (ID du problème : TIMETRIP, Difficulté : Moyenne)
__30.11 Solution : Voyage dans le temps
__30.12 Algorithme de Floyd pour la distance la plus courte entre toutes les paires
__30.13 Problème : Lutte contre la conduite en état d’ivresse (ID du problème : DRUNKEN, Difficulté : Moyenne)
Solution du 30.14 : Lutte contre la conduite en état d’ivresse
__30.15 Problème : Promesses électorales (ID du problème : PROMESSES, Difficulté : Moyenne)
__30.16 Explication : Promesse électorale

Chapitre 31 Arbre couvrant minimal
__31.1 Introduction
__31.2 Algorithme de Kruskal pour l'arbre couvrant minimal
__31.3 Algorithme de l'arbre couvrant minimal de Prim
__31.4 Problème : Réseau local (ID du problème : LAN, Difficulté : Facile)
__31.5 Solution : Réseau à courte portée
__31.6 Problème : Détermination d’un itinéraire (ID du problème : TPATH, Difficulté : Élevée)
__31.7 Solution : Détermination d'un itinéraire

Chapitre 32 Flux du réseau
__32.1 Introduction
__32.2 Algorithme de Ford-Fulkerson
__32.3 Modélisation de réseau
__32.4 Problème : Correction de matchs (ID du problème : MATTFIX, Difficulté : Moyenne)
__32.5 Solution : Trucage de matchs
__32.6 Problème : Projets nationaux (ID du problème : PROJETS, Difficulté : Élevée)
__32.7 Solution : Projet national
__32.8 Appariement bipartite
__32.9 Problème : Évêque (ID du problème : BISHOPS, Difficulté : Moyenne)
__32.10 Solution : Évêque
__32.11 Problème : Poser un piège (ID du problème : TRAPCARD, Difficulté : Élevée)
__32.12 Solution : Tendre un piège
__32.13 À étudier davantage

Ce livre est conçu pour vous aider à apprendre diverses techniques de conception d'algorithmes et de structures de données tout en résolvant des problèmes de compétitions de programmation, et à développer davantage vos compétences en résolution de problèmes.
Chaque chapitre comprend des exercices que les lecteurs peuvent rédiger et corriger eux-mêmes, et chaque exercice est accompagné d'exemples de réponses et d'explications détaillées du processus d'élaboration de la réponse.

Ce que ce livre couvre
Partie 1 : Premiers pas dans le dépannage
Partie 2 Analyse de l'algorithme
Partie 3 : Paradigmes de conception d'algorithmes
Partie 4 : Algorithmes célèbres
Partie 5 : Structures de données de base
Partie 6 Arbre
Graphique de la partie 7

Les errata et le code source sont disponibles sur la page d'accueil de ce livre (http://book.algospot.com).