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
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 ?
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.
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.
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 ?