Le cours du 28 janvier 2008

- J'ai récupéré les travaux à faire chez soi
- j'ai illustré ce qu'il y avait à faire en l'application à l'American Film Star de M. Jackson.
- je suis passé d'un automate de Moore à un automate de Mealy
- j'ai traité des automates cellulaires (le jeu de la vie de Conway)
- je suis passé d'arbres Jackson à des specs en FSP (atelier LTSA)
- j'ai introduit la communication entre processus
- le produit d'automates étiquetés
- vous pouvez installer LTSA sur vos machines persos (c'est gratuit)
- voir les messages sur ce bloc-notes (consultez ceux de l'an dernier)


Prochain cours :

- je continuerai sur FSP
- composition parallèle de processus séquentiels
- deadlock
- diagramme de transitions d'états d'une spec FSP

Le cours est disponible sur la Toile (lire ce bloc-notes)

Complexité, un mot vide de sens, ou trop plein de vide ?

Etonnant chez des informaticiens !

Alors, lisons les auteurs ...
J-P Delaye dans son beau livre, Les inattendus mathématiques, Belin, page 35, nous parle de la "complexité de Kolmogorov"
En sciences éco j'avais appris le "test de Kolmogorov-Smirnov".

"La complexité de Kolmogorov d'un objet est la taille du plus petit programme d'ordinateur qui spécifie complètement cet object. Pour un dessin ou une peinture, c'est la taille du plus petit programme qui permet de reproduire l'image de l'oeuvre sans rien perdre de ce que nous en percevons. L'idée de Kolmogorov est simplement de rendre formelle l'intuition commune que "le simple est ce qui se dit en peu de mots" et "le complexe est ce qu'on ne réussit pas à comprimer quoi qu'on fasse."

Je vous rappelle que nous distinguons :
- le complexe, intrinsèque au problème, à l'objet
- le compliqué : utiliser la numération romaine est introduire de la complication dans les opérations arithmétiques (les programmes), utiliser des notations non formelles est introduire des complications, des discussions inutiles dans la conception de systèmes automatisés. (voir mes questions de Projet Tuteuré)


Et citons de nouveau Nicolas (cité dans le poly spec1) :

"Ce qui se conçoit bien s'énonce clairement Et les mots pour le dire arrivent aisément."

Nicolas Boileau, L'art poétique, Chant I.

"faux et usage de faux et atteinte au système de traitement informatisé de données"

Dernières nouvelles :
"L'enquête préliminaire ouverte jeudi après-midi par le parquet de Paris est étendue aux faits de "faux et usage de faux et atteinte au système de traitement informatisé de données", visés par la plainte de la banque. Elle avait été ouverte à la suite de la plainte contre X déposée par un petit porteur pour "escroquerie, abus de confiance, faux et usage de faux". La brigade financière est saisie de cette enquête. "

et le blog qui nous amène au coeur du comment. On comprend un peu ... Excel, mots de passe, procédures, etc. Enfin des tas de choses qui font partie d'un cours de génie logiciel et de sécurité.

Lire aussi ici
Lire l'article du Monde

La modélisation et la vérification des procédures de sécurité utilisent entre autres les techniques que nous étudions dans ce module.

Pour ceux qui ont raté le premier cours

ou qui y faisaient autre chose qu'écouter et prendre des notes
et qui consultent ce bloc-notes, voici ce que j'ai traité :

- la prise en compte d'une "variable d'état" dans un schéma relationnel n-aire, exemple des commandes (livrée, facturée, réglée, en contentieux ...) avec un automate
- écriture de la fonction de transition d'états (fonction si automate déterministe !)
- diagramme de transition d'état simple, état initial, final
- étiqueté par événements
transitions : ETAT * EVENEMENT +-> ETAT
- avec gardes (on verra qu'en B événementiel, un événement est modélisé comme une opération gardée. Revoir l'axiome de la garde vs celui de la précondition. En DS je demandais celui du choix indéterministe. [CHOICE S OR T] I <=> [S] I & [T] I
- avec sorties, Mealy et Moore
- structuré , state-charts de Harel (états disjoints, états parallèles, macro-états)
- pliage, dépliage (exemple avec automates, exemple avec graphe de flot de contrôle d'un programme. Rappel de b a ba de programmation : nichage et séquencement.
- Expressions régulières, notation des arbres de Jackson, exemple du processus Livre, modélisation en parallèle en termes de processus et en termes ensemblistes (B ou relationnel n-aire) , vérif de cohérence entre les deux modélisations
- Le théorème de Kleene. Avant de venir en cours vous deviez lire l'histoire du concept d'automate dans le poly des sujets de TD
- Rappel : voir algo de Yamada de passage d'un automate à une expression régulière. Le cours de maths est à utiliser, réutiliser.

Les deux premiers cours de ce jour

J'ai traité ce que j'avais annoncé ici.
Pour assister au prochain cours, vous devrez me remettre en entrant dans l'amphi :
- le dépliage des deux automates de Harel fournis au tableau
- l'expression régulière ou l'automate pour l'American Film Star

Comme annoncé, je ne mettrai pas cette année sur ce bloc-notes les photos des tableaux noirs de mon cours.
Consultez les messages de l'an dernier.

Et les chapitres du poly de spec1 qui traitent de :

- B événementiel
- automates

La vie des véhicules à moteur

Faire le diagramme états-transitions étiqueté, avec transitions gardées, pour spécifier :

- l'ancien système d'identification des véhicules
- le nouveau système d'identification des véhicules
- proposez une mesure de la complexité d'un système, mesure qui utilisera les automates
- évaluez les deux systèmes
- y-a-t-il simplification ?

Ensuite proposez votre travail à Monsieur Attali et à sa commission, ou directement à Monsieur Sarkozy.
Ça fait 40 ans que chaque gouvernement français nous sort cette scie "simplification administrative" ...

Module Spec2, 2007-2008

Les deux premiers cours auront lieu vendredi matin prochain.

Vous devez avoir lu AVANT de venir en cours, l'introduction du poly des sujets de TD sur l''histoire du concept d'automate.
En début de cours, j'attends vos questions. Le mieux, me les adresser via les messages de ce bloc-notes ainsi tout le monde sera au courant.

Je vais traiter :

- La prise en compte des états d'évolution dans une modélisation relationnelle n-aire "à la Codd"
- Les différents types d'automates
- simple
- déterministe/indéterministe
- avec sorties : de Mealy, de Moore
- avec gardes
- structurées : automates de Harel
- j'en donnerai une sémantique en utilisant B (Eh oui, il faut casser le découpage en modules, désastreux !)

Tout sera illustré par des exemples. Ce ne sera pas un cours de maths pour l'info.

Vous pouvez trouver les photos du tableau du cours de l'an dernier sur ce même bloc-notes.

Récupérer les dossiers de TD ce jour à mon bureau via les représentants de groupes.

P.S. les intervenants en TD seront informés comme vous via ce blog.