\documentclass[10pt,francais]{amsart} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[frenchb]{babel} \usepackage{amsmath,amsfonts,amssymb} \usepackage{ mathabx, stmaryrd } \usepackage{amsthm,fancyhdr} \usepackage[all]{xy} \usepackage{color} \usepackage{pgf,tikz} \usetikzlibrary{arrows} \usepackage{enumitem} \usepackage[colorlinks = true, linkcolor = blue]{hyperref} \usepackage[left=2.5cm, right=3cm, top=2cm, bottom=3cm] {geometry} \usepackage{lmodern} \frenchbsetup{StandardLists=true} \AtBeginDocument{\let\textlabel\label} %A enlever pour ne pas avoir les petits carrés sur les références \pagestyle{plain} \title{Méta-plans pour les leçons d'informatique pour l'agrégation de mathématiques option D} \begin{document} \begin{titlepage} \maketitle \end{titlepage} \newpage \tableofcontents \newpage \section*{Introduction} Voici la liste des mes méta-plans pour les leçons d'informatique de l'option D. Ils contiennent les grandes lignes de ce que je comptais mettre dans mes leçons le jour de l'oral, les références permettant de construire ce plan et deux développements référencés. J'indique pour certaines parties la référence plus ou moins précise d'où je la tire entre crochets. La leçon 920 était mon impasse ; aussi, pas de plan pour celle-ci. J'espère que ce document vous aidera à élaborer vos propres plans ! \section*{901. Structures de données. Exemples et applications.} \textbf{Plan :} \medskip \textbf{Motivation :} Le choix d'une structure de données adaptée au problème algorithmique qu'on se pose peut permettre de faciliter la conception de l'algorithme ou d'améliorer sa complexité (temporelle ou spatiale). \medskip I/Formalisme [\hyperref[bib]{BBC}] \begin{itemize}[label=$\rightarrow$] \item Définition d'un type + types de base : entiers, booléens, tableau, liste (doublement) chaînée \item Définition d'un type de données abstrait \item Comment décrire un type de données abstrait : signature (= sorte et opérations possibles) + préconditions (= domaine de définition des opérations) + axiomes (= prop des opérations) \item Ex : Description d'un dictionnaire \item Rq : Les types abstraits permettent de concevoir des algorithmes en dehors de tout langage de programmation \item Définition : structure de données = type abstrait + implémentation \item Ex : Reprendre celui avec le dictionnaire \end{itemize} \medskip II/Structures linéaires [\hyperref[bib]{FG}] \begin{itemize}[label=$\rightarrow$] \item Ex : Liste : description du type + avantages et inconvénients des différentes implémentations (tableau / liste chaînée) \item Ex : Pile : description de type + implémentations + appli : parcours en profondeur d'un graphe \item Ex : File : description du type + implémentations + appli : parcours en largeur d'un graphe \end{itemize} \medskip III/Structures arborescentes [\hyperref[bib]{FG}] [\hyperref[bib]{Cor}] 1) Graphes \begin{itemize}[label=$\rightarrow$] \item Définition d'un graphe (orienté) + ex vie courante \item Définition d'un graphe par son type + implémentations = matrice d'adjacence, liste d'adjacence, liste des arêtes \item Applis : Floyd-Warshall (matrice d'adjacence), algos de plus courts chemins, Prim... \end{itemize} 2) Arbres \begin{itemize}[label=$\rightarrow$] \item Définition d'un arbre + ex : arbre généalogique, arborescence de fichiers \item Définition arbre binaire par induction / par son type abstrait + implem \item Définition d'un tas + appli : tri par tas \fbox{DEV1} \end{itemize} \medskip IV/Quelques structures adaptées à la recherche 1) ABR \begin{itemize}[label = $\rightarrow$] \item Définition arbre binaire de recherche (ABR) + complexité d'un recherche \item Pb de l'ABR = sa hauteur. D'où les AVL pour équilibrer \item Définition ABR optimal + complexité de la recherche \end{itemize} 2) Tables de hachage \begin{itemize}[label = $\rightarrow$] \item Définition table de hachage, clé, univers \item Définition collisions + résolution par chaînage \item Définition hachage parfait + comment l'obtenir sans prendre trop de mémoire \fbox{DEV2} \item Rq : On peut aussi utiliser une fonction de hachage pour vérifier l'intégrité de données (md5sum) \end{itemize} \begin{itemize}[label = $\rightarrow$] \item On peut aussi parler de la structure Union-find + appli à la recherche d'arbre couvrant minimal avec Kruskal \end{itemize} \medskip ANNEXE : faire plein de dessins ! \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], Beauquier [\hyperref[bib]{BBC}], Froidevaux-Gaudel [\hyperref[bib]{FG}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Hachage parfait [\hyperref[bib]{Cor} p 258-262] \item Complexité du tri par tas [\hyperref[bib]{Cor} p 142-148] \end{itemize} \newpage \section*{902. Diviser pour régner. Exemples et applications.} \textbf{Plan :} \medskip I/Principe 1) Description \begin{itemize}[label=$\rightarrow$] \item C'est un méthode de conception d'algos : on divise le problème en sous problèmes de même nature, on résout récursivement ces sous problèmes (directement s'ils sont suffisamment "petits") puis on combine les solutions \item Ex : Exponentiation rapide \item Ex : Calcul de la hauteur d'un arbre binaire, parcours infixe, préfixe, postfixe des sommets d'un arbre \item Ex : Recherche dichotomique dans un tableau trié \end{itemize} 2) Complexité \begin{itemize}[label=$\rightarrow$] \item Théorème fondamental (= "master theorem") + attention il ne couvre pas tous les cas \item Ex : $T(n) = 2T(\frac{n}{2}) + \Theta(n)$ donne un complexité en $\Theta(nln(n))$ (relation de récurrence courante) \item Ex : Expression de la complexité + complexité pour exponentiation rapide, recherche dichotomique et parcours d'arbres \end{itemize} 3) Limites \begin{itemize}[label=$\rightarrow$] \item Ex : Calcul des termes de la suite de Fibonacci + arbre des appels en annexe. Mauvaises complexités \item Généralisons : Quand les sous problèmes se recoupent, DPR n'est pas idéal ; on se tourne alors vers la programmation dynamique \end{itemize} \medskip II/Deux algorithmes de tri \begin{itemize}[label=$\rightarrow$] \item Tri fusion : entrée, sortie, sous problèmes, algorithme, relation de récurrence pour la complexité et complexité + rq : c'est un tri optimal et il en existe une version en place \item Tri rapide : la même chose mais plus vite, écrire l'algo + modification pour obtenir le tri rapide randomisé \fbox{DEV1} \item Appli (des deux tris) : Visualisation de données, tri des clés dans Dijkstra ou Prim, gestion de files de priorité, utile dans les algos gloutons... \end{itemize} \medskip III/Multiplications en tous genres 1) Produit de nombres \begin{itemize}[label=$\rightarrow$] \item Ex : Produit de nombres par Karatsuba [\hyperref[bib]{Das} p 45] \item Applis : Calcul de produit matriciel, RSA, algos de calcul formel \end{itemize} 2) Produit de matrices \begin{itemize}[label=$\rightarrow$] \item Ex : Algorithme de Strassen \item Appli : Calcul de l'inverse d'une matrice (en utilisant son polynôme minimal), résolution de systèmes linéaire, affichage graphique, algorithme de Floyd-Warshall pour les plus courts chemins, calcul de la fermeture transitive d'un graphe (avec Floyd-Warshall aussi) \end{itemize} 3) Produit de polynômes \begin{itemize}[label = $\rightarrow$] \item Ex : Algorithme FFT \fbox{DEV1} \item Appli : dans une certaines mesure, Berlekamp ! \end{itemize} \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], Dasgupta [\hyperref[bib]{Das}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Analyse du tri rapide randomisé [\hyperref[bib]{Cor} p 166-170 et 158-161] \item FFT [\hyperref[bib]{Cor} p 827] \end{itemize} \newpage \section*{903. Exemples d'algorithmes de tri. Correction et complexité.} \textbf{Idée de défense de plan :} Intérêts de la leçon : pratique (on retrouve un tri dans beaucoup d'algos) + théorique (les algos de tris sont nombreux et variés, utilisent différentes méthodes de conception d'algos) \textbf{Plan :} \medskip I/Le problème du tri \begin{itemize}[label=$\rightarrow$] \item Déf : Enoncé du problème du tri : entrée = une famille $(x_i)_{i \leq n}$ et un ordre total $<$ / sortie = une famille $(x_{\sigma(i)})_i$ triée (cad tel que $in, égalité à zéro \item Prop : Si $P$ et $Q$ sont primitifs récursifs, $P^c$, $P \vee Q$ et $P \wedge Q$ aussi \item Ex : L'égalité et l'inégalité large sont des prédicats primitifs récursifs \item Appli : Schéma if..then..else : Si la condition $P_{if}$ est un prédicat primitif récursif et $f_{then}$ et $f_{else}$ sont primitives récursives alors le schéma if..then..else aussi \end{itemize} 3) Minimisation bornée \begin{itemize}[label=$\rightarrow$] \item Définition minimisation bornée + prop : la minimisation bornée par rapport à un prédicat primitif récursif est primitive récursive \item Ex : La division euclidienne, le min et le modulo sont primitifs récursifs + m|n et le fait d'être premier sont des prédicats primitifs récursifs \end{itemize} 4) Cela ne suffit pas \begin{itemize}[label=$\rightarrow$] \item Prop : L'ensemble des fonctions primitives récursives est dénombrable \item Csqc : Il y a des fonctions de $\mathbb{N}$ dans $\mathbb{N}$ qui ne sont pas primitives récursives \item Ex : La fonction d'Ackermann n'est pas primitive récursive \fbox{DEV1} \end{itemize} \medskip II/Fonctions récursives 1) Construction \begin{itemize}[label=$\rightarrow$] \item Définition prédicat sûr \item Définition minimisation non bornée \item Définition fonction récursive totale \item Rq : Savoir si un prédicat est sûr est indécidable \item Ex : $n \longmapsto$ le plus petit p premier tel que $p > n$ est récursive totale \item Appli : Schéma de la boucle while : si la condition C d'arrêt est un prédicat sûr et h est récursive totale alors le schéma "tant que C faire h" est récursif total \item Définition fonction récursive partielle + ex \end{itemize} 2) Lien avec les machines de Turing \begin{itemize}[label=$\rightarrow$] \item Définition fonction calculable par machine de Turing au sens strict \item Prop : Récursive totale implique calculable au sens strict + réciproque vraie \fbox{DEV2} \item Définition fonction calculable par machine de Turing au sens large \item Prop : Récursive partielle équivaut à être Turing calculable au sens large \item Rq : il existe des fonctions qui ne sont même pas récursives partielles (castor affairé) \end{itemize} \bigskip \textbf{Références :} Wolper [\hyperref[bib]{Wol}] (principalement), Cori-Lascar [\hyperref[bib]{CL2}], Lassaigne-Rougemont [\hyperref[bib]{LdR}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Fonction d'Ackermann [\hyperref[bib]{CL2} p 18] \item Une fonction Turing calculable est primitive récursive [\hyperref[bib]{LdR} p 148] + [\hyperref[bib]{Wol} p 135] \end{itemize} \newpage \section*{913. Machines de Turing. Applications.} \textbf{Plan :} \medskip I/Machines de Turing (= MT) 1) Formalisation \begin{itemize}[label=$\rightarrow$] \item Définition (choix : un seul état initial, et une tête de lecture qui doit bouger à chaque étape) \item Rq : Dessin pour illustrer ce que sont le ruban et la tête de lecture \item Définition MT déterministe \item Définition d'une configuration, étape de calcul, calcul, calcul acceptant \item Définition d'un langage accepté / décidé par une MT \end{itemize} 2) Extensions \begin{itemize}[label=$\rightarrow$] \item Prop : Normalisation \item Prop : Machines à ruban bi-infini, à plusieurs rubans = ça n'apporte rien de plus \item Prop : On peut toujours déterminiser une MT \item Enoncé de la thèse de Church-Turing \end{itemize} \medskip II/Calculabilité 1) R et RE \begin{itemize}[label=$\rightarrow$] \item Rq : Un problème de décision est associé au langage des codages des instances positives \item Définition de R, RE, co-RE + prop : RE $\neq \emptyset$ \item Définition d'un énumérateur + prop : $L \in RE$ ssi il existe un énumérateur pour $L$ \item Prop : Stabilités de R et RE \end{itemize} 2) Décidabilité, indécidabilité \begin{itemize}[label=$\rightarrow$] \item Ex : $L_{\in} = \{ | w \in L(M)\}$ est dans RE mais n'est pas décidable \item Problème de l'arrêt \item Définition fonction calculable \item Définition d'une réduction (calculable) + prop : réduction et décidabilité \item Théorème de Rice \fbox{DEV1} + ex \end{itemize} \medskip III/Complexité en temps 1) Modèle \begin{itemize}[label=$\rightarrow$] \item Définition temps de calcul + comparaison MT déterministes et non déterministes \item Définition de TIME(f(n)) et NTIME(f(n)), de P, NP, EXP... \item Ex de problèmes dans P et NP \item Définition vérificateur en temps polynomial + prop : être dans NP équivaut à avoir un vérificateur polynomial \end{itemize} 2) NP complétude \begin{itemize}[label=$\rightarrow$] \item Définition réduction polynomiale \item Définition NP-difficile, NP-complet \item Théorème de Cook \fbox{DEV2} \end{itemize} \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], Wolper [\hyperref[bib]{Wol}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Théorème de Rice [\hyperref[bib]{Wol} p 150] \item Théorème de Cook [\hyperref[bib]{Car} p 203] \end{itemize} \newpage \section*{914. Décidabilité et indécidabilité. Exemples.} \textbf{Idée de défense de plan :} 10ème problème de Hilbert : existe-t-il un algo qui permette de dire si une équation diophantienne admet une solution ou pas $\rightarrow$ Généralisation : si on a un énoncé mathématique, peut on \textit{décider} (notion qu'on précise ici) s'il est vrai ou pas ? Dans la suite, on remarque que plus une structure est riche, moins on sait dire de choses dessus. \textbf{Plan :} \medskip I/Formalisme [\hyperref[bib]{Car} p 139-160] 1) Machine de Turing (MT) \begin{itemize}[label=$\rightarrow$] \item Définition MT, langage accepté, langage décidé \item Définition de R et de RE \item Prop : $R \subset RE$ + il existe des langages pas dans RE + stabilités de R et RE \end{itemize} 2) Problème \begin{itemize}[label=$\rightarrow$] \item Définition d'un problème, codage d'un problème, langage associé à un problème = langage des codages des instances positives du problème \item Définition d'un problème décidable / indécidable + rq : ça ne dépend pas du codage \item Définition fonction calculable + réduction \item Prop : Si A se réduit à B et A est indécidable alors B aussi \end{itemize} \medskip II/Indécidabilité et MT \begin{itemize}[label=$\rightarrow$] \item Prop : Indécidabilité problème de l'arrêt, problème du mot \item Théorème de Rice \fbox{DEV1} \item Appli : Langage vide est indécidable \end{itemize} \medskip III/Décidabilité et langages rationnels \begin{itemize}[label=$\rightarrow$] \item Liste des problèmes décidables sur les langages rationnels : problème du mot, problème du langage vide, du langage universel, égalité de langage... \item Rq : C'est difficile de trouver un problème indécidable sur les langages rationnels \end{itemize} IV/Décidabilité et indécidabilité : langages algébriques \begin{itemize}[label=$\rightarrow$] \item Prop : Pour les langages algébriques, le problème du langage vide et du mot sont décidables \item Def : Problème de correspondance de POST + POST modifié \item Prop : Ils ont la même classe de décidabilité et POST modifié est indécidable \item Appli : Le problème de l'intersection vide, du langage universel, de l'égalité et de l’ambiguïté sont indécidables sur les langages algébriques [\hyperref[bib]{Car}] \end{itemize} V/Décidabilité et logique [\hyperref[bib]{DNR}] 1) Vocabulaire \begin{itemize}[label=$\rightarrow$] \item On se donne un langage du premier ordre et $\vdash$ un système de déduction correct et complet \item Définition théorie, théorie consistante, théorie complète \item Définition théorie récursive, théorie décidable \item Prop : Une théorie complète, récursive sur un langage dénombrable est décidable \end{itemize} 2) Presburger \begin{itemize}[label=$\rightarrow$] \item Langage de l'arithmétique de Presburger \item Axiomes de la théorie de Presburger \item Décidabilité de Presburger \fbox{DEV2} \end{itemize} 3) Peano \begin{itemize}[label=$\rightarrow$] \item Langage et axiomes de Peano (on rajoute la multiplication à Presburger= \item Théorèmes d'indécidabilité autour de Peano [\hyperref[bib]{DNR} p 126-127] \end{itemize} \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], Wolper [\hyperref[bib]{Wol}], Autebert [\hyperref[bib]{Aut}], [\hyperref[bib]{DNR}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Théorème de Rice [\hyperref[bib]{Wol} p 150] \item Décidabilité de Presburger [\hyperref[bib]{Car} p 178] \end{itemize} \newpage \section*{915. Classes de complexité. Exemples.} \textbf{Plan :} \medskip Intro : S'intéresser à la décidabilité d'un problème ne suffit pas : en pratique un algo n'est utilisable que lorsqu'il s'exécute en temps raisonnable et utilise un espace limité. Rq : On peut passer d'un problème de décision à un problème d'optimisation et inversement : on s'autorise donc à utiliser le terme "problème" pour les deux. A tout problème de décision on associe le langage des instances positives du problème. Cette association permet de confondre problème et langage \medskip I/Machines de Turing et complexité 1) Définitions \begin{itemize}[label=$\rightarrow$] \item Rappel : Langage décidé par MT \item Définition temps / espace de calcul d'une MT M sur $\omega$ \item Définition complexité en temps / espace de M + complexité en temps (n) $\geq$ n \item Rq : Parfois on ne considère pas l'espce pris par l'entrée dans la complexité en espace \item Prop : Lien entre les deux complexités [\hyperref[bib]{Car} p 194] \end{itemize} 2) Influence du modèle sur la complexité temporelle \begin{itemize}[label=$\rightarrow$] \item Théorème d'accélération = permet de négliger les constantes donc d'exprimer la complexité temporelle avec des $O$ \item Prop : Complexité en temps : influence d'un ruban bi-infini / plusieurs bandes \end{itemize} 3) Influence du modèle sur la complexité spatiale \begin{itemize}[label=$\rightarrow$] \item Prop : Complexité spatiale et ruban bi-infini / plusieurs bandes \item Théorème de Savitch \end{itemize} \medskip II/Classes de complexité en temps 1) Définitions \begin{itemize}[label=$\rightarrow$] \item Définition de TIME(f(n)) et NTIME(f(n)) \item Définition de P, NP, EXP, NEXP \item Prop : Les diverses inclusions entre ces classe + attention il y en a plein pour lesquelles on ne sait pas si c'est strict ou pas \end{itemize} 2) Exemples de problèmes dans P \begin{itemize}[label=$\rightarrow$] \item Ex : Problème d'accessibilité dans un graphe (d'où, décider si le langage reconnu par un automate est vide) \item Ex : Tout langage algébrique est dans P (CYK) \item Ex : 2-color et 2-SAT sont dans P \end{itemize} 3) Exemples de problèmes dans NP \begin{itemize}[label=$\rightarrow$] \item Définition d'un vérificateur en temps polynomial \item Prop : Appartenir à NP équivaut à avoir un vérificateur polynomial \item Ex : PVC et cycle hamiltonien sont dans NP \end{itemize} 4) NP-complétude \begin{itemize}[label=$\rightarrow$] \item Définition réduction polynomiale + dessin + prop \item Définition NP-difficile, NP-complet \item Ex : SAT, 3SAT, PVC, 3-color, Cycle hamiltonien sont NP-complets \item Théorème de Cook \fbox{DEV2} \item Confronté à un problème NP-complet, on peut trouver un algo polynomial qui résout un sous problème de celui qu'on considère ou trouver une approximation polynomiale + ex PVCE \fbox{DEV2} \end{itemize} \medskip On peut aussi parler de complexité spatiale \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], Wolper [\hyperref[bib]{Wol}], Cormen [\hyperref[bib]{Cor}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Théorème de Cook [\hyperref[bib]{Car} p 203] \item Problème du voyageur de commerce euclidien [\hyperref[bib]{Cor} p 1023] \end{itemize} \newpage \section*{916. Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Exemples.} \textbf{Plan :} \medskip But : Formaliser les raisonnements mathématiques, encodage de problèmes (coloriage, emploi du temps) \medskip I/Syntaxe \begin{itemize}[label=$\rightarrow$] \item On se donne un ensemble dénombrables de variables + les symboles $(, ) \neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$ \item Définition des formules propositionnelles par induction + ex \item Représentation des formules par un arbre ou un circuit électrique \item Théorème de lecture unique d'où non ambiguïté \item Rq : On peut enlever les parenthèses superflues + ex \end{itemize} \medskip II/Sémantique 1) Valuations \begin{itemize}[label=$\rightarrow$] \item Définition valuation + extension aux formules + tables de vérité (exemple en annexe) \item Définition formules équivalentes + ex $(p \Rightarrow q) \equiv (\neg q \Rightarrow \neg p)$ \item Appli : Système complet de connecteurs + ex $\{\wedge, \neg \}$ \item Définition de la satisfiablité \end{itemize} 2) Formes normales \begin{itemize}[label=$\rightarrow$] \item Définition littéral et clause + ex \item Définition FNC, FND + ex \item Prop : Toute formule est équivalente à une FND ou une FNC \item Rq : Pas d'unicité pour la FNC + expliquer comment on opère la transformation + complexité \item Prop : Transformation de Tseitin \fbox{DEV1} \end{itemize} \medskip III/Satisfiabilité 1) Compacité \begin{itemize}[label=$\rightarrow$] \item Définition : formule valide, tautologie, contradiction, finiment satisfiable \item Théorème de compacité pour la résolution en calcul propositionnel \item Appli : $k$-coloriage (un graphe est 3-coloriable ssi tout sous graphe fini l'est) \item On peut développer ce système de déduction \end{itemize} 2) SAT \begin{itemize}[label=$\rightarrow$] \item Le problème SAT + théorème de Cook \fbox{DEV2} \item Un algo naïf pour SAT, mentionner les SAT solveurs \item Rq : Si on a une FND, SAT se fait en temps linéaire ; si on a une FNC, c'est facile de vérifier la validité de la formule \item Applis : réductions : choisir celle qu'on veut \item Rq : 2SAT et Horn-SAT sont eux dans P \end{itemize} \bigskip \textbf{Références :} Wolper [\hyperref[bib]{Wol}], Carton [\hyperref[bib]{Car}], Cori-Lascar [\hyperref[bib]{CL1}], Lassaigne-Rougemont [\hyperref[bib]{LdR}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Théorème de Cook [\hyperref[bib]{Wol} p 185] ou [\hyperref[bib]{Car} p 203] \item Transformation de Tseitin [\hyperref[bib]{Car} p 204] \end{itemize} \newpage \section*{918. Systèmes formels de preuve en logique du premier ordre. Exemples.} \textbf{Plan :} \medskip But : Formaliser les preuves. On aimerait que cela permette de les automatiser. \medskip I/Logique du premier ordre 1) Syntaxe \begin{itemize}[label=$\rightarrow$] \item On se donne $\{v_i\}_i, \{c_i\}_i, \{f_i\}_i, \{p_i\}_i$ des ensembles dénombrables de variables / constantes / symboles de fonctions / symboles de prédicats \item définition terme, formule atomique, formule + exs \item Définition occurrences quantifiées d'une variable / variable libre + ex \item Définition + notation d'une substitution \end{itemize} 2) Sémantique \begin{itemize}[label=$\rightarrow$] \item Définition structure + définition inductive de la valeur d'un terme dans une structure munie d'une valuation \item Définition modèle + formule satisfiable ou valide \end{itemize} 3) Théories et modèles \begin{itemize}[label=$\rightarrow$] \item Définition d'une théorie, modèle d'une théorie + ex : Presburger avec $\mathbb{N}$ \item Définition F est conséquence sémantique d'une théorie T \end{itemize} 4) Système de déduction \begin{itemize}[label=$\rightarrow$] \item Définition d'un séquent + ex \item Définition d'une règle de déduction + ex : modus ponens \item Définition d'un système de déduction \item Définition d'un séquent / formule prouvable \item Définition théorie cohérente / complète \end{itemize} \medskip II/Déduction naturelle \begin{itemize}[label=$\rightarrow$] \item Donner toutes les règles de déduction \end{itemize} 2) Propriétés \begin{itemize}[label=$\rightarrow$] \item Prop : La déduction naturelle est correcte ($T \vdash F \Rightarrow T \vDash F$) \item Définition théorie de Henkin + prop : une théorie de Henkin cohérente et complète admet un modèle \item Prop : Complétion d'une théorie cohérente en une théorie de Henkin + csqc : toute théorie cohérente admet un modèle \item Prop : Complétude de la déduction naturelle ($T \vDash F \Rightarrow T \vdash F$) \item Rq : Le calcul des séquents permet de symétriser les règles de la déduction naturelle \end{itemize} \medskip III/Résolution 1) Clauses \begin{itemize}[label=$\rightarrow$] \item Définition d'une clause \item Prop : Comment transformer une formules en clause + ex \end{itemize} 2) Unification \begin{itemize}[label=$\rightarrow$] \item Définition unificateur, unificateur principal + ex \item Prop : Existence d'un unificateur principal dès qu'il existe un unificateur \item Algo d'unification \fbox{DEV1} + rq sur la complexité \end{itemize} 3) Résolution \begin{itemize}[label = $\rightarrow$] \item Règles de la résolution \item Définition preuve par résolution / par réfutation \item Prop : Correction de la résolution \item Définition modèle de Herbrand \item Prop : Complétude de la résolution \fbox{DEV2} + appli : compacité de la résolution \end{itemize} \bigskip \textbf{Références :} [\hyperref[bib]{DNR}], Lassaigne-Rougemont [\hyperref[bib]{LdR}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Complétude de la résolution [\hyperref[bib]{LdR} p 102] \item Etude d'un algorithme d'unification [\hyperref[bib]{DNR} p 248] \end{itemize} \newpage \section*{919. Unification : algorithmes et applications.} \textbf{Plan :} \medskip I/Syntaxe et unification 1) Termes et substitutions \begin{itemize}[label=$\rightarrow$] \item Définition d'un langage du premier ordre \item Définition terme + ex \item Définition substitution + notation + résultat d'une substitution appliquée à un terme + ex \end{itemize} 2) Unificateurs \begin{itemize}[label=$\rightarrow$] \item Définition termes unifiables, unificateur + ex \item Extension : unificateur d'un ensemble fini d'équations \item Définition unificateur principal \item Prop : Si on a un unificateur, on a un unificateur principal \end{itemize} \medskip II/Algorithmes 1) Historique \begin{itemize}[label=$\rightarrow$] \item Algorithme de Robinson \item Prop : Il est non déterministe, exponentiel en temps et en place \end{itemize} 2) Algo classique \begin{itemize}[label=$\rightarrow$] \item Algo de Martelli-Montanari (code) \item Prop : Il est correct et termine \fbox{DEV1} \item Ex sur lequel il est exponentiel en temps et en place [\hyperref[bib]{DNR}] \end{itemize} 3) Améliorations \begin{itemize}[label=$\rightarrow$] \item Première idée : Transformer les termes en graphes \item Algo utilisant les graphes + ex + il est linéaire en place mais peut rester exponentiel en temps \item Deuxième idée : Amélioration de l'algo précédent pour obtenir un temps quadratique \item Rq : Avec Union-find, on peut avoir un algo pseudo-linéaire en temps \end{itemize} \medskip III/Application à la résolution 1) Clauses \begin{itemize}[label=$\rightarrow$] \item Définition formule atomique + ex \item Définition d'une clause \item Prop : Transformation d'une formule en clauses + ex \end{itemize} 2) Résolution \begin{itemize}[label=$\rightarrow$] \item Règles de la résolution \item Définition d'une preuve par résolution / par réfutation \item Prop : Correction de la résolution \item Définition d'un modèle de Herbrand \item Prop :Complétude de la résolution \fbox{DEV2} \end{itemize} \medskip IV/Application à la réécriture \begin{itemize}[label = $\rightarrow$] \item Définition de $R$ un système de réécriture noté $\rightarrow$ \item Définition + notation de "u et v sont joignables" \item Définition d'un système terminant, confluent, localement confluent \item Définition de la position d'un sous terme + substitution d'un sous terme \item Définition paire critique + ex en annexe \item Lemmes des paires critiques + $R$ est localement confluent ssi ses paires critiques sont joignables \item Lemme de Newman \item Th : Si $R$ est terminant et a un nombre fini de règles, il est confluent ssi ses paires critiques sont joignables. On peut donc décider la confluence d'un tel système \end{itemize} \bigskip \textbf{Références :} [\hyperref[bib]{DNR}], Lassaigne-Rougemont [\hyperref[bib]{LdR}], Baader [\hyperref[bib]{Baa}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Complétude de la résolution [\hyperref[bib]{LdR} p 102] \item Etude d'un algorithme d'unification [\hyperref[bib]{DNR} p 248] \end{itemize} \newpage \section*{920. réécriture et formes normales.} IMPASSE \section*{921. Algorithmes de recherche et structures de données associées.} \textbf{Plan :} \medskip Intro : On cherche quelles structures utiliser pour manipuler un ensemble $E$ pour lequel on souhaite rechercher, supprimer et insérer des éléments. Dans la suite, on considère que les clés sont deux à deux distinctes. \medskip I/Recherche dans une structure "séquentielle" \begin{itemize}[label=$\rightarrow$] \item Recherche dans une liste non triée + complexité des 3 opérations \item Recherche dans un tableau trié (dichotomie) + complexité des 3 opérations \item Cas particulier d'une liste de caractère = recherche de motif dans un texte : on peut le faire grâce à l'automate des occurrences \fbox{DEV1} \end{itemize} \medskip II/Tables de hachage [\hyperref[bib]{Cor}] 1) Généralités \begin{itemize}[label=$\rightarrow$] \item Définition univers et clés \item Adressage direct + problème de mémoire si l'univers est grand \item Principe du hachage + def : fonction de hachage \item Définition d'une collision + gestion des collisions par chaînage \item Définition d'un hachage uniforme + coûts des 3 opérations \end{itemize} 2) Faire un bon hachage \begin{itemize}[label=$\rightarrow$] \item Pb : Le pire cas d'une recherche peut être en $O(n)$ et en plus un utilisateur malveillant peut consciemment remplir une alvéole pour que ce pire cas arrive \item Définition classe universelle de fonctions de hachage + ex \item Prop : Hachage parfait \fbox{DEV2} \end{itemize} \medskip III/Structures arborescentes 1) ABR \begin{itemize}[label=$\rightarrow$] \item Définition arbre binaire de recherche + prop : hauteur d'un tel arbre en fonction du nombre de noeuds \item Algos pour la recherche, insertion, supprimer + complexités \item Rq : Toutes ces complexités sont en $O(\text{hauteur de l'arbre})$ : on a un problème si l'arbre est en peigne \end{itemize} 2) AVL \begin{itemize}[label=$\rightarrow$] \item Définition d'un AVL \item Rq : Les algos de recherche / insertion / suppression sont les mêmes qu'avec les ABR \item Définition rotation à gauche et à droite + dessins en annexe \item Complexité des 3 opérations incluant le rééquilibrage \end{itemize} 3) On peut aussi parler des ABR optimaux \medskip Conclusion : Tableau comparatif des structures / complexités des opérations [\hyperref[bib]{FG} p 298] \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], Froidevaux-Gaudel [\hyperref[bib]{FG}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Automate des occurrences [\hyperref[bib]{Cor} p 915-921] \item Hachage parfait [\hyperref[bib]{Cor} p 258] \end{itemize} \newpage \section*{923. Analyse lexicale et syntaxique. Applications.} \textbf{Plan :} \medskip Prérequis : Notions sur les automates finis \medskip I/Analyse lexicale 1) Outils \begin{itemize}[label=$\rightarrow$] \item Déf : C'est un procédé qui transforme une suite de caractère en une suite de mots \item Définition unité lexicale, motif (représenté par une expression rationnelle), lexème + ex \end{itemize} 2) Reconnaissance des lexèmes \begin{itemize}[label=$\rightarrow$] \item Théorème de Kleene : d'où l'utilisation d'automates pour reconnaître des motifs \item Prop : Tout automate fini est équivalent à un automate déterministe \item Prop : Existence et construction de l'automate minimal (= des résiduels) \item Automates des occurrences \fbox{DEV1} \end{itemize} 3) Utilisation des automates \begin{itemize}[label=$\rightarrow$] \item On créé un automate minimal pour chacun des motif puis on les lit simultanément jusqu'à ce qu'on ne puisse plus avancer dans aucun des automates. Juste avant cette étape il y avait donc au moins un des automates qui n'était pas bloqué. On prend le plus long préfixe du mot qui aboutissait dans un état final de cet automate pour savoir quel est le motif. Si il y a une égalité, on impose des priorités (de façon par exemple à ce que "12" devienne et non ) \end{itemize} \medskip II/Analyse syntaxique But : Construire l'arbre représentant la structure du texte résultant de l'analyse lexicale 1) Grammaire, analyseur universel \begin{itemize}[label=$\rightarrow$] \item Définition grammaire algébrique, dérivation, langage engendré + ex \item Ici notre but est de savoir si la chaîne de noms d'unités lexicales peut être produite par la grammaire du langage source et si oui, de construire un arbre syntaxique \item Définition grammaire de Chomsky \item Algorithme CYK \fbox{DEV2} \end{itemize} 2) Analyse descendante : cas de LL(1) \begin{itemize}[label=$\rightarrow$] \item Définition de premier et suivant + algos \item Table prédictive + exemple d'analyse descendante (de l'axiome vers le texte) sur grammaire LL(1) \item Rq : Expliquer la dénomination LL(1) \end{itemize} 3) Analyse ascendante LR(0) \begin{itemize}[label=$\rightarrow$] \item Définition d'un item, règle de réduction \item Automate des items pour analyse descendante (du texte vers l'axiome) sur grammaire LR(0) \end{itemize} \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], Schwarzentruber [\hyperref[bib]{Sch}], Cormen [\hyperref[bib]{Cor}] (pour développement) \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Automate des occurrences [\hyperref[bib]{Cor} p 915-921] \item CYK [\hyperref[bib]{Car} p 199] \end{itemize} \newpage \section*{924. Théories et modèles en logique du premier ordre. Exemples.} \textbf{Idée de défense de plan :} Une théorie est un ensemble de formules : on aimerait savoir ce qu'on a défini avec, quelles structures $\rightarrow$ modèles \medskip \textbf{Plan :} \medskip I/Syntaxe et sémantique en logique du premier ordre 1) Syntaxe \begin{itemize}[label=$\rightarrow$] \item Définition langage du premier ordre + ex : langage de la théorie des groupes \item Définition terme (clos), formule atomique, formule + ex : quelques formules de la théorie des groupes \end{itemize} 2) Interprétation \begin{itemize}[label=$\rightarrow$] \item Définition structure, valuation, valeur d'une formule \item Définition formule satisfiable, formule valide \end{itemize} 3) Théories \begin{itemize}[label=$\rightarrow$] \item Définition d'une théorie + ex : théorie des groupes \item Définition modèle d'une théorie + ex pour la théorie des groupes \item Définition formule T-valide, T-satisfiable +ex (toujours en théorie des groupes) \item Définition théorie consistante, cohérente, contradictoire (avec $\vdash$ = la déduction naturelle) \item Définition théorie de Henkin + prop : une théorie de Henkin cohérente et complète admet un modèle + complétion d'un théorie en une théorie de Henkin + csqc : toute théorie cohérente admet un modèle \end{itemize} \medskip II/Modèles de Herbrand et résolution 1) Clause \begin{itemize}[label=$\rightarrow$] \item Définition clause \item Prop : Transformation d'une formules en ensemble de clauses \end{itemize} 2) Unification \begin{itemize}[label=$\rightarrow$] \item Définition unificateur + algo d'unification \item Règles de la résolution + définition d'une preuve par résolution / réfutation \end{itemize} 3) Complétude de la résolution \begin{itemize}[label=$\rightarrow$] \item Définition modèle de Herbrand \item Prop : On a un modèle ssi on a un modèle de Herbrand \item Appli 1 : Une version faible de Lowenheim-Skolem \item Appli 2 : Complétude de la résolution \fbox{DEV1} \end{itemize} \medskip III/Théories récursives et décidables \begin{itemize}[label=$\rightarrow$] \item Définition des deux notions \item Recopier en gros le V de la leçon 914 + décidabilité de Presburger \fbox{DEV2} \end{itemize} \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], [\hyperref[bib]{DNR}], Lassaigne-Rougemont [\hyperref[bib]{LdR}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Décidabilité de Presburger [\hyperref[bib]{Car} p 178] \item Complétude de la résolution [\hyperref[bib]{LdR} p 102] \end{itemize} \newpage \section*{925. Graphes : représentation et algorithmes.} \textbf{Plan :} \medskip I/Définitions \begin{itemize}[label=$\rightarrow$] \item Définition graphe orienté, non orienté, pondéré \item Définition sommet adjacent, chemin entre deux sommets, cycle, coût dans le cas pondéré \item Définition : cas particulier des arbres + caractérisations \item Représentations : matrice d'adjacence, liste d'adjacence, liste d'arêtes + comparaison coût mémoire et coûts des opérations classiques \end{itemize} \medskip II/Parcours \begin{itemize}[label=$\rightarrow$] \item Parcours en largeur : algo + complexité \item Appli : Prim, Dijkstra (même principe) \item Parcours en profondeur : algo + complexité \item Appli : Calcul des composantes fortement connexes \item Appli des deux parcours : résoudre le problème d'accessibilité \end{itemize} \medskip III/Arbres couvrants minimaux \begin{itemize}[label=$\rightarrow$] \item définition d'un ACM \item Algo de Prim \item Algo de Kruskal \end{itemize} \medskip IV/Plus courts chemins \begin{itemize}[label=$\rightarrow$] \item A origine unique : Bellman-Ford \fbox{DEV1} \item A originie unique : Dijkstra \item Entre tout couple de sommets : Floyd-Warshall + appli : calcul de la fermeture transitive d'un graphe \end{itemize} \medskip V/Un peu de NP-complétude \begin{itemize}[label=$\rightarrow$] \item Le problème k-color : il est NP-complet \item Définition d'un cycle hamiltonien \item Le problème du voyageur de commerce et du cycle hamiltonien sont NP-complets \item Mais on peut quand même faire des choses : PVCE \fbox{DEV2} \end{itemize} \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], Froidevaux-Gaudel [\hyperref[bib]{FG}], Garey-Johnson [\hyperref[bib]{GJ}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Bellman-Ford [\hyperref[bib]{Cor} p 602-605] \item Problème du voyageur de commerce euclidien [\hyperref[bib]{Cor} p 1023] \end{itemize} \newpage \section*{926. Analyse des algorithmes, complexité. Exemples.} \textbf{Plan :} \medskip Intro : Quand on a plusieurs algos corrects pour répondre à un problème, on souhaite les comparer. Une façon de faire est de s'intéresser à leurs complexités temporelles / spatiales \medskip I/Généralités [\hyperref[bib]{FG} p 5-27] 1) Notion de complexité \begin{itemize}[label=$\rightarrow$] \item "Définition" d'un algorithme \item Définition complexité spatiale (on ne compte pas la place prise par l'entrée) + rq : on pourrait formaliser cette notion avec les machines de Turing \item Définition complexité temporelle = fonction $c$ qui à une entrée $x$ associe $c(x)$ le nombre d'opérations élémentaires effectuées sur l'entrée $x$ + ex recherche de $x$ dans la liste $l$ : $c(x,l) = $ position de $x$ dans $l$ si $x \in l$ et $|l|$ sinon \item Définition complexité pire cas $c_{max}(n) = max \{c(x) | x \text{ est de taille } n \}$ et de la complexité moyenne $c_{moy}$ + prop $c_{moy} \leq c_{max}$ + ex recherche dans une liste $c_{moy}(n) = \frac{n}{2}$ \item Rq : Souvent on considère que les entrées sont équiprobables mais c'est souvent faux et ça peut influer \end{itemize} 2) Mesurer la complexité \begin{itemize}[label=$\rightarrow$] \item Rq : Un calcul exact est inutile car dépend de la machine, de l'implémentation \item Notation $O$, $\Omega$, $\Theta$ + ex \end{itemize} \medskip II/Quelques méthodes d'analyse de complexité 1) Méthodes directes \begin{itemize}[label=$\rightarrow$] \item Algos itératifs = facile + ex CYK \fbox{DEV1} \item Algo récursifs = plus compliqué + ex complexité du tri rapide randomisé \fbox{DEV2} \end{itemize} 2) Relations de récurrence sur la complexité \begin{itemize}[label=$\rightarrow$] \item Théorème fondamental de DPR + ex avec le tri fusion (ou Strassen) \item Attention il ne couvre pas tous les cas \item Utilisation de séries génératrices quand on a une relation de récurrence qui s'y prête + ex complexité moyenne du tri rapide [\hyperref[bib]{FG} p 519] \end{itemize} 3) Analyse amortie \begin{itemize}[label=$\rightarrow$] \item Définition : La complexité amortie de l'opération $o$ est le coût moyen de $o$ dans une séquence de $n$ opérations $o$ \item Ex : Méthode de l'agrégat + ex : compteur binaire [\hyperref[bib]{Cor}] + ex ajout dans une table dynamique \item Rq : Il existe d'autres méthodes : méthode comptable, potentiels... \end{itemize} \medskip III/Comment améliorer la complexité \begin{itemize}[label=$\rightarrow$] \item Changer de structure de données pour modifier le coût des opérations élémentaires + ex : matrice d'adjacence VS liste d'adjacence + ex Dijkstra, la complexité est différente si on utilise un tas de Fibonacci plutôt qu'un tas \item Compromis temps/espace : on peut essayer d'augmenter la complexité spatiale pour diminuer la temporelle (et inversement) + ex : mémoïsation en général + rq : parfois, on peut même gagner sur les deux plans, exemple de Fibonacci en conservant uniquement les deux dernières valeurs (linéaire en temps, constant en espace) \item Parfois, on a une borne min pour la complexité d'un algo, par exemple pour les tris par comparaison (tous en $\Omega(n)$) + rq : on peut quand même essayer d'améliorer les constantes des algorithmes optimaux (tri rapide > tri fusion) \end{itemize} \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], Froidevaux-Gaudel [\hyperref[bib]{FG}], Carton [\hyperref[bib]{Car}] (pour CYK) \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item CYK [\hyperref[bib]{Car} p 199] \item Complexité du tri rapide [\hyperref[bib]{Cor} p 166-170] \end{itemize} \newpage \section*{927. Exemples de preuves d'algorithme. Correction, terminaison.} \textbf{Plan :} \medskip Intro : On présente des méthodes permettant de montrer qu'un algorithme termine et est correct relativement à sa spécification + définition spécification (= une prop $P_1$ sur l'entrée et une prop $P_2$ sur la sortie) + ex avec un tri \medskip I/Terminaison 1) Indécidabilité \begin{itemize}[label=$\rightarrow$] \item Définition : Un algo termine s'il s'exécute en un nombre fini d'étapes élémentaires sur toute entrée conforme à sa spécification \item Ex : fonction de Syracuse \item Prop : Indécidabilité du problème de l'arrêt \end{itemize} 2) Ensemble bien fondé \begin{itemize}[label=$\rightarrow$] \item Définition ensemble bien fondé + ex ordre lexicographique [\hyperref[bib]{Alb}] \end{itemize} 3) Algos itératifs \begin{itemize}[label=$\rightarrow$] \item Définition d'un variant de boucle \item Prop : Si une boucle possède un variant, elle termine \item Ex : Dans une boucle for, (indice final) - (indice initial) est un variant \item Ex : Un algo des graphes \end{itemize} 4) Algos récursifs \begin{itemize}[label=$\rightarrow$] \item Prop : Soit $f$ une fonction récursive sur $A$ et $\varphi : A \rightarrow E$ = ensemble bien fondé. Soit $B = \varphi^{-1}\{\text{éléments minimaux de } \varphi(A) \}$. Si $\forall b \in B$, $f(b)$ termine et si pour tout $e$, n’apparaissent qu'un nombre fini de $f(y)$ et tous tels que $\varphi(y) < \varphi(x)$ alors $f$ termine pour tout élément de $A$ \item Ex : Factorielle termine \item Ex : Ackermann termine (ordre lexicographique) \end{itemize} \medskip II/Correction 1) Définitions \begin{itemize}[label=$\rightarrow$] \item Définition correction partielle / totale \item Ex : Syracuse est partiellement correct + la non primalité de Fermat est partiellement correcte \end{itemize} 2) Algos itératifs \begin{itemize}[label=$\rightarrow$] \item Définition d'un invariant de boucle \item Ex : Euclide et tri insertion sont corrects \item Ex : Le tri par tas est totalement correct \fbox{DEV1} \item EX : Unification est totalement correct \fbox{DEV2} \end{itemize} 3) Algos récursifs \begin{itemize}[label=$\rightarrow$] \item Définition induction bien fondée \item Ex : Tri fusion, factorielle, calcul de la hauteur d'un arbre \end{itemize} \bigskip \textbf{Références :} Cormen [\hyperref[bib]{Cor}], [\hyperref[bib]{DNR}], Wolper [\hyperref[bib]{Wol}] (pour le pb de l'arrêt), Albert [\hyperref[bib]{Alb}] \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Etude d'un algorithme d'unification [\hyperref[bib]{DNR} p 248] \item Correction du tri par tas [\hyperref[bib]{Cor} p 142-148] \end{itemize} \newpage \section*{928. Problèmes NP-complets : exemples et réduction.} \textbf{Plan :} \medskip Prérequis : Notions sur les machines de Turing \medskip I/La classe NP [\hyperref[bib]{Car}] 1) Complexité \begin{itemize}[label=$\rightarrow$] \item Définition classe P, classe NP \item Prop $P \subset NP$ + on ne sait pas si $P = NP$ \item Définition vérificateur en temps polynomial \item Prop : Etre dans NP équivaut à avoir un vérificateur polynomial \end{itemize} 2) NP-complétude \begin{itemize}[label=$\rightarrow$] \item Définition réduction polynomiale \item Définiton problème NP-dur, NP-complet \item Prop : Si $A$ est NP-complet et se réduit à $B$ alors $B$ est Np-complet \end{itemize} 3) Complexité et décision \begin{itemize}[label=$\rightarrow$] \item Définition problème de décision + son langage associé = $\{\text{instances positives}\}$ \item Définition problème d'optimisation \item Lien entre les deux + ex + le problème d'optimisation est dit NP-complet quand le problème de décision associé l'est \end{itemize} \medskip II/Autour de la satisfiabilité [\hyperref[bib]{Car}] \begin{itemize}[label=$\rightarrow$] \item Le problème SAT + théorème de Cook \fbox{DEV1} \item Problèmes CNF-SAT et 3SAT : ils ont NP complets car SAT $\leq$ CNF-SAT et CNF-SAT $\leq$ 3SAT \item Les problèmes 2SAT, HORN-SAT et CND-SAT sont eux dans P \end{itemize} \medskip III/Problème du voyageur de commerce \begin{itemize}[label=$\rightarrow$] \item Prop : Le problème du chemin hamiltonien est NP-complet (que le graphe soit orienté ou pas) car CNF-SAT $\leq $ chemin hamiltonien \item Prop : Celui du cycle hamiltonien aussi \item Prop : Le problème du voyageur de commerce est NP-complet car cycle hamiltonien $\leq$ PVC + rq sur la version optimisation du PVC \item Déns le cadre euclidien : PVCE \fbox{DEV2} \end{itemize} \medskip IV/Programmation linéaire en nombres entiers [\hyperref[bib]{GJ}] \begin{itemize}[label=$\rightarrow$] \item Prop : PLNE est NP-complet car CNF-SAT $\leq $ PLNE \item La relaxation de ce problème est dans P (admis) \end{itemize} \bigskip \textbf{Références :} Carton [\hyperref[bib]{Car}], Cormen [\hyperref[bib]{Cor}], Garey-Johnson [\hyperref[bib]{GJ}], Sipser [\hyperref[bib]{Sip}] (pour certaines réductions) \bigskip \textbf{Développements :} \begin{itemize}[label=$\rightarrow$] \item Théorème de Cook [\hyperref[bib]{Car} p 203] \item Problème du voyageur de commerce euclidien [\hyperref[bib]{Cor} p 1023] \end{itemize} \newpage \section*{Bibliographie} \label{bib} [Alb] Albert, \textit{Cours et exercices d'informatique} [Aut] Autebert, \textit{Théorie des langages et des automates} [Baa] Baader, \textit{Term rewriting and all that} [BBC] Beauquier, Berstelle et Chrétienne, \textit{Elements d'algorithmique} [Car] Carton, \textit{Langages formels} [CL1] Cori et Lascar, \textit{Logique mathématique, Tome 1} [CL2] Cori et Lascar, \textit{Logique mathématique, Tome 2} [Cor] Cormen et alii, \textit{Algorithmique} [Cro] Crochemore, \textit{Algorithmique du texte} [Das] Dasgupta, Papadimitriou et Vazirani, \textit{Algorithms} [DNR] David, Nour et Raffalli, \textit{Introduction à la logique} [FG] Froidevaux et Gaudel, \textit{Types de données et algorithmes} [GJ] Garey et Johnson, \textit{Computers and intractability : A guide to the theory of NP-completness} [LdR] Lassaigne et de Rougemont, \textit{Logique et fondements de l'informatique} [Sch] Schwarzentruber, \textit{Compilation : analyse lexicale et syntaxique} [Sip] Spiser, \textit{Introduction to the theory of computation} [Wol] Wolper, \textit{Introduction à la calculabilité} \end{document}