INF412 - Fondement de l'Informatique : logique, modèles, calculs (2023-2024)
Résumé de section
-
Informations:
Les documents de la DE:
Archives:
- Archives pales: voir plus bas dans cette même page.
Plan prévisionnel:
- Bloc 1: Introduction, Récursivité/Induction, Calcul propositionnel.
- Bloc 2: Calcul propositionnel. Introduction au calcul des prédicats.
- Bloc 3: Calcul des prédicats. Complétude du calcul des prédicats .Grands théorèmes du calcul des prédicats.
- Bloc 4: Incomplétude. Introduction aux Machines de Turing.
- Bloc 5: Machines de Turing. Modèles de Calculs. Thèse de Church-Turing. Calculabilité.
- Bloc 6: Calculabilité. Révisions
- Bloc 7: Preuve du théorème d'incomplétude. Introduction à la complexité
- Bloc 8: Complexité en temps. NP-complétude.
- Bloc 9: NP-complétude: suite.
- Bloc 10: Autres complexités.
-
- Version: 2023
- Intégralité du polycopié:
Le document en un seul fichier
-
- Chapitre par chapitre:
- 01: Introduction
- 02: Récursivité et induction
- 03: Calcul propositionnel
- 04: Démonstrations
- 05: Calcul des prédicats
- 06: Modèles. Complétude
- 07: Machines de Turing
- 08: Modèles de calculs
- 09: Calculabilité
- 10: Incomplétude de l'arithmétique
- 11: Bases de l'analyse de complexité d'algorithmes
- 12: Complexité en temps
- 13: Quelques problèmes NP-complets
- 14: Complexité en espace mémoire
- 15: Corrections de certains exercices
- Chapitre par chapitre:
- Version: 2023
-
- Version 2023
- The whole document:
The document in one file
-
- Chapter by chapter:
- 01: Introduction
- 02: Recurrence and induction
- 03: Propositional calculus
- 04: Proofs
- 05: Predicate calculus
- 06: Models. Completeness
- 07: Turing machines
- 08: A few other models of computation
- 09: Computability
- 10: Incompleteness of arithmetic
- 11: Basic of complexity analysis of algorithms
- 12: Time complexity
- 13: Some NP-complete problems
- 14: Space complexity
- 15: Solutions of some exercises
- Chapter by chapter:
- Version 2023
-
-
Globalement: Introduction, Récursivité/Induction, Calcul propositionnel.
-
Enregistrement vidéo cours 22 Août Ressource Nudgis
-
-
Solution de la PC1 Fichier
-
-
-
Globalement: Calcul propositionnel: rappels, complétude fonctionnelle, théorème de compacité. Calcul des prédicats.
- Transparents en un seul fichier (version imprimable 2x2)
- Chapitres du polycopiés concernés: chapitre 3 et 4.
-
Enregistrement vidéo du cours du 29 Août Ressource Nudgis
-
-
PC2 : corrigé Fichier
-
-
-
Globalement: Grands théorèmes du calcul des prédicats. Complétude.
- Transparents en un seul fichier (version imprimable 2x2)
- Chapitres du polycopiés concernés: chapitre 5 et 6
-
Voir aussi https://www.geeksforgeeks.org/propositional-and-first-order-logic-gq/ pour plein de questions à choix multiples.
-
Les étudiants doiventMarquer comme terminé
-
-
PC3 : corrigé Fichier
-
-
-
Globalement: Incomplétude. Introduction aux machines de Turing.
-
Enregistrement amphi du 12 septembre 2023 Ressource Nudgis
-
-
PC4 : corrigé Fichier
-
-
Bloc 5 (19-20 Septembre) - Machines de Turing. Modèles de Calculs. Thèse de Church-Turing. Calculabilité.
-
Globalement: Machines de Turing. Modèle de Calculs. Thèse de Church-Turing. Calculabilité.
-
Les étudiants doiventMarquer comme terminé
-
-
PC5 : corrigé Fichier
-
-
-
- PC 6 Notée 2018:
- PC 5 Notée 2017:
- PC 5 Notée 2016:
- PC 5 Notée 2015:
- PC 5 Notée 2014:
- Pour l'édition 2013, la PC notée était la PC 6, donc avec un cours de plus et une PC de plus....
- Pour l'édition 2012, les PC précédentes étaient différentes: plusieurs exercices correspondents maintenant à des exercices des PCs actuelles
- Pour l'édition 2011, la PC notée était la PC 6, donc avec un cours de plus et une PC de plus et les PC précédentes étaient différentes: plusieurs exercices correspondents maintenant à des exercices des PCs actuelles
- Ce cours n'existait pas auparavant.
-
-
-
-
-
Sujet 2023 Fichier
-
Correction 2023 Fichier
-
-
-
Globalement: Calculabilité.
-
-
Les étudiants doiventMarquer comme terminé
-
-
-
-
Les étudiants doiventMarquer comme terminé
-
-
PC7 : corrigé Fichier
-
-
-
-
Les étudiants doiventMarquer comme terminé
-
-
PC8 : corrigé Fichier
-
-
-
Globalement: NP-compétude (suite).
-
Les étudiants doiventMarquer comme terminé
-
-
PC9 : corrigé Fichier
-
-
-
Globalement: Autres complexités.
-
Les étudiants doiventMarquer comme terminé
-
-
PC10 : corrigé Fichier
-
-
Ce cours est la suite de INF423.
INF423 était sur 9 blocs, alors que INF412 est sur 8 blocs.
Le cours INF423 a été crée en 2011-2012.
Archives pour INF423:
Archives pour INF412:
-
Ces pages et liens sont facultatifs. Ils sont là pour ceux qui veulent en savoir plus.-
Les vidéos suivantes m'ont été signalées et me semblent de très bonne qualité.
- Sur le théorème d'incomplétude:
-
- Sur le théorème d'incomplétude:
-
- Prototypes physiques de Machines de Turing
- EN VENTE
- Machine de Turing électronique (auteur: Thierry Delattre, produit en vente). 12 états max par algorithme. Pour plus d'infos écrire à contact@thamtham.fr Twitter: thamographe
- PROTOTYPES:
- Preuves ou vidéo "amusantes" à propos de la Turing complétude de différents systèmes ou des machines de Turing
- The LEGO Turing Machine
- La machine de Turing en cartes Magic (Passe-Science)
- The LEGO Turing Machine
-