L2SI / I31 - Examen de TP d'algorithmique

Vendredi 17 novembre 2017: 13:15(-0:15) → 15:15(+0:15)

CONSIGNES.

TOUS DOCUMENTS INTERDITS. Vous avez 1/4 d'heure au début de l'examen pour lire en détail les consignes ci-dessous avant de commencer les exercices, et un deuxième 1/4 d'heure en fin d'examen pour le finaliser.

Lisez attentivement les énoncés et suivez scrupuleusement les instructions en respectant à la lettre les commandes, les noms des fichiers proposés, majuscules/minuscules comprises.

L'expérience prouve que certains étudiants ne savent pas lire un énoncé et/ou recopier une simple commande. Vous devriez donc les copier avec la souris afin d'éviter, entre autres, de confondre la quote ' et l'antiquote `.

NB. Pour les étudiants de la filière SI : si vous n'avez pas suivi ces consignes et que je dois intervenir pour faire ce travail à votre place (10% des étudiants de la promotion 2016-2017), je retirerai 5 points à votre note.


SUJET.

Le barème indiqué sur les exercices est approximatif. Les réponses aux questions posées doivent être incorporées aux fichiers sources Python sous forme de commentaires en début de programme.

IMPORTANT : Expliquez en français sous forme de commentaires les algorithmes que vous utilisez pour écrire vos fonctions !

[+4] On désigne par A et B deux listes d'entiers naturels triées. Écrivez une fonction Fusionner(A,B) qui renvoie la liste triée contenant tous les termes des deux listes. Vous ne devez pas utiliser d'algorithme de tri pour trier la concaténation des deux listes A+B mais balayer les termes des deux listes pour construire la liste résultat.

Exemple : si A=[1,1,3,5] et B=[2,4,7], la liste renvoyée est la liste [1,1,2,3,4,5,7].

Quelle est la complexité de votre algorithme en fonction des longueurs n et m des deux listes ?

# L'algorithme consiste à ranger min(A[i],B[j]) dans une liste
# auxiliaire en incrémentant l'indice de la liste qui a fourni ce minimum.
# Une fois l'extrémité d'une des deux listes atteinte, on complète
# la liste auxiliaire avec le relicat de l'autre liste. 
# La complexité est en O(n+m) où n = |L1| et m = |L2|
# chaque liste est en effet parcourue une seule fois
def fusion(A,B):
    i = j = 0
    LF = []
    while (i < len(A)) and (j < len(B)):
        if A[i] < B[j]:
            LF = LF + [A[i]]
            i = i + 1
        else:
            LF = LF + [B[j]]
            j = j + 1
    if (i < len(A)):
        LF = LF + A[i:]
    else:
        LF = LF + B[j:]
    return LF

A = [int(x) for x in input("Liste A: ").split()]
B = [int(x) for x in input("Liste B: ").split()]
print(fusion(A,B))
[+6] On désigne par a et b chaînes de caractères. Écrivez une fonction Trouver(a,b) qui renvoie la liste des positions de la chaîne a dans la chaîne b si a est une sous-chaîne de b et la liste vide sinon. Vous ne devez pas utiliser les opérateurs Python match, find ou in.

Par exemple si a="GA" et b="GARGANTUA", la liste renvoyée est la liste [0,3].

Quelle est/sont la/les complexité(s) de votre algorithme en fonction des longueurs n et m des deux chaînes ?

# L'algorithme consiste à parcourir b (avec l'indice i) tant qu'il 
# est encore possible d'y trouver le motif a. On avance dans ce parcours 
# soit d'une position si le motif a ne coïncide pas ou que partiellement 
# avec b, soit de la longueur du motif s'il coïncide avec b à partir de
# la position i.
# Le nombre de symboles qui coïncident est stocké dans la variable "egaux".
# Si le nombre de symboles qui coïncident égale la longueur du motif a
# c'est que l'on a trouvé a dans b, on range alors la position i
# dans notre liste de positions. 
# Dans le meilleur des cas, a n'est pas présent dans b et son premier
# caractere est différent de tous les caractères dans b
# une seule comparaison est nécessaire jusqu'au dernier symbole de b
# qu'il est possible de comparer soit T-n,m) = O(m-n) si
# n = |a| et m = |b|
# Dans le pire des cas, la chaîne a diffère uniquement sur le
# dernier symbole et en chaque position de b (exemple a="AAB" et
# b = "AAAAAAAAAAAAAAAAAAA"). Dans ce cas tous les symboles de a et
# b sont comparés, donc T(n,m)=O(n*m)
import sys
def trouver(a,b):
    POS = []
    i = 0
    while (i <= len(b)-len(a)):
        egaux = 0
        while (egaux < len(a)) and (a[egaux] ==  b[i + egaux]):
            # on reconnaît un symbole de plus de a dans b            
            egaux = egaux + 1
        if egaux == len(a):
            # On a trouve a en b[i], on range i et on avance de |a|
            POS = POS + [i]
            i = i + len(a)
        else:
            # On n'a pas trouvé a, on avance d'une position dans b
            i = i + 1
    return POS

if len(sys.argv) < 3:
    print(sys.argv[0]," a b")
else:
    print(trouver(sys.argv[1],sys.argv[2]))
[+6] Écrivez une fonction S2B(N,t) qui renvoie la représentation binaire sur t bits de l'entier N sous forme de chaîne de caractères (bit de poids fort à gauche). Ainsi S2B(5,8) renvoie la chaîne "00000101".

On désigne par L une liste d'entiers. Écrivez une fonction Python Blocs(L,t) qui renvoie une liste d'entiers contenant alternativement les longueurs des séquences de 0 et de 1 qui constituent la concaténation des écritures binaires sur t bits des entiers de la liste L.

Par exemple, si L=[3,0,8,2], la concaténation des écritures binaires des entiers sur 8 bits de cette liste est "00000011"+"00000000"+"00001000"+"00000010" et la fonction Blocs doit renvoyer la liste [6,2,12,1,9,1,1].

Quelle est la liste renvoyée par l'appel Blocs(Blocs(Blocs([0],8),8),8) ?

# On récupère la représentation binaire de N. On enlève
# le "0b" en début de chaîne et on complète à gauche par
# le nombre de "0" manquants.
def S2B(N,t):
    bits = bin(N)[2:]
    bits = "0"*(t - len(bits)) + bits
    return bits

# La chaîne de caractères "convoi" contient la concaténation
# des différents blocs binaires.
# La variable rl contient la longueur courante de la séquence
# de bits identiques.
def Blocs(L,t):
    convoi = ""
    i = 0
    while (i < len(L)):
        # On concatène à convoi chaque séquence binaire	   
        convoi = convoi + S2B(L[i],t)
        i = i + 1
	rl = 1
    # On récupère le premier bit de la séquence globale	       
    bit = convoi[0]
    B = []
    i = 1
    while (i  < len(convoi)):			    
	if (convoi[i] == bit):
	    # Le i-ème bit a toujours la même valeur 	
            rl = rl + 1
	else:
	    # Le i-ème bit a changé, on rajoute rl à la liste B,
	    B = B + [rl]
	    # on change la valeur du bit courant 0->1 ou 1->0	
            bit = str(1 - int(bit))
	    # et on met à jour la longueur de la future séquence
            rl = 1
        i = i + 1
    return B + [rl]

# Cet appel affiche [5, 1, 9, 1, 6, 2] :
# NB. Il manquait les crochets autour de 0 dans le sujet. Certains 
# étudiants avaient corrigé, d'autres non, dans tous les cas les 
# points étaient donnés si la réponse était cohérente. 
print(Blocs(Blocs(Blocs([0],8),8),8))
[+4] En incluant la librairie random (rajouter from random import * dans votre script), l'appel de la fonction random() (sans paramètre) renvoie un nombre flottant de l'intervalle [0,1[.

Écrivez une fonction DansUnite(x,y) qui renvoie True si le point de coordonnées (x, y) du plan réel est dans la boule unité, autrement dit si sa distance au point de coordonnées (0,0) est strictement inférieure à 1, et False sinon.

Écrivez une fonction Flechette() (sans paramètre) qui renvoie un couple de points (x, y) dans le quart positif du carré unité, i.e. tel que 0 ≤ x < 1 et 0 ≤ y < 1.

Écrivez une fonction Cribler(n) qui génère n couples (x, y) au hasard dans le quart positif du carré unité et qui renvoie le nombre de ces couples qui appartiennent au cercle unité.

Écrivez un script qui demande de saisir la valeur entière n et qui renvoie la valeur (4 * Cribler(n)) / n. Que calcule ce script ?

# Il s'agit d'une estimation du nombre Pi. En effet, on tire dans le
# carré [0,1] x [0,1] et toutes les fléchettes n'iront pas dans le
# le quart de disque inscrit dans ce carré, la surface du carré étant 1 et 
# celle du 1/4 de disque pi/4, la proportion de fléchettes dans le disque
# doit être proche du ratio entre ces deux surfaces soit pi/4.   
import sys
from random import *

def DansUnite(x,y):
    return (x*x + y*y) < 1.0

def Flechette():
    return random(), random()

def Cribler(n):
    NbDansDisque = 0
    i = 0
    while i < n:
        if DansUnite(*Flechette()):
            NbDansDisque = NbDansDisque + 1
        i = i + 1
    return NbDansDisque

seed()

if len(sys.argv) < 2:
    print("Syntaxe: ",sys.argv[0],"nbtirs")
else:
    NbTirs = int(sys.argv[1])
    print(4*Cribler(NbTirs)/NbTirs)