Partie 3

Partie 3.

Expérimentation sur la machine de Turing

COURS 7 : La machine-caractères

COURS 8 : Machine-nombres

TRAVAUX DIRIGES

Partie 3.

Expérimentation sur la machine de

Turing

COURS 7 :La machine-caractères

Objectifs : maîtriser le formalisme algorithmique en développant des algorithmes sur la machine-caractères.

7.1 Présentation

La machine est une boite qui renferme un ruban. Au cours de l'utilisation de la machine, le ruban défile devant une fenêtre. Le défilement se fait toujours dans un seul sens. Le ruban est composé d'une suite finie de cases comportant chacune un caractère. Le ruban se termine par une case spéciale contenant le caractère '.'. A tout instant, le seul caractère du ruban auquel la machine a accès est celui qui est présent dans la fenêtre. Nous baptisons ce caractère le caractère courant. L'obtention du caractère suivant se fait par un ordre de lecture.

7.2 Exemples

Sur cette machine, on peut développer de nombreux algorithmes tels que la détermination du nombre total de caractères de la machine, la recherche du mot le plus long, le nombre de mots de longueur donnée, etc.

A titre d’exemples donnons quelques uns :

Nombre de mots se terminant par ‘S’

    ALGORITHME S
    VAR
        Cs : ENTIER
        C : CAR
    DEBUT
        Cs := 0
        LIRE( C )
        TANTQUE C # '.'
            SI C = 'S'
                LIRE( C )
                SI C = ' ' OU C = '.'
                    Cs := Cs + 1
                FSI
            SINON
                LIRE(C )
            FSI
        FINTANTQUE
    FIN

Nombre de ‘LES’

    ALGORITHME LES
    VAR
        LES : ENTIER
        C : CAR
    DEBUT
        LES := 0
        LIRE( C )
        TANTQUE C # '.'
            SI C= 'L'
                LIRE( C )
                SI C = 'E'
                    LIRE ( C )
                    SI C = 'S'
                        LES := LES + 1
                        LIRE(C )
                    FSI
                FSI
            SINON
                LIRE( C )
            FSI
        FINTANTQUE
        ECRIRE(LES)
    FIN

Nombre de mots

ALGORITHME Nombre_de_mots
    VAR
        C, Cmot : ENTIER
        Mot : CAR
    DEBUT
        LIRE( C )
        Cmot := 0
        TANTQUE C # '.'
            TANTQUE C = ' ' ET C #'.'
                LIRE(C )
            FINTANTQUE
            Mot := ''
            TANTQUE C # ' ' ET C # '.'
                Mot := Mot + C
                LIRE(C)
            FINTANTQUE
            SI Mot # ''
                Cmot := Cmot + 1
                ECRIRE(Cmot)
            FSI
        FINTANTQUE

COURS 8 : Machine-nombres

Objectifs :maîtriser le formalisme algorithmique en développant des algorithmes sur la machine-nombres. Introduire à ce niveau la structure de contrôle ‘POUR’

8.1 Présentation

Par analogie à la machine-caractères, on peut définir la machine-nombres o� chaque ordre de lecture délivre le prochain nombre. On suppose que la première lecture délivre le nombre de nombres. On pourra alors développer les algorithmes suivants :

- recherche du maximum

- recherche d'un élément donné

- recherche le nombre de sous suites croissantes

- etc.

8.2 Structure de contrôle ‘POUR’

On utilise cette structure quand on connaît à l’avance le nombre d’itérations d’une boucle. La formulation algorithmique est la suivante :

    POUR Variable := Exp1, Exp2, Exp3
        Action 1
        Action 2
        ...
        Action n
    FINPOUR

Variable désigne une variable entière.

Exp désigne une expression. Exp1 est la valeur initiale de la variable, Exp2 la valeur finale et Exp3 l’incrément. Toute boucle ‘POUR’ peut se traduire en une boucle ‘TANTQUE’. Par contre, l’inverse n’est pas toujours possible.

Exemple1

POUR I := 1, 20, 4

Ecrire(I)

FINPOUR

Les valeurs imprimés sont 1, 4, 8, 12, 16 et 20.

Exemple 2

S := 0

POUR I := 40, 1, -1

S := S+ I

FINPOUR

C’est la somme des 40 premiers naturels.

Utilisation en PASCAL

En PASCAl, l’incrément est toujours égal à 1 ou –1.

Dans le cas o� l’incrément est +1 on utilise l’instruction ‘FOR’ comme suit

FOR Variable := Exp1 TO Exp2 DO Instruction

Dans le cas o� l’incrément est -1 on utilise l’instruction ‘FOR’ comme suit

FOR Variable := Exp1 DOWNTO Exp2 DO Instruction

Instruction désigne une instruction simple ou composée.

Exemple

L’exemple 2 se traduit en PASCAL comme suit :

S := 0 ;

FOR I :=40 DOWNTO 1 DO

S := S + I

8.3 Exemples d’algorithmes sur la machine-nombres

Recherche du maximum

   ALGORITHME Maximum
    VAR
        Max , Nombre, K, I : ENTIER
    DEBUT
        LIRE(K) { Nombre de Nombre }
        LIRE(Max)
        POUR I :=2, K
            LIRE(Nombre)
            SI Nombre > Max
                Max := Nombre
            FSI
        FINPOUR
        ECRIRE(Max)
    FIN

Premier nombre dont le carré est égal à la somme des deux précédents.

    ALGORITHME Premier_carre
    VAR
        Prec1, Prec2, Nombre, I, K : ENTIER
        Trouv : BOOLEEN
    DEBUT
        LIRE(K)
        LIRE(Prec1)
        LIRE(Prec2)
        I := 3
        Trouv := Faux
        TANTQUE I <= K ET NON Trouv
            LIRE(Nombre)
            SI Nombre*Nombre = Prec1 + Prec2
                Trouv := Vrai
            SINON
                Prec1 := Prec2
                Prec2 := Nombre
                I := I + 1
            FSI
        FINTANTQUE
        SI Trouv
            ECRIRE( Nombre)
        SINON
            ECRIRE('Néant')
        FSI
    FIN

Nombre de sous suites croissantes

   ALGORITHME Sous_Suite
    VAR
        N, Nombre, I, K, Prec: ENTIER
    DEBUT
        N := 1
        LIRE(K)
        LIRE(Nombre)
        POUR I :=2, K
            Prec := Nombre
            LIRE( Nombre)
            SI Nombre < Prec
                N := N + 1
            FSI
        FINPOUR
        ECRIRE(N)
    FIN

TRAVAUX DIRIGES

I. Machine-caractères

1. Longueur du ruban

2. Nombre de blancs.

3. Nombre d’occurrences de 'LE'.

4. Nombre d'occurrences de 'LES'.

5. Nombre de mots ( mot = suite de caractères ne contenant pas de blancs)

6. Nombre de mots se terminant par 'TION'

7. Nombre de mots contenant 'TION'.

8. Nombre de mots commençant par 'A' et se terminant par 'S'.

9. Le mot le plus long.

10. Les mots ne contenant pas de voyelles

11. Les mots contenant au moins trois voyelles

II. Machine-nombres

1. le plus grand élément.

2. Le plus petit élément

3. 1. et 2.

4. La somme des nombres impairs.

5. La somme des nombre pairs.

6. Recherche d'un élément donné.

7. La liste des termes compris entre a et b donnés

8. les multiples de a donné.

9. Les diviseurs de a donné.

10. La somme des nombres positifs.

11. Le nombre de sous suites croissantes.