# Séances de préparation aux oraux 2026 ## Semaine 1 : thème logique ### Séance "base" - Présentation des différents types d'épreuves et conseils - Logique (énigme des robots), mines-télécom 2024 - Système de connecteurs logiques, mines-télécom 2025 ### Séance "approf" - Déduction_naturelle et typage, ccinp-a - inférence de type - exo ENS 2023 - incomplétude de la déduction naturelle intuitioniste grâce à la sémantique de Tarski ### TP CCINP 13h - SAT ccinp-b 2023 ### TP Centrale/Mines 15h Au choix : - Jeu randomisé et route optimale - Centrale - sujet 02 - Inférence de type - Mines-Ponts ### À finir en autonomie - Déduction_naturelle, mines-télécom sujet0 - Déduction_naturelle, ccinp-a sujet0 - Horn-SAT, ccinp-b 2024 - Fnc-sat et n-color, ccinp-a sujet0 ## Semaine 2 : thème structures de données ### Séance "base" - tas binaire mt-2024 - création d'un tas en temps linéaire - file mt-2024 - étude amortie de file avec deux piles ### TP Centrale/Mines 13h - Représentation de chaı̂nes de caractères - Centrale - sujet 06 ### TP CCINP 15h - liste chainee de mots, ccinp-2025 - arbres de Braun, ccinp-b - file cyclique ocaml, ccinp-b-2023 ### Séance "approf" - révision union_find (sans puis ac compression de chemins) - invariants union_find pour MQ les opérations sont logarithmiques - exo x_2023 union_find ### À finir en autonomie - ABR ccinp-a-sujet0 - arbre et tri mt-2023 - (minima locaux dans les arbres ccinp-a-sujet0) - introduction du logarithme étoile (cf [fiche](https://perso.eleves.ens-rennes.fr/~afalq494/docs_info/fiches_info/Logarithme_etoile.pdf) ) - complexité amortie de union_find avec compression de chemin (cf [fiche](https://perso.eleves.ens-rennes.fr/~afalq494/docs_info/fiches_info/Union-find.pdf)) - à chercher : comment trouver le chemin de la prochaine feuille dans un arbre complet à gauche ## Semaine 3 : ### Séance "approf" - classes de complexité probabilistes ([slides de Nathaniel Carré](https://luminy26.informatique.prof/carr%C3%A9/classes_proba.pdf)) - réductions entre problèmes NP : set_cover et dom_sommets (exo 10 de la [feuille de révisions de MPI](https://cahier-de-prepa.fr/mpi-fermat/download?id=752&v=6e215)) ### Séance "base" : thèmes graphes et prog. dyn. - exercice relation équiv ccinp-a-2024 (dont parcours pour calculer les composantes connexes) - exercice ccinp-b-2023 justification de texte ### TP CCINP 13h - maximum des degrés, CCINP type B, sujet 0 - récolte dynamique de fleurs, ccinp tyep B, 2023 - ### TP Centrale/Mines/ENS 15h - Sujet 0 CCMP - [lien de téléchargement **attention 55 Mo**](https://filesender.renater.fr/?s=download&token=3456965b-6306-444a-b629-cdadbd3d489e) - [lien de téléchargement d'une version allégée (20.5Mo)](https://filesender.renater.fr/?s=download&token=1f0359e1-862d-4717-9d1a-728840e03603) - Sujet ENS : [très grands nombres](https://informatique.ens-lyon.fr/concours-info/2017/tres_grands_numbres.pdf) ### À finir en autonomie - chemin simple sans issue, exo ccinp type b, 2023 - clôture transitive, ccinp type b, 2024 - sac à dos, exo ccinp type b, sujet 0 - être efficace pour coder des graphes en C, y compris des petits graphes explicites pour tester ses fonctions ## Semaine 4 : thème langages ### Séance "base" - Langages réguliers, ccinp type a - Grammaires, Mines-Télécom 2023 - Décidabilité, ccinp type a, 2023 ### Séance approfondissement ou base ? à voir mardi ### TP Centrale/Mines 13h ### TP CCINP 15h - Langage de Dyck, ccinp type b, 2024 - Langage locaux, ccinp type b, 2023 ## Semaine 5 : thèmes divers # Séance base