http://get-the.net/ 2026-07-26T03:19:17+02:00 http://get-the.net/ http://get-the.net/lib/images/favicon.ico text/html 2010-01-10T16:51:55+02:00 http://get-the.net/doku.php?id=m1ilc:algo_dist_1&rev=1263138715&do=diff Election (1/2) I) Proposer un algorithme d'élection dans les cas suivants : * Election sur un anneau unidirectionnel * Election sur un arbre couvrant Solution #1 D'abord, comprenons ce que c'est qu'un anneau unidirectionnel : chaque machine à un, et un seul destinataire (dit “successeur”) pour ses messages, et une seule source. Cependant, l'anneau ne suit pas nécessairement une numérotation des machines, ni même des connections physiques (tant qu'il existe un chemin physique pour réalis… text/html 2010-01-10T17:21:16+02:00 http://get-the.net/doku.php?id=m1ilc:algo_dist_2&rev=1263140476&do=diff Elections (2/2) Election sur un arbre couvrant (suite) Racine initiateur Hypothèses * L'initiateur, est la racine * Communications FIFO, sans perte, par arbre couvrant Principe * envoie REQ à tous ses fils, pour choisir quand toutes les réponse seront remontées. * Chaque fils qui n'est pas feuille transmet à ses fils. * Lorsqu'un processus aura reçu les réponses de tous ses fils, il répondra à son parent la meilleur valeur de ses fils et de lui-même. * Lorsque a reçu toutes … text/html 2010-01-08T12:54:00+02:00 http://get-the.net/doku.php?id=m1ilc:algo_dist_3&rev=1262951640&do=diff Election dans un graphe quelconque Maillage complet et diffusion Soit l'algorithme du plus fort (bully algorithme) de Garcia-Molina: Le site initiateur diffuse le message à tous les processus. Puis il attend. A la réception d'un un processus répond text/html 2010-05-18T18:01:39+02:00 http://get-the.net/doku.php?id=m1ilc:algoplus&rev=1274198499&do=diff Algorithmique avancée Enseignant Site/Liens Cours TD TP ECTS M. Basile SAUVAGE Materiel 2008 ou Sauvage:enseignements 18 18 3 Objectifs savoir-faire et compétences -- Analyse d'algorithmes Contenu Etude des principales familles d'algorithmes : diviser pour régner, méthodes gloutonnes, programmation dynamique, algorithmes randomisés. Algorithmes approchés pour la résolution de problèmes difficiles. Prérequis Algorithmique de base, structures de données, programmation impérative… text/html 2010-05-19T07:50:34+02:00 http://get-the.net/doku.php?id=m1ilc:algoplus_ct&rev=1274248234&do=diff Algorithmique Avancée -- Contrôle Terminal Exercice 1 (8 pts) Exercice 2 (12 pts.) Recherche du k-ième plus petit élément d'un tableau A non trié de n éléments indexés de 1 à n. 2.1 Écrivez un algorithme Pivoter(A, inf, sup) qui ré-ordonne les éléments du sous-tableau A[inf..sup] autour du pivot A[inf] : tous les éléments plus petits que le pivot se retrouvent à sa gauche, et tous les éléments plus grands à sa droite. Cet algorithme doit renvoyer la position finale du pivot. Il ne doit pas… text/html 2010-01-09T20:29:50+02:00 http://get-the.net/doku.php?id=m1ilc:algorithmes_distribues&rev=1263065390&do=diff Algorithmes Distribués Synoptique Prof Site Cours TP TD ECTS M. P. Gançarsky site perso du prof 24h 3 Contenu Aspects algorithmiques des systèmes distribués (ou répartis). Etude d'algorithmes distribués pour la résolution de problèmes de communication, d'allocation de ressources et de synchronisation. Exclusion mutuelle par échange de messages. Diffusion. Arbres couvrants. Tâches : ordonnancement, terminaison, répartition des calculs. Coopération et concurrence entre process… text/html 2010-05-23T10:37:56+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo&rev=1274603876&do=diff Problèmes et méthodes algorithmiques en bioinformatique Enseignant Site/Liens Cours TD TP ECTS M. Christian Michel 24 12 Objectifs Ce cours présente les principaux problèmes et méthodes algorithmiques en bioinformatique. Contenu Méthodes statistiques de recherche de motifs biologiques: * fréquences d'occurrence et significativité, * fonctions de corrélation et ses transformées, * entropie, * méthodes graphiques (exemple avec la représentation “Chaos Game”), * méthodes st… text/html 2010-05-23T16:14:05+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_2&rev=1274624045&do=diff Introduction Algorithme Naïf Pour perspective, partons de l'algorithme naïf et le calcul de son complexité. L'algorithme naïf cherche un mot x de longueur |x|=m dans un texte y de longueur |y|=n. Il étudie tous les cas possibles, en comparant x au contenu d'une fenêtre glissante sur y de longueur m. text/html 2010-05-23T11:27:11+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_3&rev=1274606831&do=diff Objectifs de la Recherche de Motifs Biologiques L'objectif de la détermination de génomes complets--d'organismes simples ou complexes-- est de permettre l'identification de principes et lois apportant à la biologie les bases nécessaires pour une science quantitative ét prédictive. text/html 2010-05-25T20:13:06+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_4&rev=1274811186&do=diff Concept de Populations de Gènes Exercice Proposer des hypothèses de structures de gènes primitifs et de modes d'évolution de ces gènes. Est-ce que le gène primitif était aléatoire ou non? Et l'évolution, aléatoire ou non-aléatoire? Considérons les possibilités, et leurs conséquences reflétées dans les gènes actuels. text/html 2010-05-25T20:29:59+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_5&rev=1274812199&do=diff Principe Les principaux modèles probabilistes de l'évolution des gènes et génomes sont les modèles de substitution de lettres au cours du temp et leurs extensions aux modèles de substitution de motifs. Il existe quatre hypothèses probabilistes sur le processus de substitution : text/html 2010-05-25T18:24:52+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_5_3&rev=1274804692&do=diff Énoncé du problème Matrice de substitution à 2 paramètres : il existe deux taux de substitution, un à l'intérieur des purine et pyrimidines, et un entre purines et pyrimidines. Soient * α le taux de transition (intra-classe) * β le taux de transversion (entre classes) text/html 2010-05-25T18:40:34+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_5_4&rev=1274805634&do=diff 5.4 Distance évolutive Le problème est de définir une distance entre deux mots qui ont évolué d'un même ancêtre. Rappel, la probabilité que le site soit occupé au temps t par une lettre identique à celle au temps 0 et . La probabilité que deux mots aient 2 lettres identiques dans un même site au temps t qui soient identiques à la lettre au temps 0, puisqu'ils sont censés évoluer indépendamment, est P(t)*P(t). text/html 2010-05-24T17:46:44+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_6&rev=1274716004&do=diff Définitions +1...n1...m1...n1...mii... Exercice L'ensemble A34 est-il un code? Oui : * x1,...,xn = x'1,...,x'm implique que n=m car tous les mots ont longueur 3. * => xi=x'i car ils arrivent aux mêmes positions (3*(i-1)..”*(i-1+2) et les deux concaténations sont égales. text/html 2010-05-25T12:32:14+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_diff_eq&rev=1274783534&do=diff * * * calcul du facteur intégrant l(t) * d'où * * multiplication de l'équation différentielle par l(t) * * Or, , d'où * * Ensuite, intégration de l'équation différentielle : * text/html 2010-03-23T13:34:48+02:00 http://get-the.net/doku.php?id=m1ilc:bioinfo_projet&rev=1269347688&do=diff Recensement de codes circulaires Il s'agit d'un problème d'énumération combinatoire efficace (ou très gros moyens de calcul) pour dénombrer (et lister, éventuellement) les ensembles de trils (trinucléotides ou trilettres) de A43 qui sont des codes circulaires, puis parmi ces ensembles, ceux qui sont maximaux, maximaux et autocomplémentaires, maximaux et C3, et (enfin) à la fois maximaux, autocomplémentaires et C3. text/html 2009-11-30T13:07:55+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_1&rev=1259582875&do=diff I. Machines de Turing Introduction * On s'occupe [dans ce cours?] de langages (formels) : ensembles de mots sur un alphabet . * Nous aurions vu des classes de langages intéressants. Langages Rationnels Représentation graphique d'un automate fini déterministe text/html 2009-11-30T14:17:25+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_2&rev=1259587045&do=diff Composition de Machines de Turing D'abord, un petit exercice de conception d'une MT (assez) simple : Exercice : MT qui inverse a et b Pour un MT avec , trouver une MT qui change a en b et b en a. S = symbole lu Q = état qi sj qij sij dij 0 > 0 -> Si début de ruban, on avance à droite 0 c 0 -> si on lit c on avance au caractère suivant 0 a 1 b si on lit a on écrit b et se prépare à avancer en passant à l'état 1 0 b 1 a si on lit b on écrit a et se prépare à … text/html 2009-11-30T14:49:44+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_3&rev=1259588984&do=diff I.3 Fonctions Récursives Exemple 1 : retournement Exemple 2 : incrément unaire Exercice : incrément binaire Rajouter 1 en binaire dans le sens “habituel”. Fonctions entières récursives Langages récursivement énumerables Semi-décidabilité text/html 2009-10-19T11:14:50+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_5&rev=1255943690&do=diff 1.5 Machines de Turing non-déterministes Exemple FIXME faut faire un dessin déf : semi-décidabilité déf : décision déf : calcule Remarque Toute MT est un MTND. Est-ce qu'on peut avoir une MT équivalente à une MTND? Théorème d'équivalence Si une MTND décide (resp. semi-décide) un langage L, alors il existe une MT standard qui décide (resp. semi-décide) L. text/html 2009-10-21T22:36:14+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_6&rev=1256157374&do=diff <= section précedente -\- section suivante => Grammaires Générales * génération versus reconnaissance Exemples * grammaire linéaire à droite (régulières) * grammaires hors contexte (algébriques) Exemple particulier Quelle est cette grammaire? text/html 2009-11-03T08:29:06+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_7&rev=1257233346&do=diff <= section préc. Fonctions numériques * Remarque : calcul et manipulation de symboles sont équivalents. Les entiers correspondent à des mots sur un alphabet, en unaire, base b, nombres romains... * fonctions polynomiales telles sont construites avec * des fonctions de base * des combinaisons de fonctions text/html 2010-01-06T11:32:01+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_9&rev=1262773921&do=diff II. Indécidabilité II.1 Thèse de Church-Turing On a vu au chapitre précedent plusieurs modèles de calcul qui étaient tous équivalents aux MT standard. Church et Turing cherchaient à caractériser ce qu'on savait calculer mécaniquement: calcul booléen, décidabilité des langages récursifs. En même temps, il y avait du travail fondamental sur la formalisation des mathématiques (Hilbert, notamment) et les (possibilité de) preuves mécaniques. text/html 2010-01-06T21:20:43+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_a&rev=1262809243&do=diff II.4 Problèmes Indécidables Théorème (rappel) * H n'est pas récursif * Il existe des langages récursivement énumérables qui ne sont pas récursifs * La classe des langages récursivement énumerables n'est pas stable par complément * Exemple : * H n'est pas récursif et n'est pas récursivement énumerable. text/html 2010-01-06T21:22:17+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_b&rev=1262809337&do=diff II.5 Problèmes indécidables pour les grammaires Théorème Les problèmes suivants sont indécidables: * Etant donnée une grammaire générale G et un mot w, est-ce que ? * Etant donnée une grammaire générale G, est-ce que ? * Etant donnée deux grammaires et , est-ce que ? * Etant donnée une grammaire G, est-ce que ? * Il existe une grammaire générale pour laquelle le problème suivant est indécidable : étant donné w, est-ce que ? text/html 2010-01-06T14:43:50+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_d&rev=1262785430&do=diff III. Complexité Introduction Deux exemples pour rentrer dans le sujet : * Problème du voyageur de commerce. Etant donné une carte routière et une liste de N villes, comment réaliser un circuit qui visite les N villes en parcourant la plus courte distance possible. * Géométrie tortue : void triangle(float x, float y, float d, float h){ if (y+d)<h {tracer(x-d, y+d); triangle(x-d, y+d, d, h); tracer(x+d, y+d); triangle(x+d, y+d, d, h); tracer(x,y);}} . complexité ~ sk avec y+kd < h < y+(k… text/html 2009-10-11T16:26:36+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_1&rev=1255271196&do=diff Machine de Turing Une machine de Turing (MT) est un quintuplet où * K est un ensemble fini d'états * est un alphabet (fini) contenant les symboles (blanc) et (début de mot) * : état initial * : ensemble des état d'arrêt * : fonction de transition * * text/html 2009-10-11T16:33:26+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_2&rev=1255271606&do=diff Configuration (d'une MT) Soit une machine de Turing. Une configuration de M est un élément de text/html 2009-11-30T12:46:39+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_3&rev=1259581599&do=diff Pas de Calcul Soientt une machine de Turing et et deux configuration de M. On dis qu'on passe de la première à la deuxième en un pas de calcul si et seulement si tel que * * la situation est l'une de ces trois: * * et * soit * soit text/html 2009-10-11T21:34:38+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_4&rev=1255289678&do=diff Langage décidé Soit . * On appelle configuration acceptée ou réussie de M une configuration de la forme . * On appelle configuration rejettée ou échouée de M une configuration de la forme . * On dit que M accepte le mot * On dit que M rejette le mot * On dit que M décide un langage si et seulement si * * text/html 2009-11-30T14:39:17+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_5&rev=1259588357&do=diff Fonctions Récursives (ou Turing calculables) Soit une MT et un alphabet et . Si M s'arrête avec l'entrée ( ) de sorte que avec on dit que est le résultat de sortie de ce calcul, on note . Note: ce mot est unique car M est déterministe. text/html 2009-10-20T17:03:39+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_6&rev=1256051019&do=diff Grammaire générale (déf.) Une grammaire générale est un quadruplet: * * V = ensemble de symboles * : ensemble de symboles terminaux * : ensemble des symboles non-terminaux * : start symbole * R : ensemble des règles, sous-ensemble fini de où contient au moins 1 symbole non-terminal text/html 2009-11-30T15:01:17+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_7&rev=1259589677&do=diff Soit une MT telle que * * une fonction On dit que M calcule f si et seulement si Exemples : * * text/html 2009-11-30T15:29:44+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_8&rev=1259591384&do=diff Semi-décision Soit * un MT, * * et On dit que M semi-décide L (ou accepte L) si et seulement si M s'arrête avec l'entrée . N.B. : M boucle à l'infini avec l'entrée . text/html 2009-11-30T13:20:32+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_calc&rev=1259583632&do=diff Pour toute machine de Turing M, * on note la fermeture réflexive transitive de . * On dit que la configuration produit la configuration si et seulement si * Un calcul de à partir de est une suite de configurations On dit alors qu'on a un calcul de longueur n, et on note text/html 2009-11-23T09:50:27+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_def_reduction_nofooter&rev=1258966227&do=diff Définition Soient . Une réduction de à est une fonction récursive * text/html 2009-10-09T19:01:14+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_defs&rev=1255107674&do=diff En-tête 2 ---------- ---------- ---------- text/html 2010-10-03T11:29:44+02:00 http://get-the.net/doku.php?id=m1ilc:c_et_c_ex_5&rev=1286098184&do=diff Enoncé Trouver/concocter une MT grammaire qui valide engendre . pas sûr que c'était à rendre; j'ai modifié l'énoncé pendant ma réflexion (!) et trouvé (je crois) une MT (machine de Turing) qui vérifie L au lieu d'une grammaire qui l'engendre. text/html 2009-12-08T10:35:10+02:00 http://get-the.net/doku.php?id=m1ilc:cao&rev=1260264910&do=diff CAO Enseignant Site/Liens Cours TD TP ECTS 12 12 12 Objectifs Manipulation des primitives standard en conception géométrique. Calcul et tracé de ces primitives. Utilisation d'un logiciel de CAO. Contenu Notions mathématiques sur les courbes et surfaces paramétriques : continuité, tangente, normale, courbure et torsion ; Notions de maillages : définition et structures de données ; Interpolation de points : Lagrange, Hermite, Coons, Splines ; Courbes, carreaux de surfac… text/html 2009-10-09T18:44:50+02:00 http://get-the.net/doku.php?id=m1ilc:compil_1&rev=1255106690&do=diff Introduction Le problème : Homme et machine n'utilisent pas la même langage. Homme Machine langage de programmation langage machine basé s/ modèles mathématiques reflète architecture matérielle Structuration, modularité au niveau binaire, manipulation de registres => besoin de réaliser la traduction d'un langage source vers un langage cible. text/html 2010-01-04T17:28:33+02:00 http://get-the.net/doku.php?id=m1ilc:compil_2&rev=1262622513&do=diff Analyse Syntaxique Introduction Le rôle de l'analyse syntaxique est de * déterminer si la suite de tokens est conforme à la grammaire définissant le langage source; * repérer [et signaler] les erreurs syntaxiques; * définir l'arbre de syntaxe abstraite. text/html 2010-01-05T06:39:03+02:00 http://get-the.net/doku.php?id=m1ilc:compil_3&rev=1262669943&do=diff Analyse Syntaxique (2) Analyse Ascendante Ceci conduit à des analyseurs plus puissants au sens où elle réussit avec un sur-ensemble stricte de grammaires. Exemple La grammaire G0 mais sans la multiplication * E -> E + T * E -> T * T -> (E) * T -> id text/html 2009-10-12T09:01:39+02:00 http://get-the.net/doku.php?id=m1ilc:compil_4&rev=1255330899&do=diff SLR (suite) Construction de la Table d'Analyse D'abord on calcule les états: * On commence par placer acc dans la colonne $ de la ligne correspondante à l'état qui contient S' -> S. * On place les reduce : pour chaque état s, on recherche une règle de la form et on place reduce de cette règle dans la case ACTION[s,a] pour tout * On place les shift : à chaque fois qu'on a S'=GOTO[s,X] on place shift s' dans la case GOTO[s,X]. text/html 2009-10-17T20:25:56+02:00 http://get-the.net/doku.php?id=m1ilc:compil_5&rev=1255803956&do=diff Cours numéro cinq text/html 2010-01-03T18:15:45+02:00 http://get-the.net/doku.php?id=m1ilc:compil_7&rev=1262538945&do=diff Génération de code intermédiaire Formes Possibles Les différentes formes possibles de code intermédiaire sont * arbre de syntaxe abstraite * notation polonaise inversée (forme linéaire de l'arbre de syntaxe) * un code à trois adresses : une séquence d'instructions étiquettée dont chaque intruction utilise au plus 3 adresses de variables de référence text/html 2009-11-16T10:09:46+02:00 http://get-the.net/doku.php?id=m1ilc:compil_8&rev=1258362586&do=diff V. Gestion de la table des symboles Introduction La table des symboles mémorise les informations relatives aux identificateurs d'un programme : * le nom * le type (simple, structuré, étiquette, fonction, tableau, paramètre formel d'une fonction) * le nombre de dimensions, les bornes inférieurs et supérieurs (pour chaque dimension) pour un tableau * le nombre d'arguments pour une fonction * le mode d'adressage pour un paramètre formel (valeur ou adresse) * l'emplacement mémoire (u… text/html 2009-11-16T19:36:02+02:00 http://get-the.net/doku.php?id=m1ilc:compil_9&rev=1258396562&do=diff VI. Optimisation du Code Intermédiaire Introduction La phase d'optimisation de code prend en entrée du code intermédiaire et retourne en sortie du code intermédiaire “optimisé.” Elle a lieu avant la phase de génération de code. Donc, les optimisations qui sont réalisées sont indépendantes de la machine cible. La plupart de ces optimisations concernent les boucles car généralement ceux sont ces parties du code qui sont les plus consommatrices de temps CPU. text/html 2010-01-04T15:26:59+02:00 http://get-the.net/doku.php?id=m1ilc:compil_fermetures&rev=1262615219&do=diff Algorithmes de fermeture LL(1) Définitions * ensembles appelés FIRST pour tous les symboles (terminaux, non-terminaux, alternatives) dans G. * Un ensemble appelé FIRST pour chaque queue alternative en G; où une queue alternative est une suite de zéro ou plus symboles si est une alternative ou queue alternative en G. text/html 2009-12-05T10:34:09+02:00 http://get-the.net/doku.php?id=m1ilc:compil_iii_2&rev=1260005649&do=diff III. Traduction dirigée par le syntaxe * Objectif : réaliser la traduction d'un texte (ou d'un programme) dans un code intermédiaire equivalent. * Idée : associer des informations aux règles de grammaire. On distingue parmi les grammaires ainsi enrichies : * grammaires de traduction * grammaires attribuées text/html 2010-01-04T18:10:57+02:00 http://get-the.net/doku.php?id=m1ilc:compil_ll&rev=1262625057&do=diff Analyse Descendante Exemple (simple) R1: S -> cAd R2: A -> ab | a Analysons 'cad' et construisons l'arbre de syntaxe abstraite. étape arbre symboles 0 S cad 1 S / | \ c A d cad même symbole, voyons si la suite correspond prenant une première hypothèse pour 'A' 2 S / | \ c A d / \ a b cad première hypothèse pour ce qu'a produit 'A' 3 S / | \ c A d / \ a b cad on avance le… text/html 2010-01-04T18:30:32+02:00 http://get-the.net/doku.php?id=m1ilc:compil_ll_2&rev=1262626232&do=diff Principe de l'analyse itérative -- LL(1) Algorithme utilisé: * un pointeur sur la chaine de tokens (la chaine est terminée par $) * une pile contenant des non-terminaux et des terminaux * une table dont * chaque ligne correspond à un non-terminal * chaque colonne identifie un terminal. Intuitivement, l'élément T[X,a] contient la règles à utiliser lorsque X est au sommet de la pile et a est l'élément courant de la chaine. text/html 2009-12-23T15:05:22+02:00 http://get-the.net/doku.php?id=m1ilc:compil_td_1&rev=1261577122&do=diff Analyse Lexicale Une suite de caractères est lu par un analyseur lexical, et celui-ci produit une suite de symboles (unités syntaxiques, “tokens”). Ces symboles comprennent des identifiants, des mots réservés, des constantes, des délimiteurs , des opérateurs simples ou composés (+ - * / := , e.g., qui sont de petits mots réservés). text/html 2009-12-23T12:04:24+02:00 http://get-the.net/doku.php?id=m1ilc:compil_td_2a&rev=1261566264&do=diff TD 2 : Analyse Syntaxique Descendante Grammaire récursive Grammaire G0 E -> E+T | T T -> T*F | F F -> (E) | id | cte Cette grammaire est récursive à gauche. Pour la dérécursiver, nous observons que * E -> T ou T+T ou T+...+T * F -> F ou F*F ou F*...*F text/html 2010-01-01T16:22:35+02:00 http://get-the.net/doku.php?id=m1ilc:compil_td_4&rev=1262359355&do=diff Interrogation écrite du 7 décembre 2007, documents non autorisés. Exercice 1 On modélise par une grammaire G un sous-ensemble du français. Les classes des unités lexicales sont {verbe, nom, qui, et, . }. Ces classes sont aussi les symboles terminaux de la grammaire G. L'unité lexicale verbe peut prendre les valeurs: dérange, suit, aime, frappe, et écoute. L'unité lexicale nom peut prendre les valeurs Alphonse, Bastien, Yannick et Hélène. Les unités lexicales qui, et, et . ont une seule vale… text/html 2010-01-04T16:31:43+02:00 http://get-the.net/doku.php?id=m1ilc:compil_td_5&rev=1262619103&do=diff Optimisation de Code Le code intermédiaire généré par un compilateur à la forme suivante. * A quel type de programme correspond ce code intermédiaire? Tri à bulles * Tracer le graphe des flôts * Eliminer les sous-expressions communes * Effectuer une propagation des copies et éliminer le code inutile. * Traiter les variables d'induction et les invariantes de boucle. text/html 2009-12-13T17:19:03+02:00 http://get-the.net/doku.php?id=m1ilc:compil_td_6&rev=1260721143&do=diff Code assembleur MIPS Exercice 1 Traduire en assembleur MIPS l'extrait de code C suivant: if (t1 < t2) t3 = t1 ; else t3 = t2; la $t0,t1 lw $t1, $t0 blt $t2, $t1, joe b jim; joe: move $t3, $t1 b fin jim: move $t3, $t2 fin: nop Exercice 2 Soit l'extrait de code C suivant qui calcule dans t2 initialisé à 0 la somme des entiers de 1 à t1: text/html 2010-01-04T18:07:34+02:00 http://get-the.net/doku.php?id=m1ilc:compilation&rev=1262624854&do=diff Synoptique Prof Site Cours TP TD ECTS Eric VIOLARD <http://icps.u-strasbg.fr/~violard/> 28h 12h 20h 6 Contenu Structure d'un compilateur. Analyse lexicale. Analyse syntaxique descendante et ascendante. Analyseurs LL(1), SLR (1), LR (1) et LALR (1). Grammaires attribuées et notion d'actions sémantiques. Traitement des erreurs. IV. Production de code intermédiaire. V. Gestion de la table des symboles. VI. Optimisation de code. Génération de code objet. Pre-requis Bonnes co… text/html 2010-01-04T15:02:26+02:00 http://get-the.net/doku.php?id=m1ilc:compilation_resume_as&rev=1262613746&do=diff Résumé -- Analyse Syntaxique * Il y deux manières de réaliser l'analyse syntaxique : descendante et ascendante. L'analyse descendante cherche à simuler le processus de production; l'analyse ascendante cherche à remonter (défaire) le processus de production. text/html 2010-10-03T07:07:20+02:00 http://get-the.net/doku.php?id=m1ilc:complexite_et_calculabilite&rev=1286082440&do=diff Synoptique Prof Site Cours TP TD ECTS M. Pascal Schreck 24h 3 Contenu Extensions des machines de Turing, machines de Turing non déterministes. Récursivité (au sens de Turing) et mu-récursivité (au sens de Church). Thèse de Church-Turing. Machine de Turing universelle et non-calculabilité. Exemples de problèmes indécidables, classes de complexité : P, NP et EXP, NP-complétude. Pre-requis Théorie des langages Références Lewis & Papadimitriou, “Elements of the theory of com… text/html 2010-05-12T09:35:56+02:00 http://get-the.net/doku.php?id=m1ilc:easea&rev=1273649756&do=diff Easea est une application " un langage de haut niveau dédié à la spécification d'algorithmes d'évolution artificielle. Easea jusqu'à la version 0.7 compile des fichiers de spécification .ez en fichiers objet C++ ou Java, utilisant GA." Il est maintenant à la version 1.0. Il compile en C++, mais en Java? Comment faire? Il manque de documentation. Pour commencer à palier à ça, voici ce qui nous a été communiqué par les auteurs. text/html 2010-12-16T15:25:56+02:00 http://get-the.net/doku.php?id=m1ilc:ec3&rev=1292509556&do=diff text/html 2009-12-14T17:23:09+02:00 http://get-the.net/doku.php?id=m1ilc:edid&rev=1260807789&do=diff Prof Site H.Cours H.TP H.TD ECTS M. Nicolas LACHICHE Site du cours 12h 12h 3 Pre-requis Connaissances de base en informatique et en programmation ; base de données relationnelles (niveau L3). Contenu Entrepôts de données complexes, cubes de données complexes, performances, réutilisation de techniques de fouilles de données dans le processus décisionnel... Architecture n-tiers. Navigation, interrogation et indexation. Outils d’analyse de données (OLAP). Entrepôt de données.… text/html 2009-12-29T13:33:07+02:00 http://get-the.net/doku.php?id=m1ilc:edid_td_3&rev=1262089987&do=diff Tutoriel d'exploration de données Module 1 : modèle d'association Recherche de relations dans vos données à l'aide d'un modèle d'association " Un modèle d'association recherche des schémas dans vos données en décernant des associations entre des articles. Un modèle d'association recherche ces schémas en appliquant la formule “Les clients qui achètent le produit A achètent aussi le produit B.” " text/html 2009-10-15T08:04:11+02:00 http://get-the.net/doku.php?id=m1ilc:edid_tp_1&rev=1255586651&do=diff Note : this is not original material, merely an extract of the IBM Tutorial Documents omitting the procedures to have a slightly higher-level view of the tutorial before (and while) performing it. Module 1: Designing the physical data model for your data warehouse In this module, you will connect to the GSDB database and create a physical data model for the new data mart that you will build. You will create a MARTS schema in the data model and then update the GSDB database with the changes. text/html 2010-07-15T10:23:14+02:00 http://get-the.net/doku.php?id=m1ilc:examens_jan_10&rev=1279182194&do=diff text/html 2010-01-10T12:28:44+02:00 http://get-the.net/doku.php?id=m1ilc:fain&rev=1263122924&do=diff Contenu Fondements et algorithmes de l'imagerie numérique * Prérequis : Mathématiques, informatique et anglais de licence * Contenu : * pixels, voxels et adjacence; connexité, composantes connexes; * courbe discrète, dualité figure fond; théorème de Jordan; trous, arborescence des composantes; nombre d'Euler. * Reconstruction de composantes connexes. * Pixel simple, nombre de Yokoi. * Distances discrètes, masques de chanfrein, algorithme de transformée de distances. * … text/html 2010-01-08T15:37:54+02:00 http://get-the.net/doku.php?id=m1ilc:fain_1&rev=1262961474&do=diff FAIN : Cours 1 Notions de topologie discrète Définition : une image 2d est représentée par une grille d'affichage I(x,y) telle que I(x,y) définit la couleur d'un pixel de coordonnées (x,y) avec , pixel(x,y) = centre du carré de coté égal à l'unité. text/html 2009-11-03T17:06:15+02:00 http://get-the.net/doku.php?id=m1ilc:fain_2&rev=1257264375&do=diff Connexité (suite) Voir la documentation de Ch. Ronse, notamment * Distances et connexité * Figure et fond Thm de Jordan Une figure fermée (courbe simple du plan) sépare le plan en deux régions : intérieur et extérieur. Pour que cela soit vrai dans le plan discrétisé pour des courbes simples fermées (les bords des zones, objets, ou figures) vérifiant 4-adjacence il faut prendre 8-adjacence pour le fond, et vice versa. text/html 2010-01-11T07:24:11+02:00 http://get-the.net/doku.php?id=m1ilc:fain_6&rev=1263191051&do=diff Adjacence des Composantes Connexes * : objet * : fond Définition Soient * l'ensemble des k-composantes connexes de O; * l'ensemble des k'-composantes connexes de F; On dira que est adjacent à s'il existe et tels que p et q sont 8'adjacents. text/html 2010-01-09T20:14:20+02:00 http://get-the.net/doku.php?id=m1ilc:fain_cercles&rev=1263064460&do=diff Algorithmes de tracer de cercles Pour l'étude, on considère la partie dans le deuxième octant (x>0, y>x) d'un cercle de rayon R et centre (0,0). x2 + y2 = R2. Deux approches se présente : * Calculs flottants : pour y=arrondi(sqrt{R*R - x*x) * Algorithme de Bresenham (analogue de son algorithme pour les segments) : incrémentale, arithmétique entière. text/html 2010-01-08T13:05:21+02:00 http://get-the.net/doku.php?id=m1ilc:fain_segments&rev=1262952321&do=diff Algorithmes de tracé de segments de droites Problème: étant donné deux points P et Q de coordonnées entières, afficher le segment de droite PQ. C'est à dire, déterminer les pixels approximant le segment et donnant l'impression visuelle. Rappel: Droite de pente k passant par un point et de vecteur directeur . text/html 2010-01-10T08:54:38+02:00 http://get-the.net/doku.php?id=m1ilc:fain_td1&rev=1263110078&do=diff FAIN TD 1 Exercice 1 Reconnaitre des figures 4-connexes et 8-connexes. 7 7 bb b b 7 7 6 6 c d 6 6 5 5 c a d 5 5 4 4 c a d 4 4 3 3 c a d 3 3 2 2 c d 2 2 1 1 dd d d d 1 1 0 0 0 0 0 1234567 0 1234567 0 1234567 0 1234567 ensemble 1 ensemble 2 ensemble 3 ensemble 4 * ensemble 1 est 4-connexe, et donc 8-connexe (aussi) * ensemble 2 n'est ni 4-connexe, ni 8-connexe puisque la “barr… text/html 2010-01-10T12:30:37+02:00 http://get-the.net/doku.php?id=m1ilc:fain_td2&rev=1263123037&do=diff TD2 Remplissage Tracer un disque On supposera disposer d'une fonction SegHori(x1, x2, y) trançant un segment horizontal. Ecrire un algorithmes qui n'utilise que des opérations sur les entiers pour tracer un disque (constitué de pixels à l'intérieur d'un cercle). text/html 2010-01-10T11:20:36+02:00 http://get-the.net/doku.php?id=m1ilc:fain_td3&rev=1263118836&do=diff Géométrie Discrète Connexité des droites discrètes Nous avons entamé l'étude du traitement des droites avec le cas d'un segment d'épaisseur juste assez pour être 8-connexe : un pixel par colonne si pente faible, un pixel par ligne si pente forte, avec l'algorithme de Bresenham notamment. Considérons maintenant des “droites” d'épaisseur paramétrable; des ensembles de points (x,y) entiers tels que <jsmath>0 \leq ax - by + \mu \lt \omega</jsm>. De plus, on va supposer que tous les paramètres s… text/html 2010-05-08T10:30:40+02:00 http://get-the.net/doku.php?id=m1ilc:fain_td4&rev=1273307440&do=diff Topologie digitale Calculer les nombres d'Euler * Calculer le nombre d'Euler en 4-connexité et le nombre d'Euler en 8-connexité des deux ensembles suivants. Faites le calcul de deux manières différentes : considérant les configurations locales et en comptant les faces, les arêtes et les commets. * Calculer l'arbre des composantes connexes de ces 2 ensembles aussi pour les deux connexités. Qu'en déduisez-vous? text/html 2010-01-10T11:05:25+02:00 http://get-the.net/doku.php?id=m1ilc:fain_td5&rev=1263117925&do=diff Distances Cinq Mesures Transformée de distance Navigation -- -- -- text/html 2010-05-13T10:12:18+02:00 http://get-the.net/doku.php?id=m1ilc:fainbis&rev=1273738338&do=diff Traitement d'images Enseignant Site/Liens Cours TD TP ECTS M. Etienne Baudrier Enseignement 18 12 6 Objectifs Connaissances de base en traitement d'images statiques 2D. Contenu Formation d'images, perception visuelle. Résolution et quantification. Format bitmap et couleur. 24 févrierOpérations sur les contrastes et les histogrammes. Seuillage, double seuillage, et seuillage automatique. 3 marsFiltres linéaires, lissage, rehaussement et accentuation d'arêtes. 31 marsF… text/html 2010-05-13T09:41:49+02:00 http://get-the.net/doku.php?id=m1ilc:fainbis_1&rev=1273736509&do=diff Introduction aux images L'image et les capteurs Une image est l'acquisition par un capteur d'une scène réelle. Le capteur peut être sensible à différentes sources (signaux): * ondes électromagnétiques * ré-émission : réflexion et réfraction * visibles, infrarouge, ultraviolet, rayons gamma, rayons x, autres text/html 2010-05-13T10:04:07+02:00 http://get-the.net/doku.php?id=m1ilc:fainbis_2&rev=1273737847&do=diff Transformation à niveaux de gris Qu'est-ce? Son utilité? étirement de contraste Négatif Masquage Réhaussement Quantification d'images à traiter dans un cours précedent Histogramme text/html 2010-03-30T22:23:42+02:00 http://get-the.net/doku.php?id=m1ilc:fainbis_scilab&rev=1269980622&do=diff Compte Rendu Suite à quelques difficultés pour faire ce TP ce matin, j'ai constaté que la configuration de l'installation des logiciels chez moi permettait d'aller plus loin. ___________________________________________ scilab-5.1 Consortium Scilab (DIGITEO) Copyright (c) 1989-2009 (INRIA) Copyright (c) 1989-2007 (ENPC) ___________________________________________ Initialisation: Chargement de l'enviro… text/html 2009-12-29T15:43:14+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_1&rev=1262097794&do=diff Introduction Motivations * Il y a des questions, des prémisses de décisions, que l'humain a besoin ou envie (économique) de traiter; * Ces “études” peuvent impliquer des quantités de données et besoins en calcul énormes; * La technologie permet économiquement de faire des traitements qu'on ne pouvait pas faire il y a peu d'années. * De quoi a-t-on besoin ? Extraire des connaissances intéressantes et utiles à partir des text/html 2010-01-03T12:02:19+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_2&rev=1262516539&do=diff Réseaux de Neurones 1. Introduction Fonctions d'activation * seuil : f(s) = 0 si s <= k, f(s)=1 si s>k. On dit qu'on a un réseau neuronal vraiment symbolique * linéaire : f(s) = -1 si s <= -1/k, 1 si s > 1/k, k*s ailleurs * sigmoide : . Si k est grand, f(s) est proche de 0 ou de 1 pour presque toutes les valeurs de s. On dit qu'on a un réseau neuronal relativement symbolique * ou autre : gaussienne, à valeurs discrètes, etc; text/html 2010-01-02T11:45:27+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_4&rev=1262429127&do=diff Arbres de Décision Intérêts Le grand intérêt des arbres de décision est qu'ils combinent l'approche logique et l'approche statistique, pour donner un modèle expressif et lisible flou (c'est à dire, probabiliste et non déterministe). Ainsi ils produisent un modèle qui peut être traduit sous forme de règles, exprimant une conditionnalité complexe (avec disjonctions) des valeurs discrètes à prédire. text/html 2010-01-01T12:40:57+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_7&rev=1262346057&do=diff Classification non-supervisé Regroupement et modélisation Ici, le but est de trouver une description compacte permettant de résumer et décrire des objets à partir des données initiales (copieuses). Ceci s'inscrit dans la fouille exploratoire et descriptive et “summarization” . Des approches peuvent être empruntées: text/html 2009-12-30T13:23:14+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_de_donnees&rev=1262175794&do=diff Fouille de Données Prof Site Cours TP TD ECTS M. Gançarski <http://dpt-info.u-strasbg.fr/~gancars/> 12h 12h 3 Contenu Introduction à l’extraction de connaissances à partir de données, Extraction de règles. Arbres de décision. Evaluation de l’apprentissage. Classification non-supervisée et extraction de concepts. Apprentissage statistique et modèle bayésien naïf. Réseaux de neurones. Machines à vecteurs supports. Pre-requis Aucun pré-requis autre que connaissances de bas… text/html 2009-12-19T15:18:55+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_tp&rev=1261232335&do=diff TP Clustering Introduction K-Means Clustering Exercice 2.2 Dans le premier résultat, on lit : Class attribute: play Classes to Clusters: 0 1 2 <-- assigned to cluster 1 3 5 | yes 1 3 1 | no Cluster 0 <-- No class Cluster 1 <-- no Cluster 2 <-- yes Or, les clusters portent des labels “yes”, “no”, et “No class”. Le cluster #1 contient 3 des 5 “no”, le cluster #0 contient 5 des 9 “yes” : ces clusters contienent des majorités des instances de ces deux classes et se voient attr… text/html 2009-12-30T13:32:44+02:00 http://get-the.net/doku.php?id=m1ilc:fouille_wemmert&rev=1262176364&do=diff Supports de Cours C. Wemmert * * [classif--regroupement] * [classif--hiérarchies] * [classif --formation de concepts] text/html 2010-01-28T14:01:57+02:00 http://get-the.net/doku.php?id=m1ilc:lattices&rev=1264683717&do=diff Travail Encadré de Recherche Synoptique Enseignant Site/Liens Cours TD TP ECTS Mme. Florence Le Ber Mme. Agnès Braud 6 Objectifs Treillis de Galois pour données complexes, adaptation d'algorithmes existants et mise en oeuvre sur un exemple de donnée Sujet Le LHyGeS (Laboratoire d'Hydrologie et de Géochimie de Strasbourg) est un laboratoire pluri-disciplinaire où sont notamment menées des recherches sur la problématique de l'évaluation de l'état écologique des cours d'eau. Da… text/html 2010-01-28T13:45:31+02:00 http://get-the.net/doku.php?id=m1ilc:lattices_0&rev=1264682731&do=diff Choisir l'algorithme Après (première) lecture de “Comparing performance of algorithms for generating concept lattices” by SERGEI O. KUZNETSOV, j'ai constaté : " Compte tenu des résultats qu'il affiche et d'autres considérations, plusieurs paires se suggèrent. Une axe est celle du type de problème :(a) petit et éparse (ou contexte creuse?), (b) moyen, ou (c) grand et à contexte dense. Donc, une sorte de paire serait (a)-(b) [Godin et Bordat], (b)-(c) [Bordat et un parmi Norris, CbO et Nex… text/html 2010-05-17T05:20:30+02:00 http://get-the.net/doku.php?id=m1ilc:opt_stoch&rev=1274066430&do=diff Optimisation stochastique Enseignant Site/Liens Cours TD TP ECTS Pierre Collet 24 12 Objectifs Donner à l'étudiant les concepts de base et les mécanismes d'optimisation. Contenu Etude de la représentation des problèmes. Présentation de méthodes récentes d'optimisation pour une représentation de longueur fixe (algorithmes génétiques, stratégies d'évolution, Optimisation par Colonie de Fourmis, Optimisation par Essaim Particulaire, Algorithmes à Estimation de Distribution) e… text/html 2009-10-21T22:33:28+02:00 http://get-the.net/doku.php?id=m1ilc:pdf_de_xavier&rev=1256157208&do=diff Les pdf de Xavier Les notes pour chaque cours sont dans un fichier cumulatif. FIXME Il y a une fonctionnalité provisoire: * les fichiers pdf sont mal servis si on clique dessus : il ne faut pas. * On peut choisir “enregistrer la cible”; dans ce 2e cas ils sont servis, mais perdent leur nom et s'appellent tous fetch.php (bien que pdf parfaitement lisible une fois téléchargé). * Ils s'ouvrent correctement si on les ouvre dans une nouvelle fenêtre (clique droit), mais pas dans un nouvel … text/html 2011-04-09T08:26:55+02:00 http://get-the.net/doku.php?id=m1ilc:preuves&rev=1302330415&do=diff Ingénierie de la preuve Enseignant Site/Liens Cours TD TP ECTS Cours : J. Narboux TP : N. Magaud, P. Schreck Lien externe 18 18 Objectifs - Apprentissage des outils de preuve formelle et de certification de logiciels - Utilisation de l'outil Coq pour décrire, prouver et extraire des programmes certifiés Contenu Techniques et systèmes de spécification et de preuve de logiciels. Rôles des mathématiques, de la logique et de la programmation. Définition de types, fonctions, p… text/html 2010-05-19T08:55:15+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_3&rev=1274252115&do=diff Currification Exercice Montrer que la formule suivante est valide / prouvable : (A -> (B -> C)) <-> (A ∧ B -> C) Remarque: -> est associatif à droite, on aurait pu écrire: (A -> B -> C) $<->(A ∧ B -> C) Pourquoi utiliser la currycation ? Afin de pouvoir réaliser des applications partielles plus facilement. Remarque: cette opération porte le nom de Haskell Curry (1900-1982). text/html 2010-05-19T10:54:25+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_4&rev=1274259265&do=diff Structures de données Types inductifs Coq est basé sur un formalisme appelé Calcul des Constructions avec types Inductifs. Deux points de vue possibles: * On se donne les entiers. * On se donne les types inductifs en général (les entiers sont un cas particulier). text/html 2011-04-09T09:21:24+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_defs&rev=1302333684&do=diff Création de Types Avec Inductive Inductive jour : Set := lundi : jour | mardi : jour | mercredi : jour | jeudi : jour | vendredi : jour | samedi : jour | dimanche : jour.Inductive fonction : Set := fid: fonction |fconst: R -> fonction |fsin: fonction |fcos: fonction |fexp: fonction |fplus: fonction -> fonction -> fonction |fmoins: fonction -> fonction -> fonction |fmult: fonction -> fonction -> fonction |fcomp: fonction -> fonction -> fonction . Ensuite, pour concretiser (interpréter) les fonc… text/html 2010-05-19T09:59:30+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_egalite&rev=1274255970&do=diff L'égalité en Coq Check eq. eq : forall A : Type, A -> A -> Prop Check refl_equal. refl_equal : forall (A : Type) (x : A), x = x C'est un type polymorphe (A:Type). Cela signifie que l'on a une relation d'égalité générique dont le premier argument est le type des éléments à comparer. text/html 2010-05-19T10:04:51+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_sortes&rev=1274256291&do=diff Les sortes Une sorte est un type pour les types. Les propositions A, B, etc. sont des types (ceux de leurs termes de preuves). Ces types sont de type Prop. On dit que A, B, etc. sont de sorte Prop. D'un autre coté, les booléens bool, les entiers nat sont des types dont le type est Set. Set et Prop sont de type Type. text/html 2011-04-09T09:51:03+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_td_types&rev=1302335463&do=diff Sans récursion On commence par une structure de données définie sans récursion : les mois (ou les jours) Récursives Inductive positive : Set := I : positive | C2X : positive | C2XP1 : positive. Definition un : positive := I. Definition trois : positive := C2XP1 I. Definition quatre: positive := C2X (C2X I). Definition sept : positive := C2XP1 (trois). Bon, on voit comment ça mmarche. Comment définir la fonction successeur? Une fonction avec filtration sur le constructeur (récursivement)… text/html 2011-04-09T08:36:52+02:00 http://get-the.net/doku.php?id=m1ilc:preuves_tp3&rev=1302331012&do=diff GaussInt : Set D'abord, création d'un ensemble inductif à partir de Z: Require Export ZArith. Inductive GaussInt : Set := c : Z ->Z-> GaussInt. Definition g0 := c 0 0. Definition g1 := c 1 0. Definition gi := c 0 1. Définition des Opérations Definition Gadd (x y : GaussInt):GaussInt := match x with c a b => match y with c a1 b1 => c (a+a1) (b+b1) end end. Definition Gmult (x y : GaussInt) : GaussInt := match x with c a b => match y with c a1 b1 => c (a*a1 - b*b1) (a*b1 + a… text/html 2010-05-20T11:45:08+02:00 http://get-the.net/doku.php?id=m1ilc:search&rev=1274348708&do=diff Algorithmes de recherche Enseignant Site/Liens Cours TD TP ECTS 12h 12h 3 Objectifs Acquisition d'algorithmiques et de méthodes informatiques exactes pour l'analyse du texte. Contenu Rappel de définitions et exemples de mots particuliers. Algorithmes de localisation d'un langage dans un texte: arbre d'un dictionnaire, automate-dictionnaire, implantations avec fonction de suppléance et successeur par défaut. : Algorithme d'alignement global optimal de 2 mots. Algorithmes… text/html 2010-05-19T19:07:21+02:00 http://get-the.net/doku.php?id=m1ilc:search_1&rev=1274288841&do=diff Alphabet et Mots lettresmot vide * L'ensemble des mots sur l'alphabet A est noté A* * L'ensemble des mots sur l'alphabet A excepté le mot vide ε est noté A+ * La longueur d'un mot x est la longueur de la suite associée au mot x et est notée |x|. On note x[i], avec 0 ≤ i ≤ |x|-1, la lettre à l'indice i de x avec par convention une numérotation des indices à partir de 0. L'indice i représente une position sur x si x ≠ ε. La j-ième lettre de x est la lettre à la position j-1 sur x et x=x… text/html 2010-05-20T13:33:04+02:00 http://get-the.net/doku.php?id=m1ilc:search_automates&rev=1274355184&do=diff Implantation Informatique La mise en oeuvre informatique est basée sur les files, les états et les . Opérations de base pour les files : * FILE_VIDE() crée puis retourne (un pointeur sur) une file vide * FILE_EST_VIDE(F) retourne vrai si la file F est vide et faux sinon * ENFILER(F,x) ajoute l'élément x en queue de la file F (c'est une file, pas une pile) * TETE(F) retourne l'élément situé en tête de la file F sans l'enlever * DEFILER(F) supprime l'élément en tête de la file F * … text/html 2010-05-20T10:49:59+02:00 http://get-the.net/doku.php?id=m1ilc:search_b_m&rev=1274345399&do=diff Boyer-Moore Algorithme de Boyer-Moore Recherche d'une chaîne dans un texte Quelle complexité pour l'algorithme « standard » ? Algorithme Temps Pre-traitement Temps d'Appareillement Naïf 0 O((n-m+1) m ) Rabin-Karp θ(m) O((n-m+1) m ) Automate E.F. O(m|∑|) θ(n) Knuth-Morris-Pratt θ(m) θ(n) Boyer-Moore O(n/m) au mieux O(m+n) au pire [Comment] Peut-on mieux faire ? text/html 2010-05-20T11:26:28+02:00 http://get-the.net/doku.php?id=m1ilc:search_fsm&rev=1274347588&do=diff Automate (ou machine) à états finis Machine abstraite définie par un quintuplet (Q, ∑, T, s, A), avec : * Q, ensemble fini d’états, * , alphabet fini, * T, fonction de transition ()‏ * qd, état de départ ∈ Q * A, ensemble d’états « acceptants » ∈ Q text/html 2010-05-24T10:19:21+02:00 http://get-the.net/doku.php?id=m1ilc:semantics&rev=1274689161&do=diff Sémantique Enseignant Site/Liens Cours TD TP ECTS Cours : E. Violard TD : N. Magaud à voir. peut être des TD/TP via racine de N. Magaud 18 18 Objectifs Acquérir les bases théoriques des techniques de spécification et preuve de programme. Contenu Preuve de programmes. Correction partielle et terminaison. Préconditions, postconditions, invariants, variants. Logique de Hoare. Weakest préconditions de Dijkstra. Application à la construction rationnelle de programmes. … text/html 2010-02-06T18:59:27+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_1&rev=1265479167&do=diff Fondements de la programmation Un objectif de ce cours est de découvrir sur quoi repose la programmation en se basant sur l'étude des programmes et des langages. Les langages révèlent des modes de programmation. Mais qu'est-ce qu'un mode de programmation? text/html 2010-05-24T08:19:25+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_2&rev=1274681965&do=diff II. Sémantique d'un langage de programmation NB On ne peut donner un sens à un énoncé que s'il est bien typé. Les types sont des éléments essentiels dans la construction des programmes. Ils sont liés à des notions de spécification de de preuve (spécification algébrique de types) que nous développerons dans un chapitre dédié. La sémantique d'un langage de programmation est ce qui donne la signification aux programmes, les notions permettant de définir formellement les opérations sur les don… text/html 2010-04-10T09:36:56+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_3&rev=1270885016&do=diff Sémantique Dénotationnelle d'un langage de programmation Consiérons maintenant un langage de programmation impérative simplifié (que nous appellerons “L”) comportant : * instructions de base * l'affectation : x := expr * l'instruction vide : skip text/html 2010-05-24T08:01:39+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_4&rev=1274680899&do=diff Détermination de la sémantique de Programmes Exercice 1 Déterminer la sémantique du programme while n > 0 do n := n-1 pour n∈N. Pour cela, on construit la suite des programmes (Wi) et leur fonction sémantique (wi) i+1 Wi+1 = if n>0 then i { n:= n-1; if n>0 then { i-1 { n:= n-1; if n>0 then { ... 0 { n:= n-1; bottom }... }}}}} avec i accolades fermantes wi+1(s) = non-définie si et (s| n-> 0) si text/html 2010-05-24T10:09:55+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_5&rev=1274688595&do=diff Sémantique des Programmes Récursifs On considère une autre construction dans les langages de programmation, celle des programmes récursifs. Un programme récursif (fonction ou procédure) est récursivement associé à un nom. Le corps du programme fait explicitement référence à ce nom (c'est ce qu'on désigne par “appel récursif”). text/html 2010-03-18T08:36:03+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_6&rev=1268897763&do=diff III. Preuves de correction des programmes Sémantique et preuve Comme nous l'avons vu, l'objectif premier des définition et développements formels de l'activité de programmation est de garantir la correction des programmes. Alors que la sémantique d'un programme donne toute la signification de ce programme, la preuve de correction, ell, se limite à démontrer une propriété de ce programme. text/html 2010-05-24T13:49:11+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_7&rev=1274701751&do=diff Preuves de correction (suite) Exemple Démontrons ce théorème d la logique de Hoare : a:= n; b:= m while b<>0 do a:=a+1; b:=b-1 {a=n+m} | {n+m = n+m} a:=n {a+m = n+m} | Axiome 1 | {a+m = n+m} b:=m {a+b = n+m} Axiome 1 {n+m = n+m} a:=n; b:=m {a+b = n+m} R1 vrai => n+m = n+m {vrai} a:=n; b:=m {a+b = n+m= Règle 4 corps de l'itération {a+1+b-1 = n+m} a:= a+1 {a+b-1 = n+m} Axiome 1 {a+b-1 = n+m} b:= b-1 { {a+b = n+m } Axiome 1 {a+1+b-1 = n+m} a:=a+1; b:=b-1 {a+b = n+m} [ Règle 1… text/html 2010-05-24T19:02:04+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_8&rev=1274720524&do=diff Introduction L'aspect preuve de programmes a un dual naturel qui est la réalisation d'un programme à partir d'une spécification. Par exemple, en se basant sur la logique de Hoare pour les programmes impératifs : * preuve : étant donné un programme P, prouver que ce programme admet deux prédicats p et q comme pré- et post- conditions. * dérivation : étant donné deux prédicats p et q, prouver un programme P qui admette ces deux prédicats comme pré- et post- conditions (on utilise les règles… text/html 2010-05-26T18:51:16+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_9&rev=1274892676&do=diff Raffinement de Programmes Le raffinement établit une relation entre des programmes. => La propriété de satisfaction peut être par exemple * la correction partielle. * * la correction total : * . En particulier, : si P termine, alors P' termine aussi. text/html 2010-05-27T21:39:41+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_a&rev=1274989181&do=diff Les types sont des éléments importants dans la construction des programmes. Dans cette partie, nous présentons un cadre qui permet de définir formellement les types et les opérations sur les objets de ces types. Ce cadre est celui des spécifications algébriques. text/html 2010-05-27T22:33:46+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_b&rev=1274992426&do=diff Nous avons vu que plusieurs Σ-algèbres pouvaient être associées à une signature Σ. Parmi ces Σ-algèbre certaines ne correspondent pas au type que l'on souhaite spécifier. Par exemple, dans l'interprétation Num4 de Nat, 3 est plus grand que son successeur, ce qui est correcte dans cette algèbre, mais incorrecte dans ce que nous voulions spécifier, le type des entier naturels. text/html 2010-05-24T11:18:12+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_c&rev=1274692692&do=diff Dans ce chapitre, nous présentons la logique dite équationnelle, utilisée pour faire la preuve de théorèmes et nous établissons le lien entre les théorèmes d'une spécification et les propriétés des opérations dans les modèles de la spécification. text/html 2010-02-08T09:08:11+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_td_1&rev=1265616491&do=diff Raisonner pour programmer Où l'on cherche à exprimer formellement un problème et à établir les liens entre les différentes formes d'énoncés. Quelques problèmes classiques Pour chacun des problèmes suivants : * Préciser données et résultat * Écrire un énoncé qui qualifie le résultat * Écrire un énoncé qui définit le résultat * Écrire un programme impératif en langage C. text/html 2010-04-15T13:25:47+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_td_2&rev=1271330747&do=diff Le langage "nat" des suites binaires * sémantique : entiers naturels * syntaxe : représentation unaire Grammaire arithmétique C -> 0 | 1 | ... | 9 N -> C+ E -> N | E+E | E-E | E*E V -> a | b | ... | z Donner sa sémantique dénotationnelle * et * * * * text/html 2010-03-04T18:25:38+02:00 http://get-the.net/doku.php?id=m1ilc:semantics_td_2a&rev=1267723538&do=diff Maurice Lanselle M1-ILC Définition par cas * mult(0, m) = 0 * mult(1, m) = m * mult(n0, m) = add(mult(n,m),mult(n,m)) * mult(n1, m) = add(add(mult(n,m),mult(n,m)), m) Montrons par induction structurelle sur nat que * Premier cas : * Second cas : text/html 2010-07-15T10:41:11+02:00 http://get-the.net/doku.php?id=m1ilc:semestre_1&rev=1279183271&do=diff Cours qu'on a pas eu A la fin de cette première année, on peut constater qu'on nous a parlé d'ordres partiels, de point fixes, de weakest preconditions, de treillis de Gallois, et certainementent d'autres sujets qu'on aurait mieux compris si on avait eu un cour en treillis et ordres avant. text/html 2010-01-19T11:34:56+02:00 http://get-the.net/doku.php?id=m1ilc:semestre_2&rev=1263897296&do=diff S2 : UE obligatoires Enseignements ILC (ou partagés) jour horaire ECTS Responsable Hrs CI/CM Hrs TD Hrs TP Hrs Perso Fil. Langues lundi 8:00-12:00 3 M. Prim 24 51 ILC/ISI Algorithmique avancée mardi 8:30-11:45 3 M. Sauvage 18 18 39 ILC/ISI Optimisation stochastique mardi 14:30-17:45 3 M. Collet 24 12 39 ILC Problèmes et méthodes algorithmiques en bioinformatique mercredi 13:30-16:45 3 M. Michel 24 12 39 ILC Sém… text/html 2010-05-13T10:52:06+02:00 http://get-the.net/doku.php?id=m1ilc:semestre_2_dates&rev=1273740726&do=diff Dates Importantes du 2ème semestre Sem Du Au Faits marquants 4 25/01 29/01 Début enseignements mercredi matin, 27 janvier 27 : Traitement d'images -- pas cours ni TP 27 : Bioinfo -- pas cours 29 : algorithms de recherche -- pas cours 5 01/02 05/02 6 08/02 12/02 Vacances d'Hiver 7 15/02 19/02 16 : optimisation stochastique -- pas cours 17 : Traitement d'images -- pas cours ni TP 8 22/02 26/02 9 01/03 05/03 10 08/03 12/03 10 : Traitement d'ima… text/html 2009-10-21T21:43:06+02:00 http://get-the.net/doku.php?id=m1ilc:test_upload_pdf&rev=1256154186&do=diff Test Upload Suite à un incident technique voici un test: [un nom change quoi?]