Examen

Devez-vous choisir ce module de remise à niveau ?

Les exercices ci-dessous nécessitent l’utilisation du langage de programmation Python et évaluent votre capacité à concevoir et analyser des algorithmes manipulant des structures de données. Vous devriez choisir ce module de remise à niveau :

• si vous n’avez jamais programmé en Python auparavant ;
• ou si vous avez besoin d’une IA pour résoudre ces exercices.

Exercice 1

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(list1, list2):
    result = 0
    i = 0
    while i < len(list1):
        value1 = list1[i]
        j = 0
        while j < len(list2):
            value2 = list2[j]
            if value1 == value2:
                result = result + value1
            j = j + 1
        i = i + 1
    return result
# default_end
# test_start
print(mystere([1, 2, 3], [5, 4, 3, 2]))
# test_end

# exercice: show
# default_start
def mystere(list1, list2):
    result = 0                        # result=0
    i = 0                             # i=0
    while i < len(list1):           # 0<3                                                     1<3                          ...
        value1 = list1[i]           # value1=1                                                value1=2
        j = 0                         # j=0
        while j < len(list2):       # 0<4         1<4         2<4         3<4         4<4     ...
            value2 = list2[j]       # value2=5    value2=4    value2=3    value2=2
            if value1 == value2:      # False       False       True        False
                result = result + 1   # result=0    result=0    result=0    result=0
            j = j + 1                 # j=1         j=2         j=3         j=4
        i = i + 1                     # i=1                                                     i=2                         
    return result                     # 2
# default_end

Quelle est la complexité en temps de la fonction mystere ci-dessus ? n étant la taille de la liste list1 et m est la taille de la liste list2.

• \(O(1)\) - Constante
• \(O(log(nm))\) - Logarithmique
• \(O(nm)\) - Bilinéaire
• \(O((nm)log(nm))\) - Log Linéaire
• \(O((nm)^2)\) - Quadratique
• \(O((nm)^3)\) - Cubique
• \(O(2^{nm})\) - Exponentielle
• \(O((nm)!)\) - Factorielle

# exercice: show
# default_start
def mystere(list1, list2):
    result = 0                        # 1 affectation
    i = 0                             # 1 affectation
    # len(list1) iterations
    while i < len(list1):           # 1 comparaison + 1 longueur
        value1 = list1[i]           # 1 affectation + 1 accès
        j = 0                         # 1 affectation
        # len(list2) iterations
        while j < len(list2):       # 1 comparaison + 1 longueur
            value2 = list2[j]       # 1 affectation + 1 accès
            if value1 == value2:      # 1 comparaison
                result = result + 1   # 1 affectation + 1 addition
            j = j + 1                 # 1 affectation + 1 addition
        i = i + 1                     # 1 affectation + 1 addition
    return result                     # 1 affectation
# n = len(list1)
# m = len(list2)
# T(n, m) = 1 + 1 + n * (2 + 2 + 1 + m * (2 + 2 + 1 + 2 + 2) + 2) + 1
# T(n, m) = 2 + n * (7 + m * 9 + 2) + 1
# T(n, m) = 3 + 7n + 2n + 9nm
# T(n, m) = 9nm + 9n + 3
# T(n, m) => O(nm)
# default_end

Exercice 2

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(pairs):
    result = {}
    i = 0
    keys = pairs.keys()
    total = 0
    while i < len(keys):
        key = keys[i]
        value = pairs[key]
        total = total + value
        i = i + 1
    i = 0
    while i < len(keys):
        key = keys[i]
        value = pairs[key]
        result[key] = total - value
        i = i + 1
    return result
# default_end
# test_start
print(mystere({"a": 1, "b": 2, "c": 3}))
# test_end

# exercice: show
# default_start
def mystere(pairs):
    result = {}                       # result={}
    i = 0                             # i=0
    keys = pairs.keys()               # keys=["a", "b", "c"]
    total = 0                         # total=0
    while i < len(keys):              # 0<3         1<3         2<3         3<3
        key = keys[i]                 # key="a"     key="b"     key="c"
        value = pairs[key]            # value=1     value=2     value=3
        total = total + value         # total=1     total=3     total=6
        i = i + 1                     # i=1         i=2         i=3
    i = 0                             # i=0
    while i < len(keys):              # 0<3             1<3                     2<3                         3<3
        key = keys[i]                 # key="a"         key="b"                 key="c"
        value = pairs[key]            # value=1         value=2                 value=3
        result[key] = total - value   # result={"a":5}  result={"a":5, "b":4}   result={"a":5, "b":4, "c":3}
        i = i + 1                     # i=1     i=2     i=3
    return result                     # {"a":5, "b":4, "c":3}
print(mystere({"a": 1, "b": 2, "c": 3}))
# default_end

Quelle est la complexité en temps de la fonction mystere ci-dessus ? n étant la taille du dictionnaire pairs (i.e., le nombre de paires clé-valeur dans pairs).

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# exercice: show
# default_start
def mystere(pairs):
    result = {}                       # 1 affectation + O(1) création d'un dictionnaire vide
    i = 0                             # 1 affectation
    keys = pairs.keys()               # 1 affectation + O(len(pairs)) pour construire la liste des clés
    total = 0                         # 1 affectation
    # len(keys) iterations
    while i < len(keys):              # 1 comparaison + 1 longueur
        key = keys[i]                 # 1 affectation + 1 accès
        value = pairs[key]            # 1 affectation + 1 accès
        total = total + value         # 1 affectation + 1 addition
        i = i + 1                     # 1 affectation + 1 addition
    i = 0                             # 1 affectation
    # len(keys) iterations
    while i < len(keys):              # 1 comparaison + 1 longueur
        key = keys[i]                 # 1 affectation + 1 accès
        value = pairs[key]            # 1 affectation + 1 accès
        result[key] = total - value   # 1 accès + 1 affectation + 1 soustraction 
        i = i + 1                     # 1 affectation + 1 addition
    return result                     # 1 affectation
# n = len(pairs)
# T(n) = 2 + 1 + 1 + n + 1 + n * (2 + 2 + 2 + 2 + 2 + 1) + 1 + n * (2 + 2 + 2 + 3 + 2) + 1
# T(n) = 5 + n + 1 + 11n + 1 + 11n + 1
# T(n) = 23n + 8
# T(n) => O(n)
# default_end

Exercice 3

Écrire une fonction \(sort(values)\) qui prend en paramètre une liste d’entiers \(values\) et retourne un dictionnaire contenant les clés ascending et descending associées respectivement à la liste des valeurs de la liste \(values\) ordonnées par ordre croissant et décroissant.

Exemple d’utilisation :

• \(sort([8, 14, 7])\) retourne \(\{\q{ascending}: [7, 8, 14], \q{descending}: [14, 8, 7]\}\)
• \(sort([ 0, 2, 47, 5, -5])\) retourne \(\{\q{ascending}: [-5, 0, 2, 5, 47], \q{descending}: [47, 5, 2, 0, -5]\}\)
• \(sort([5, 4, 3, 2, 1])\) retourne \(\{\q{ascending}: [1, 2, 3, 4, 5], \q{descending}: [5, 4, 3, 2, 1]\}\)

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, dir, eval, sorted, reversed
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: sort, reverse
# forbidden_dict_methods: 
# default_start
def sort(values):
    return None
# default_end
# test_start
print(sort([8, 14, 7]))
print("C683AKRMaR")
print(sort([0, 2, 47, 5, -5]))
print("C683AKRMaR")
print(sort([5, 4, 3, 2, 1]))
# test_end
# solution_start
# SELECTION SORT -> worst: O(n²), best: O(n²) [Algorithme lent]
def selectionSort(values):
  n = len(values)
  i = 0
  while i < n - 1:
    min_i = i
    j = i
    while j < n:
      if values[j] < values[min_i]:
        min_i = j
      j = j + 1
    if min_i != i:
      tmp = values[min_i]
      values[min_i] = values[i]
      values[i] = tmp
    i = i + 1
  return values

# BUBBLE SORT -> worst: O(n²), best: O(n) [Algorithme moyennement rapide]
def bubbleSort(values):
  i = 0
  while i < len(values):
    j = 0
    while j < len(values) - i - 1:
      if values[j] > values[j + 1]:
        tmp = values[j]
        values[j] = values[j + 1]
        values[j + 1] = tmp
      j = j + 1
    i = i + 1
  return values

# INSERTION SORT -> worst: O(n²), best: O(n) [Algorithme moyennement rapide]
def insertionSort(values):
  i = 1
  while i < len(values):
    key = values[i]
    j = i - 1
    while j >= 0 and key < values[j]:
      values[j + 1] = values[j]
      j = j - 1
    values[j + 1] = key
    i = i + 1
  return values

# MERGE SORT -> worst: O(nlogn), best: O(nlogn) [Algorithme rapide]
def slicing(values, start, end):
    new_size = end - start
    new_arr = [0] * new_size
    i = 0
    while i < new_size:
        new_arr[i] = values[start + i]
        i = i + 1
    return new_arr
    
def concatenate(list1, list2):
    new_size = len(list1) + len(list2)
    new_arr = [0] * new_size
    i = 0
    while i < len(list1):
        new_arr[i] = list1[i]
        i = i + 1
    i = 0
    while i < len(list2):
        new_arr[len(list1) + i] = list2[i]
        i = i + 1
    return new_arr

def merge(list1, list2):
    new_size = len(list1) + len(list2)
    new_arr = [0] * new_size
    i = 0
    j = 0
    k = 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            new_arr[k] = list1[i]
            i = i + 1
            k = k + 1
        else:
            new_arr[k] = list2[j]
            j = j + 1
            k = k + 1
    new_arr = slicing(new_arr, 0, k)
    new_arr = concatenate(new_arr, slicing(list1, i, len(list1)))
    new_arr = concatenate(new_arr, slicing(list2, j, len(list2)))
    return new_arr
    
def mergeSort(values):
    ans = values
    if len(values) > 1:
        mid_size = len(values)//2
        left_arr = slicing(values, 0, mid_size)
        right_arr = slicing(values, mid_size, len(values))
        ans = merge(mergeSort(left_arr), mergeSort(right_arr))
    return ans

def reverse(values):
    new_arr = [0] * len(values)
    i = 0
    while i < len(values):
        new_arr[i] = values[len(values) - 1 - i]
        i = i + 1
    return new_arr

def sort(values):
    sorted_values = mergeSort(values)
    results = {}
    results["ascending"] = sorted_values
    results["descending"] = reverse(sorted_values)
    return results
# solution_end

# default_start
print("Hello World!")

# default_end