Author(s): François Bergeron
Series: lecture notes
Edition: version 2015-10-20
Year: 2015
Language: French
Commentary: Downloaded from http://www.lacim.uqam.ca/~christo/Mathematiques%20algorithmiques/livre.pdf
Nombres et fonctions numériques
Entiers, et preuves par récurrence
Fonctions
Définitions récursives
Tours de Hanoï (*)
Opérations de base avec les entiers
Polynômes en x
Un problème non résolu (*)
Coefficients binomiaux
Entiers modulo n
Le théorème d'Euler-Fermat (*)
La cryptographie à clé publique (*)
Fractions continues
Nombres de Fibonacci et nombre d'or
Un exemple d'analyse d'algorithme (*)
Calcul approché de zéros (réels) de fonctions
Un joli coup d'oeil (*)
Exercices
Ensembles et fonctions
Introduction
Ensembles
Sous-ensembles
Opérations de base sur les ensembles
Produit cartésien
Relation
Fonctions
Bijections
Injections
Surjections
Compter les éléments d'un ensemble
Ensembles, décidabilité, et complexité d'algorithmes (*)
Exercices
Graphes simples
Introduction
Graphe simple.
Voisinage et degré
Chemin dans un graphe.
Opérations sur les chemins
Cycles hamiltoniens
Composantes connexes
Plus court chemin
Cycles eulériens
Multigraphe
Isomorphisme de graphes
Matrice d'adjacence
Contraction d'arêtes et mineurs (*)
Graphes planaires
Cartes
Coloration de graphes
Chemins dans le graphe ZZ (*)
Exercices
Structures arborescentes
Introduction
Arbres
Arborescences
Arbres binaires
Arbres binaires croissants
Arbres ordonnés
Fonction de stationnement (*)
Forêts
Exercices
Graphes orientés
Introduction
Graphe orienté.
Endofonction
Chemins dans un graphe orienté
Graphes acycliques
Graphes valué
Matrices booléennes
Le demi-anneau tropical
Flot dans un réseau
Chemins et mots (*)
Chaînes de Markov (*)
Ordres (*)
Jeux impartiaux
Exercices
Mots, langages, et automates
Introduction.
Mots
Langages
Grammaires
Automates déterministes
Exercices
Algèbre (*)
Introduction
Algorithme de Gauss-Jordan
Algorithme d'Euclide pour polynômes
Bases de Gröbner
Permutations
Diagrammes de Ferrers
Algorithme RSK
Le problème du mot pour un groupe
Exercices
Appendices
Un soupçon de logique
Axiomatique de la théorie des ensembles
Notions d'algèbre
Polynômes
Groupe et anneaux
Anneaux et idéaux
Anneau Euclidien
Calcul formel
Introduction
Théorie des ensembles et calcul formel
Notations
