4 articles tagués avec « colle »

• Décidabilité : Tout le cours.

• Classes de complexité : Tout le cours.

Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).

• Algorithmes d'approximation et Branch and Bound : Tout le cours.

• Algorithmes probabilistes : Tout le cours.

Voici la liste des compétences et connaissances à avoir en colle ainsi que le DS 3.

Révisions sur les graphes : Tout le cours.

Arbres couvrants : Tout le cours.

Composantes fortement connexes et Kosaraju : Tout le cours.

Couplages et graphes bipartis : Tout le cours.

Plus courts chemins et A* : Tout le cours.

Décidabilité : Tout le cours.

Classes de complexité : Tout le cours.

Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).

Algorithmes d'approximation et Branch and Bound : Tout le cours.

Algorithmes probabilistes : Tout le cours.

Voici la liste des compétences et connaissances à avoir pour votre deuxième colle ainsi que le DS 2.

Grammaires :

• Grammaire non-contextuelle (algébrique, hors-contexte).
• Dérivation.
• Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
• Les langages réguliers sont algébriques.
• Arbre de dérivation.
• Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
• Analyse syntaxique : exemple.

Révisions sur les graphes :

• Définitions : degré, voisins...
• Chemin, cycle, connexité.
• Connexe à $n$ sommets $\Rightarrow$ au moins $n - 1$ arêtes.
• Acyclique à $n$ sommets $\Rightarrow$ au plus $n - 1$ arêtes.
• Composantes connexes, composantes fortement connexes.
• Un graphe est un arbre ssi il est connexe acyclique ssi connexe et $n - 1$ arêtes ssi acyclique et $n - 1$ arêtes.
• Représentations par matrice et liste d'adjacence.
• Parcours en largeur et profondeur. Application à la connexité et à la recherche de cycle.

Arbres couvrants :

• Définition.
• Algorithme de Kruskal. Correction.
• Union-Find avec compression de chemin et union par rang.

Voici la liste des compétences et connaissances à avoir pour votre première colle. La colle est constituée d'un ou plusieurs exercices.

Langages :

• Définitions et opérations sur les mots et langages
• Montrer l'égalité de deux langages (double inclusion...)
• Montrer une propriété par récurrence sur des mots
• Connaître la définition de langage régulier
• Montrer qu'un langage est régulier (éventuellement en passant par une expression régulière)
• Connaître la syntaxe des expressions régulières
• Montrer une propriété sur les langages réguliers (ou expressions régulières) par induction structurelle
• Écrire un programme OCaml pour manipuler une expression régulière

Automates :

• Définitions
• Écrire un programme OCaml pour manipuler un automate
• Montrer qu'un langage est reconnaissable
• Trouver le langage reconnu par un automate
• Compléter un automate
• Algorithme de déterminisation et automate des parties
• Stabilité des langages reconnaissables par complémentaire, intersection, union, différence. Automate produit.
• États accessibles et co-accessibles. Automate émondé. Tout automate est équivalent à un automate émondé.
• Lemme de l'étoile, avec démonstration et application pour montrer qu'un langage n'est pas reconnaissable.

Théorème de Kleene :

• Langage local, expression régulière linéaire.
• Algorithme de Berry-Sethi pour construire un automate (de Glushkov) à partir d'une expression régulière.
• ε-transitions. Tout automate avec des ε-transitions est équivalent à un automate sans ε-transition.
• Automate de Thompson (construit récursivement) à partir d'une expression régulière.
• Méthode d'élimination des états pour obtenir une expression régulière à partir d'un automate.
• Théorème de Kleene et conséquences.

Grammaires :

• Grammaire non-contextuelle (algébrique, hors-contexte).
• Dérivation.
• Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
• Les langages réguliers sont algébriques.
• Arbre de dérivation.
• Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
• Analyse syntaxique : exemple.