Informatique II - Travaux Pratiques



Série d'exercices no 4

Exercice 4-1 : Tiling problem

On aimerait carreler une surface de dimension NxN carreaux en utilisant D différentes sortes de carreaux (bleu, rouge, etc). Essayer une combinaison complète, c'est-à-dire placer NxN carreaux prend NxN secondes (1 seconde / carreau). Combien de temps faut-il pour essayer toutes les combinaisons de carrelage possibles ?

Essayer d'abord avec D = 5 et N = 3

Exercice 4-2 : Inventer un algorithme pour voyageur de commerce

Ecrire un algorithme (c.a.d., les étapes essentieles d'un programme en faisant abstraction des détails de programmation) qui donne le chemin le plus court parmi tous les possibles chemins que peut prendre un voyageur de commerce pour visiter N=7 villes différentes.
Combien de différents chemins existe-t-il pour relier les 7 villes ?

Question additionelle (difficile): Pourriez-vous imaginer un algorithme qui résoud le problème du voyageur de commerce pour N=129 villes ou bien pour un nombre N arbitraire?

Exercice 4-3 : Turing machine

Donner le jeu de règles d'une machine de Turing qui débute son parcours à l'extrémité gauche du ruban, se déplace vers la droite tout en remplaçant les 0 et les 1 par des blancs et ne s'arrête que lorsqu'elle rencontre un blank.

Exercice 4-4 : Machine à états finis - parity checker

Développer une machine à états finis qui lit une séquence continue de caractères 1 et 0 (par ex 010011110101101) et renvoie à chaque étape R=1 si le nombre de 1 lus jusque là est pair, R=0 si le nombre de 1 lus jusque là est impair.

Exercice 4-5 : Machine à états finis - parenthesis checker (voir cours)

Implémenter une machine à états finis qui vérifie si une suite de parenthèses jusqu'à n=3 jeux de parenthèses est balancée ou non. La machine renvoie R=1 si la suite de parenthèses est balancée, c'est-à-dire si les parenthèses sont correctement fermées (par ex `()(()())'). La machine renvoie R=0 si la suite de parenthèses est mal balancée (par ex `())((') ou s'il y a plus que n=3 jeux de parenthèses (par ex `(((())))').

Est-il possible de généraliser cette machine à états finis pour un nombre arbitraire de parenthèses ?




retour à la page principale du cours : Informatique II

Saskia Delpretti
Last modified: Feb 3, 2005