Révisions Algorithmique et réseaux¶

1ère partie : Complexité

Répondez aux questions ci-dessous¶

Le coût en temps d’un algorithme de recherche est : 1. Constant 2. Logarithmique 3. Linéaire 4. QuadratiqueLinéaireLe coût en temps d’un algorithme de recherche de maximum est : 1. Constant 2. Logarithmique 3. Linéaire 4. QuadratiqueLinéaireLe coût en temps d’un algorithme de recherche par dichotomie est : 1. Constant 2. Logarithmique 3. Linéaire 4. Quadratique

In [ ]:

Logarithmique

Logarithmique

On mesure le temps sur un algorithme de coût linéaire qui s’exécute sur une liste de 1 000 éléments. Quel temps mettra-t-il sur une liste de 5 000 éléments ? Justifier la réponse. 1. Il mettra le même temps 2. Il mettra environ 5 fois moins de temps 3. Il mettra environ 5 fois plus de temps 4. Il mettra 25 fois plus de tempsIl mettra environ 5 fois plus de tempsOn mesure le temps sur un algorithme de coût quadratique qui s’exécute sur une liste de 1 000 éléments. Quel temps mettra-t-il sur une liste de 5 000 éléments ? Justifier la réponse. 1. Il mettra le même temps 2. Il mettra environ 5 fois moins de temps 3. Il mettra environ 5 fois plus de temps 4. Il mettra 25 fois plus de tempsIl mettra 25 fois plus de tempsOn mesure le temps sur un algorithme de coût constant qui s’exécute sur une liste de 1 000 éléments. Quel temps mettra-t-il sur une liste de 5 000 éléments ? 1. Il mettra le même temps 2. Il mettra environ 5 fois moins de temps 3. Il mettra environ 5 fois plus de temps 4. Il mettra 25 fois plus de tempsIl mettra le même tempsClasser ces coûts d’exécution en temps du plus rapide au plus lent : 1. Linéaire 2. Logarithmique 3. Polynomial 4. Constant 5. Quadratique4 > 2 > 1 > 5 > 3

1. Indiquez les complexités de référence qui sont du même ordre de grandeur que l'expression mathématique indiquée

Exemple : 3 $n^{2}$ + 5n - 2 = O($n^{2}$) – complexité quadratique.

1. $\frac{1}{3}n^{2} + 5n^{3} +2$
2. $\frac{1}{3}n^{2} + \frac{1}{3}n^{4} +2$
3. $2 + 3n log_{2}(n)$
4. $nlog_{2}(n) + 2^{n} + 7n^{3}$
5. $n! + 8n + 9n^{2}$

1. $O(n^3)$
2. $O(n^4)$
3. $O(log(n))$
4. $O(2^n)$
5. $(O(n!))$

2. On décide d'effectuer une recherche d'une valeur dans un tableau trié contenant 42000 valeurs.
On procède par dichotomie. Indiquer le nombre maximal d'itérations de l'algorithme pour une telle recherche.

In [2]:

valeur = 42000
compteur = 0
while valeur > 1:
    valeur = valeur/2
    compteur +=1
print(compteur)

valeur = 42000 compteur = 0 while valeur > 1: valeur = valeur/2 compteur +=1 print(compteur)

16

Exercice 1

Considérer les algorithmes suivants avec un temps d’exécution T(n) pour une longueur de données n.
Déterminer leurs complexités asymptotiques respectives.

Algorithme A1 :  T(n) = 3n + 2
Algorithme A2 :  T(n) = 6
Algorithme A3 :  T(n) = 4n**2 + n + 2

Algorithme A4
Exécuter A1;
Exécuter A2;
Exécuter A3;

Algorithme A5
i = 1
TANT QUE i <= n FAIRE
Exécuter A3;
i = i + 1
FIN TANT QUE
Exécuter A1;

Algorithme A6
i = 1
TANT QUE i <= 5 FAIRE
Exécuter A1;
i = i + 1
FIN TANT QUE

A4 : il faut trouver l'algorithme qui a la complexité la plus importante soit A3 : O(n**2) A5 : on exécute n fois A3 de complexité n**2, soit une complexité de O(n**3) A1 est négligeable ici A6 : on exécute 5 fois A1 de complexité n, la complexité reste O(n)

Exercice 2

Considérer les deux algorithmes A1 et A2 avec leurs temps d’exécution respectifs T1(n) = $9n^2$ et T2(n) = $100n + 96$ .

1. Déterminer la complexité asymptotique des deux algorithmes dans la notation Grand-O. Quel algorithme à la meilleure complexité asymptotique?

2. Calculer les temps maximales d’exécution des deux algorithmes Ti(n) pour n = 1, n = 3, n = 5, n = 10, n = 14.

3. Exécuter le code ci-dessous, il permet de tracer les graphes des deux fonctions Ti dans un même système de coordonnée (abscisse n, ordonnée Ti(n)).
   Pour quelles longueur de données n, quel algorithme est le plus efficace ? Justifier votre réponse graphiquement et mathématiquement.

In [3]:

import numpy as np
import matplotlib.pyplot as plt
x = np.linspace(0, 20, 500)
y1 = 9*x**2
y2 = 100*x + 96
plt.plot(x, y1, label = "T1")
plt.plot(x, y2, label = "T2")
plt.legend()

plt.show()

import numpy as np import matplotlib.pyplot as plt x = np.linspace(0, 20, 500) y1 = 9*x**2 y2 = 100*x + 96 plt.plot(x, y1, label = "T1") plt.plot(x, y2, label = "T2") plt.legend() plt.show()

1. A1 est en O(n**2) et A2 est en O(n) donc A2 a une meilleure complexité. 2. pour n=1 : T1=9 et T2 = 196 pour n=3 : T1=81 et T2=396 pour n=5 : T1=225 et T2=596 pour n=10 : T1=900 et T2=1096 pour n=14 : T1=1764 et T2=1496 3. On voit que les deux courbes de mesure de temps se croisent pour n=12 donc avant l'intersection T1 est plus efficace mais après c'est T2 Calculons l'intersection on a : 9n**2 = 100n + 96 soit 9n**2 -100n - 96 = 0 le delta est donc de (-100)**2 -4*9*(-96) = 13456 > 0, on a donc 2 points d'intersection : 1er point -(-100) -sqrt(delta) / 2*9 = -0.88 2ème point -(-100) + sqrt(delta) / 2*8 = 12 pour n= 12 cequi confirme le résultat graphique

Exercice 3

Dans cet exercice, vous allez vous même élaborer un algorithme de tri !

1. Initialiser une liste avec 10 valeurs aléatoires entre 1 et 10.
2. Ecrire un algorithme qui identifie l’index de l’élément possédant la plus petite valeur dans la liste, et stocker le dans la variable pluspetitindex.
3. Echangez les deux éléments de la liste : le premier élément liste[0] et l’élément à la position pluspetitindex.
4. Tester votre algorithme
5. Imbriquez votre algorithme dans une boucle pour que vous triez toute la liste par ordre croissant !
6. Chronométrer de nouveau le temps d’exécution pour une saisie de valeur pour n=10, n=100, n=1000, n=5000.
7. Quelle est la complexité de cet algorithme ? Justifiez-la avec les valeurs de temps d'exécution mesurées.

In [4]:

from random import randint,shuffle
from time import perf_counter
import numpy as np
import matplotlib.pyplot as plt


# votre code ci-dessous
## echange de la plus petite valeur avec le 1er élément de la liste
liste = [randint(1,10) for _ in range(10)]
print (liste)

n=len(liste)

pluspetitindex = 0
pluspetitevaleur = liste[0]
i = 0
while i < n :
    if liste[i] <= pluspetitevaleur:
        pluspetitindex = i
        pluspetitevaleur = liste[i]
    i = i + 1
    
liste[0],liste[pluspetitindex]=liste[pluspetitindex],liste[0]

print (liste)

### tri de la liste dans l'ordre croissant
liste = [randint(1,10) for _ in range(10)]
k=0
n=len(liste)
while k < n:
    pluspetitindex = k
    pluspetitevaleur = liste[k]
    i = k
    while i < n :
        if liste[i] <= pluspetitevaleur:
            pluspetitindex = i
            pluspetitevaleur = liste[i]
        i = i + 1
    
    liste[k],liste[pluspetitindex]=liste[pluspetitindex],liste[k]
    k += 1

print(liste)

## mesure des temps d'éxécution question 6
# on place dans une fonction l'algo précédent
def tri(liste):
    k=0
    n=len(liste)
    while k<n:
        pluspetitindex = k
        pluspetitevaleur = liste[k]
        i = k
        while i < n :
            if liste[i] <= pluspetitevaleur:
                pluspetitindex = i
                pluspetitevaleur = liste[i]
            i = i + 1
    
        liste[k],liste[pluspetitindex]=liste[pluspetitindex],liste[k]
        k+=1
    return liste


tableauValeurs=[]
mesure=[10,100,1000,5000, 10000]
for n in mesure:
    liste = [randint(1,10) for _ in range(n)]
    debut=perf_counter()
    tri(liste)
    fin=perf_counter()
    temps=fin-debut
    tableauValeurs.append(temps)

print(tableauValeurs)
print()

plt.plot(mesure, tableauValeurs)
plt.show()

# 7. complexité en O(n**2)

from random import randint,shuffle from time import perf_counter import numpy as np import matplotlib.pyplot as plt # votre code ci-dessous ## echange de la plus petite valeur avec le 1er élément de la liste liste = [randint(1,10) for _ in range(10)] print (liste) n=len(liste) pluspetitindex = 0 pluspetitevaleur = liste[0] i = 0 while i < n : if liste[i] <= pluspetitevaleur: pluspetitindex = i pluspetitevaleur = liste[i] i = i + 1 liste[0],liste[pluspetitindex]=liste[pluspetitindex],liste[0] print (liste) ### tri de la liste dans l'ordre croissant liste = [randint(1,10) for _ in range(10)] k=0 n=len(liste) while k < n: pluspetitindex = k pluspetitevaleur = liste[k] i = k while i < n : if liste[i] <= pluspetitevaleur: pluspetitindex = i pluspetitevaleur = liste[i] i = i + 1 liste[k],liste[pluspetitindex]=liste[pluspetitindex],liste[k] k += 1 print(liste) ## mesure des temps d'éxécution question 6 # on place dans une fonction l'algo précédent def tri(liste): k=0 n=len(liste) while k

[7, 2, 6, 7, 3, 10, 5, 3, 7, 5]
[2, 7, 6, 7, 3, 10, 5, 3, 7, 5]
[4, 4, 4, 4, 5, 7, 7, 9, 10, 10]
[1.3600000016822378e-05, 0.0004639999999938027, 0.05185009999999579, 1.1816279999999892, 4.451445400000011]

2ème partie : Algorithmes à connaitre

Algorithme de recherche dichotomique¶

Soit l'algorithme de recherche dichotomique suivant :

1. Déroulez cet algorithme à la main en utilisant le tableau t=[1,3,4,6,7,8,10,13,14], on cherche l'élément 4

2. Codez cet algorithme en python
   Vous pouvez utiliser la fonction sort() de python pour générer un tableau trié de n éléments tous différents.
   Ajouter un compteur pour comptabiliser le nombre de fois que le tableau est coupé en deux.
   Quel est le pire cas ?
   Comptabilisez le nombre de fois que le tableau est coupé en deux pour le pire cas.
   Essayez avec des tableaux de plus en plus grands. Que constatez-vous ?

3. Ecrivez un algorithme de recherche simple qui parcourt le tableau et s’arrête lorsqu’il a trouvé la bonne valeur. Comparez ces deux algorithmes de recherche lorsque vous doublez la taille du tableau. (mesurer les temps d’exécution)

Votre réponse à la question 1

In [5]:

# votre code pour les questions 2 et 3
## recherche dichotomique
def rechercheSimple(t,val):
    trouve=False
    i=0
    while i<len(t) and trouve==False:
        if t[i]==val:
            trouve=True
        i=i+1

    return trouve,i


#print(rechercheSimple([3,8,6,12],3))


def rechercheDichotomique(t,val):
    deb=0
    fin=len(t)-1
    trouve=False
    compteur=0
    while trouve!=True and deb<=fin:
        compteur=compteur+1
        mil=(deb+fin)//2
        if t[mil]==val:
            trouve=True
        elif val>t[mil]:
            deb=mil+1
        else:
            fin=mil-1

    return trouve,compteur

#création d'un tableau contenant 10000 valeurs aléatoires différentes puis triées
# si on double la taille 20000 regardez ce qu'il se passe.
tableau=[randint(1,10000) for _ in range(10000)]
    
tableau.sort()

#print(tableau)
debut=perf_counter()
print(rechercheSimple(tableau,500))
fin=perf_counter()
print(fin-debut)

debut=perf_counter()
print(rechercheDichotomique(tableau,500))
fin=perf_counter()
print(fin-debut)

# votre code pour les questions 2 et 3 ## recherche dichotomique def rechercheSimple(t,val): trouve=False i=0 while it[mil]: deb=mil+1 else: fin=mil-1 return trouve,compteur #création d'un tableau contenant 10000 valeurs aléatoires différentes puis triées # si on double la taille 20000 regardez ce qu'il se passe. tableau=[randint(1,10000) for _ in range(10000)] tableau.sort() #print(tableau) debut=perf_counter() print(rechercheSimple(tableau,500)) fin=perf_counter() print(fin-debut) debut=perf_counter() print(rechercheDichotomique(tableau,500)) fin=perf_counter() print(fin-debut)

(True, 504)
0.0004281999999875552
(True, 12)
7.429999999430947e-05

Algorithme glouton¶

Définition d'un algorithme utilisant une stratégie gloutonne : faire à chaque étape un choix localement optimal dans le but d'obtenir à la fin un résultat globalement optimal.

Supposons que vous deviez rendre la monnaie à quelqu'un. Vous disposez de l'ensemble des pièces et billets existants dans la zone euro et en quantité infini . Vous choisissez une stratégie gloutonne : des choix locaux optimaux, étape après étape, devraient produire un résultat global optimal.

A partir de la méthode gloutonne décrite ci-dessus, écrivez l'algorithme correspondant en python.

In [6]:

# votre code ci-dessous
def RenduMonnaie(s):
    valeur=[10000,5000,2000,1000,500,200,100,50,20,10,5,2,1]
    
    resultat=[]
    s=s*100 # on multiplie par 100 pour avoir la valeur en cent euro
    
    for val in valeur:
        if val<=s: #quand on trouve une valeur < au chiffre
            n=s//val # calcul le nombre de pièce ou billet de la valeur correspondante
            s=s-(val*n) # calcul la somme restante
            if val>=100: # pour afficher valeur >100 en euro et pas en cents
                val=val/100
            resultat.append([n,val]) # place le résultat dans resultat
    
    compteur=0
    for i in range(0,len(resultat)):
        compteur=compteur+resultat[i][0]
    
    return compteur,resultat
    
    
    
somme=float(input("indiquer la somme à rendre en euros : "))

print(RenduMonnaie(somme))

# votre code ci-dessous def RenduMonnaie(s): valeur=[10000,5000,2000,1000,500,200,100,50,20,10,5,2,1] resultat=[] s=s*100 # on multiplie par 100 pour avoir la valeur en cent euro for val in valeur: if val<=s: #quand on trouve une valeur < au chiffre n=s//val # calcul le nombre de pièce ou billet de la valeur correspondante s=s-(val*n) # calcul la somme restante if val>=100: # pour afficher valeur >100 en euro et pas en cents val=val/100 resultat.append([n,val]) # place le résultat dans resultat compteur=0 for i in range(0,len(resultat)): compteur=compteur+resultat[i][0] return compteur,resultat somme=float(input("indiquer la somme à rendre en euros : ")) print(RenduMonnaie(somme))

indiquer la somme à rendre en euros : 253
(5.0, [[2.0, 100.0], [1.0, 50.0], [1.0, 2.0], [1.0, 1.0]])

3ème partie : Réseaux

Révision de base structure des adresses IP.

Les adresses IP sont de la forme : "a.b.c.d", avec a, b, c et d compris entre 0 et 255 (a, b, c et d sont codés sur 1 octet).
Exemple d'adresse IP: 192.168.0.1

• Réseau de classe A : adresse réseau : a.0.0.0 (avec a qui doit être compris entre 1 et 126)
• Réseau de classe B : adresse réseau : a.b.0.0 (avec a qui doit être compris entre 128 et 191)
• Réseau de classe C : adresse réseau : a.b.c.0 (avec a qui doit être compris entre 192 et 223)

Une partie de l’adresse IP permet d’identifier le réseau auquel appartient la machine et l’autre partie de l’adresse IP permet d’identifier la machine sur ce réseau.
Pour différencier la partie de l’adresse IP qui représente le réseau de celle qui représente la machine, il faut utiliser un masque de sous réseau
Ce masque consiste en une adresse dont la représentation binaire est de la forme : 1……1 0…….0, c'est-à-dire une suite de 1 suivi d'une suite de 0.
Par exemple un masque valide est 255.255.248.0

binaire    1111 1111 .  1111 1111 . 1111 1000 . 0000 0000
décimal       255    .     255    .    248    .     0

Ce masque permet de "découper" une adresse IP en deux parties. La partie "réseau" (ici les 21 bits de poids forts à 1) et la partie "machine" (les 11 bits de poids faibles à 0).
Ce masque permet donc d'avoir, sur le même réseau, $2^{11}$ adresses distinctes.

Exemple :

  192.168.129.10 
& 255.255.248. 0
  ---------------
  192.168.128. 0

Retenons que faire le "et" bit à bit produit les résultats suivants : 1 & 1 = 1 ; 1 & 0 = 0 de même que 0 & 1 = 0

L’adresse réseau est donc 192.168.128.0
On peut placer dans ce réseau $2^{11}$ machines depuis l’adresse 192.168.128.0 à 192.168.135.255.

En effet, on peut aller jusqu’à 255 pour le dernier octet (que des 0 dans le masque soit 1111 1111 = 255), dans l’octet précédent, il y a 3 zéros de disponibles soit 111 = 7, donc on peut aller jusqu’à 135 (128+7).

Attention la 1ère adresse est l’adresse du réseau, ce n’est donc pas une adresse machine, la 1ère adresse est donc 192.168.128.1. La dernière adresse est l’adresse de broadcast, elle ne peut pas être attribuée à une machine, la dernière adresse machine est donc 192.168.135.254.

Exercice

Soit l’adresse IP 192.168.10.0 qui utilise le masque de sous-réseau suivant : 255.255.240.0.
Vous devez justifier l’ensemble de vos réponses.

1. Quelle est l’adresse du réseau ?
2. Indiquez la 1ère adresse et la dernière adresse possibles pour une machine dans ce réseau.
3. Combien de machines hôtes peut-on placer dans ce réseau ?
4. Quel est le type de ce réseau ?

Vos réponses ci-dessous 1. Soit l’adresse IP 192.168.10.0 qui utilise le masque de sous-réseau suivant : 255.255.240.0. Pour avoir l’adresse du réseau, il suffit d’additionner bit à bit en utilisant l’opérateur & l’adresse IP et le masque de sous-réseau. On sait que l’utilisation de 255 (soit 1111 1111) ne change pas la valeur additionnée, ainsi 192 & 255 = 192, donc la seule difficulté est de réaliser l’opération 10 & 240, soit 0000 1010 pour 10 & 1111 0000 pour 240 0000 0000 soit 0 l’adresse du réseau est donc 192.168.0.0. 2. la 1ère machine a pour adresse : 192.168.0.1 et la dernière a pour adresse : 192.168.15.254 En partant de la droite, le 1er octet peut aller jusqu’à 255 (1111 1111), le deuxième octet n’a que 4 bits de disponible donc sa valeur maximale est 15 (1111) Or l’adresse 192.168.15.255 est l’adresse de broadcast, elle n’est pas utilisable. 3. le masque laisse 12 bits de disponibles pour les adresses machines, soit 2**12 possibilités mais il faut retirer l’adresse du réseau et l’adresse de broadcast soit 4096-2 = 4094 (on vérifie bien que 16 x 256 = 4096) C’est un réseau de type C (avec le 1er octet compris entre 192 et 223)