Info Faidherbe
 
Rechercher dans ce site

Activité récente sur le site

Cours et TD (spé)

S'abonner pour recevoir les messages

Compléments : minimalisation des automates

publié le 22 févr. 2009 13:26 par PC1 Faidherbe

On étudie les langages dérivés, l'automate minimal et un algorithme de calcul d'icelui.

| Pièces jointes: Cours.Dérivés.pdf

DS 3

publié le 22 févr. 2009 13:11 par PC1 Faidherbe

  1. Le premier sujet était composé de trois extraits de problèmes :
    la partie logique du sujet de CCP 2003 où l'on joue à Indiana Jones (rapport du jury)
  2. la partie automates du sujet des mines 1999 sur les langages minces (rapport du jury)
    la partie automates du sujet des mines 2001 sur l'émondage des automates (avec un corrigé en Pascal proposé par R.G. Lefebvre) (rapport du jury)
  3. Le second était le sujet de polytechnique 1999 (avec deux corrigés, l'un en Caml, l'autre en Pascal, et aussi les sources en ocaml).

| Pièces jointes: DS3+.cor.caml.pdf DS3+.ml DS3+.pas.cor.pdf DS3.cor.pascal.pdf DS3.cor.pdf

Automates et langages

publié le 22 févr. 2009 13:06 par PC1 Faidherbe

Dans ce chapitre on prouve l'équivalence entre les langages rationnels et les langages reconnaissables.
On prouve aussi une forme du lemme de l'étoile qui peut servir à prouver qu'un langage n'est pas rationnel.

| Pièces jointes: Berry.Sathi.pdf Cours.Kleene.pdf

Automates

publié le 18 janv. 2009 12:33 par PC1 Faidherbe   [ mis à jour le·21 janv. 2009 07:02 ]

Un chapitre où on définit les différents automates et les langages qu'ils reconnaissent.
Le principal et de passer d'un type d'automate à un autre en conservant le langage.
Un TP de T. Bourdeaud'huy sur les automates.

| Pièces jointes: Exos.Automates.pdf Poly.automates.pdf tp6 automates.pdf

Mots et langages

publié le 30 nov. 2008 03:28 par PC1 Faidherbe   [ mis à jour le·18 janv. 2009 12:33 ]

Le premier chapitre de la partie du programme concernant les mots et les automates.
Surtout des définitions et l'introduction du formalisme rigide (les expressions régulières) qui permet un traitement automatisé.
Un petit problème sur les mots de Lyndon.

| Pièces jointes: Cours_mots.pdf Exos.Langages.pdf Exos.Lyndon.pdf tp5 huffman.pdf

DS2

publié le 30 nov. 2008 03:19 par PC1 Faidherbe   [ mis à jour le·30 nov. 2008 03:46 ]

Un problème en 3 heures composé de la deuxième partie de CCP 2005 sur les arbres binaires de recherche AVL (rapport du jury)
et de la deuxième partie de CCP 2000 sur les tas.

Un autre sujet était possible, en 4 heures. Il s'agit de l'épreuve de math-info ENS 2004.
Il est toujours utile de lire le rapport du jury.

| Pièces jointes: CCP2005.ml DS2.cor.pdf i00pm1e.pdf

Arbres Binaires de Recherche

publié le 9 nov. 2008 15:48 par PC1 Faidherbe   [ mis à jour le·21 janv. 2009 07:00 ]

Une des applications importantes des arbres binaires homogènes.
Un TP de T. Bourdeaud'huy sur les arbres AVL. Il y a deux versions, Caml et Pascal.

| Pièces jointes: Cours_ABR.pdf Exos_ABR.pdf TP3 arbres avl caml.pdf TP3 arbres avl pascal.pdf abr.ml

DS1

publié le 9 nov. 2008 13:39 par PC1 Faidherbe   [ mis à jour le·9 nov. 2008 13:43 ]

Un exercice de logique (Mines 2006) et le problème du voyageur de commerce (Mines 2008).
Une erreur fréquente : ne pas avoir (bien) lu le sujet.
Les codes OCaml et Pascal sont aussi disponibles.

| Pièces jointes: DS1.cor.pdf DS1.ml DS1.pas

Aide-mémoire Ocaml

publié le 29 oct. 2008 16:10 par PC1 Faidherbe   [ mis à jour le·29 oct. 2008 16:12 ]

Un petit livret pour les instructions courantes.

| Pièces jointes: AideMémoire.pdf

Arbres

publié le 5 oct. 2008 01:51 par PC1 Faidherbe   [ mis à jour le·21 janv. 2009 07:04 ]

Quelques définitions d'arbres avec l'accent porté sur les arbres binaires homogènes.
Le sujet du DS2 de l'an dernier qui portait sur les arbres.
Un programme oCaml qui dessine le squelette d'un arbre.
Un TP de T. Bourdeaud'huy sur les arbres. Il y a deux versions, Caml et Pascal.
Un autre TP sur les tas et le tri par tas.

| Pièces jointes: CoursArbres.ml CoursArbres.pdf DS2.pdf Exos_arbres.pdf TP2 arbres caml.pdf TP2 arbres pascal.pdf dessinArbre.ml tp4 APO caml-1.pdf

‹ Préc.    1-10 sur 12    Suiv. ›