Semaine du lundi 18 novembre 2024
Pour cette semaine, le programme de colles concerne tout ce qui a été vu précédemment, et inclut notamment :
Dans le chapitre d'algorithmique des graphes :
- la connaissance du problème de couplage maximal dans un graphe biparti
- la connaissance du lemme de Berge
- l'algorithme par recherche de chemin augmentant qui en découle ; il faut en connaître au moins le grand principe : on recherche un chemin augmentant depuis chaque sommet de $S_1$, on calcule le nouveau couplage par différence symétrique, et on recommence ; chaque recherche de chemin augmentant se fait par parcours en profondeur depuis le sommet d'origine.
Dans le chapitre de déduction naturelle :
- construction d'arbres de preuves simples à partir des règles de la déduction naturelle ; les règles ne sont pas à connaître par coeur, et devront être fournies, mais il faut savoir les utiliser
- l'équivalence entre "$\Gamma \models \varphi$" et "$\Gamma \vdash \varphi$ est démontrable" n'a pas encore été prouvée, mais est à connaître pour s'aider dans la construction des arbres, afin de juger si un séquent intermédiaire peut être démontré ou non
- la notion de "démontrer une règle" n'a pas encore été vue, mais peut être utilisée dans un exercice si elle est réexpliquée. En particulier, la règle de l'affaiblissement n'a pas encore été vue.
- aucune implémentation n'est attendue autour de la construction d'arbres de preuves
