Scribd Logo
Importer

Bienvenue sur Scribd !

  • 18 vues

    Devoir n2

    Transféré par

    Tanon lambert Kadjo

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Devoir n2

    Transféré par

    Tanon lambert Kadjo
    18 vues2 pages

    Titre original

    devoir n2

    Copyright

    © © All Rights Reserved

    Formats disponibles

    DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    18 vues2 pages

    Devoir n2

    Transféré par

    Tanon lambert Kadjo

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    sur 2

    Data Science Institute 2017-2018

    Module Python par Dr KADJO

    Informatique
    Devoir N°2
    Durée : 2H00

    « Ordinateurs, tablette et autres téléphones interdits, Documents non autorisés » »


    Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa
    copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

    Exercice 1 Complexité algorithmique


    1) Pour chacun des algorithmique suivant, indiquez la complexité au pire des cas de chaque étape
    de l’algorithme ainsi que la complexité de la fonction.

    def boucle(x): def nesting(n):


    x = x + 1 m = n
    i = 0 sum = 0
    while i < x: i = 0
    i = i + 1 while i < n:
    x = x * x j = 0
    return x while j < n:
    k = 0
    while k < m:
    def devine(a,b) : sum += 2
    if (a = = 0) : k += 1
    return b j += 1
    i += 1
    return devine(a-1,a*b) return sum

    2) Des programmes sont présentés ci-dessous. Dites ce que chacun fait et calculez sa complexité
    dans le meilleur des cas et dans le pire des cas.
    Les programmes b) et c) sont composés de deux fonctions.

    a) b)
    def majoritaire(L): def u(n):
    xmaj=L[0] u=1
    nmaj=nocc(xmaj,L) for i in range(n):
    for i in range(1,len(L)): u=1-2*u
    if nocc(L[i],L)>nmaj: return u
    xmaj=L[i] def liste_u(n): L=[]
    nmaj=nocc(L[i],L) for i in range(n+1):
    return xmaj L.append(u(i))
    return L
    c) d)
    def liste_u(n):
    def nocc(x,L):
    u=1
    n=0
    L=[u]
    for y in L:
    for i in range(n):
    if x==y:
    u=1-2*u
    n=n+1
    L.append(u)
    return L
    def u(n):
    L=liste_u(n)
    return L[-1]
    Exercice 2 Piles

    Soit une expression mathématique dont les éléments appartiennent à l’alphabet suivant :
    A ={0,1,2,… ,9, +, −, *, /,(,),[, ]}.

    1) Ecrivez un algorithme qui, à l’aide d’une unique pile d’entiers, vérifie la validité des
    parenthèses et des crochets contenus dans l’expression. L’algorithme retournera 0 si
    l’expression est correcte ou −1 si l’expression est incorrecte. On supposera que l’expression
    est donnée sous forme d’une chaîne de caractères
    2) Calculez la complexité de votre algorithme

    Exercice 3 Manipulons les bases de données

    Un technicien propose le schéma de gestion de la base de données d’une compagnie ferroviaire. Les
    relations portant sur la partie gérant les trains ont été présentées ici. La description des 3 relations
    est la suivante :

    TRAIN TRAJET TYPE


    immatriculation : entier num_trajet : entier id : entier
    gare_attache : texte #immatriculation : entier nom : texte
    #id : entier ville_dep : texte nb_place : entier
    ville_arr : texte
    heure_dep : date
    heure_arr : date

    Dans chaque relation, la clé primaire est soulignée. Pour les tables contenant une clé étrangère,
    celle-ci est préfixée par le caractère dièse (#).

    1) Donnez la suite de commandes necessaires à lma création de cette base de données


    GESTION_TRAIN en se limitant aux 3 relations.
    2) Ecrivez une requête SQL donnant comme résultat l’heure de départ, l’heure d’arrivée et
    l’identifiant de tous les trains au départ de la ville de KOMANDIMAN.
    3) Modifiez la requête de la question 2 afin d’afficher, en plus des informations demandées, la
    gare d’attache de tous les trains toujours au départ de la ville de KOMANDIMAN. Attention
    on ne veut pas de doublons.
    4) Ecrivez une requête SQL donnant comme résultat le nombre de trajets au départ de Gratos
    par type de train.
    5) Ecrivez une requête SQL donnant le nom et la gare de départ de tous les trains dont l’heure
    de départ est comprise entre 7h et 13h.

    Vous aimerez peut-être aussi