http://get-the.net/ 2026-09-23T09:03:51+02:00 http://get-the.net/ http://get-the.net/lib/images/favicon.ico 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 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 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 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-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-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 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 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-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-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-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-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 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-11-09T21:14:33+02:00 http://get-the.net/doku.php?id=m2ilc:uml_2002&rev=1289333673&do=diff Reformulation des besoins--à partir d'un cahier de charges texte--en diagrammes UML. 1. Identifier le contexte du système (“détournement” collaboration diagramme) * Système (à libeller) : un rectangle conteneur * Actor : “stick figure” * Actor (autre système) : boîte avec nom de l'acteur/système entre guillemets * Flux symbolisés par flêches * flux entrants: évènement système text/html 2010-11-12T14:23:44+02:00 http://get-the.net/doku.php?id=m2ilc:qualite_1&rev=1289568224&do=diff " Exercice interactif : aller de Strasbourg à Paris. Quelles questions faut-il poser pour établir un cahier de charges suffisant?" un produit ou service de qualité est un produit dont les caractéristiques lui permettent de satisfaire les besoins exprimés ou implicites des consommateurs. Par conséquent, un système d'information de qualité se juge 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-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 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-11-09T15:38:40+02:00 http://get-the.net/doku.php?id=m2ilc:uml_exo_regulateur&rev=1289313520&do=diff Exercice-(Le régulateur de vitesse) * Le régulateur est un dispositif qui permet de maintenir un véhicule à vitesse constante sans que le conducteur ait besoin d'intervenir * Le conducteur peut demander le maintien de la vitesse actuelle àl'aide d'une pression sur le levier situé sur le tableau de bord * Lorsqu'il freine le régulateur s'arrête * Lors d'une accélération son fonctionnement est court-circuité jusqu'à la relâche de la pédale * La régulation se fait par ouverture ou fermet… 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 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 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-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-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-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.