Up: Notes de cours de Nicolas M. Thiéry; DESS de Statistique, Informatique et Techniques NumériquesNotes de cours de Nicolas M. Thiéry; DESS de Statistique, Informatique et Techniques Numériques
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Remise à niveau informatique



Table des matières

Chapitre 1  Organisation

Ce module sera composé d'un cours d'introduction aux concepts fondamentaux d'informatique (structures de données, complexité, calculabilité, ...) et de TP d'applications. Vous serez évalués sur les TPs et sur un examen théorique final.

Chapitre 2  Jeudi 07/10/2003: TP1, structures de données

À rendre pour le 16/10/2003.

Sujet: http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP1-Nicolas.Thiery-1.0.tar.gz

Correction: http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP1-Nicolas.Thiery-1.0-Correction.tar.gz

Chapitre 3  Jeudi 16/10/2003: TP2, Tris et complexité

À rendre pour le 23/10/2003.
Exercice 1   Dans le cadre de l'utilisation de l'outil informatique, vous avez déjà implanté le tri à bulle. Complétez la class Sort avec des fonctions pour le tri rapide, le tri fusion et le tri par arbre binaire de recherche. Pour ce dernier tri, on suggère de définir une nouvelle classe BinarySearchTree qui hérite de BinaryTree, avec une méthode add pour insérer un nouvel élément.

Ceux qui voudront aller plus loin pourront implanter une classe BalancedBinarySearchTree, héritant de BinaryTree, dans laquelle les arbres ont des branches dont les longueurs diffèrent d'au plus 1. On pourra par exemple utiliser l'astuce des noeuds rouge/noir (red-black tree).

Exercice 1   Pour chacun de ces tris, estimez le nombre d'opérations élémentaires à l'aide d'un compteur, et faites quelques statistiques sur des échantillons aléatoires. Déduisez-en une évaluation de leur complexité en moyenne, au mieux et au pire.

3.1  Quelques références

Chapitre 4  Mardi 23/10/2003: TP3, Polynômes et complexité

À rendre pour le 30/10/2003. Non noté.
Exercice 2   Compléter les méthodes add, multiply et multiplyKaratsuba dans la classe Polynom fournie http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP3-Nicolas.Thiery-1.0.tar.gz. Pour ceux qui veulent aller plus loin: compléter aussi la méthode multiplyFFT. Tracer, pour des polynômes aléatoires de degré croissant, la courbe du temps nécessaire pour les différentes opérations de multiplication en fonction du degré des polynômes en entrée.

Correction: http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP3-Nicolas.Thiery-1.0-Correction.tar.gz

Chapitre 5  Jeudi 30/10/2003, TP 4: Automates et langages rationnels

À rendre pour le 6 novembre.
Exercice 2   Écrire des programmes (par exemple en perl ou en java) utilisant des expressions régulières appropriées pour: Si vous optez pour java, vous pouvez utiliser la bibliothèque gnu.regexp. Un mini d'exemple d'utilisation est fourni:

http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP4-Nicolas.Thiery-1.0.tar.gz

Pour la documentation complète de cette bibliothèque, voir:

file:/usr/java/docs/gnu.regexp/
Le reste des exercices est facultatif.
Exercice 3   Soit Sigma={ a,b,c} un alphabet. Les langages suivants sur Sigma sont-ils rationnels?
  1. L1={ aba,bba,acab}
  2. L2=a*
  3. L3=a*b*
  4. L4={ anbn,nappartient àN}
  5. L5={(ab)n,nappartient àN}.

Exercice 4   Soit Sigma={ a,b} un alphabet. Construire les automates déterministe finis qui reconnaissent respectivement:
  1. Le langage L1:={ aa,ab,bbaab};
  2. Le langage L2:=a*;
  3. Le langage L3:=a+;
  4. Le langage L4:=a*b*;
  5. L'ensemble des mots se terminant par b;
  6. L'ensemble des mots contenant au moins un b;
  7. L'ensemble des mots contenant une sequence de 4 b consécutifs;
  8. L'ensemble des mots dont le nombre d'occurrence de b est divisible par 3;
  9. L9:={ a,b}*{ a}{ a,b}2;
  10. L10:=(aab+aa+aabb)*.

Exercice 5   Implantation des automates sur machine.
  1. Concevoir une structure de donnée appropriée pour stocker un automate déterministe fini.
  2. Implanter, dans le langage de votre choix, une fonction prenant en entrée un automate et un mot, et vérifiant que le mot est bien reconnu par l'automate.
  3. Utiliser cette fonction pour écrire des programmes reconnaissant les langages de l'exercice précédent.

Exercice 6   Implanter une fonction qui étant donné un entier n construit un automate reconnaissant le langage L:=ab,aabb,aaabbb,...,anbn.

Exercice 7   Pour ceux qui n'ont peur de rien!
  1. Implantez une fonction prenant un automate non déterministe, et renvoyant un automate déterministe reconnaissant le même langage.
  2. Implantez une fonction prenant en entrée un automate fini déterministe pour L1, et retournant un automate fini déterministe pour L1*.
  3. Implantez une fonction prenant en entrée des automates finis déterministes pour L1 et L2, et retournant un automate fini déterministe pour L1.L2.
  4. Implantez une fonction prenant en entrée des automates finis déterministes pour L1 et L2, et retournant un automate fini déterministe pour L1union L2.

5.0.1  Quelques références

Chapitre 6  Jeudi 30/10/2003, TP 4: Grammaires

À rendre pour le 13 novembre. Non noté.

L'objectif de ce TP est d'apprendre à utiliser les grammaires en pratique, par exemple avec javacc. Un mini exemple d'utilisation de javacc est fourni:

http://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/RN-TP5-Nicolas.Thiery-1.0.tar.gz

Pour la doc et des exemples plus complets d'utilisation de javacc, voir:

file:/usr/java/javacc/
Exercice 3   Modifier l'exemple fourni pour qu'il reconnaisse n'importe quel jeu de parenthèses, accolades, comme par exemple: [[{}[([])]]{()}]).

Écrire une application Calc qui calcule la valeur d'une expression comme '(3 + 4) * (3 + 4*(1+2))'.

En réutilisant les classes ExpressionTree & autres du premier TP, écrire une application InfixToPolish qui transforme en notation infixe une expression comme '(3 + 4) * (3 + 4*(1+2))'.

Exercice 4   Écrire une classe qui permet de lire des fichiers au format Hexier.

Valid HTML 4.0! Up: Notes de cours de Nicolas M. Thiéry; DESS de Statistique, Informatique et Techniques NumériquesNotes de cours de Nicolas M. Thiéry; DESS de Statistique, Informatique et Techniques Numériques
Remise à niveau informatique / UCBL, DESS de Statistique, Informatique et Techniques Numériques / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:22:41 2007