Algorithmique puante

Question 1

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un algorithme ?

Answer 1

Un algorithme est un suite d’opérations censée résoudre un problème. Il manipule des données d’entrée et produit une sortie répondant au problème.

Question 2

2 - Algo - Variables, Types et Valeurs

Qu’est-ce que le typage ?

Au sens de la classification.

Answer 2

Le typage c’est le fait de classifier des données (par types) selon les opérations qui sont possibles.

Par exemple : Deux nombres peuvent être additionnés ensemble alors que deux chaînes de caractères peuvent être concaténées ensemble.

Question 3

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type ?

Answer 3

Un type c’est un ensemble de valeurs et des opérations possibles sur ces valeurs. Un type vérifie un certain nombre de propriétés et on le représente par un identifiant (son nom).

Question 4

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’une donnée ?

Answer 4

Une donnée c’est une constante OU une entité qui possèdde un type, une valeur et un identifiant.

Question 5

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’une variable ?

Answer 5

Une variable est une entité qui va pointer sur un espace mémoire.

Question 6

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type primitif ?

Answer 6

Un type primitif est fourni par défaut et a une valeur non décomposable.

Dans le cadre du cours, on fournit les entiers, les réels, les caractères, les booléens et les chaînes de caractères.

Question 7

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type composé ? Citer les quatre types composés vus en cours.

Answer 7

Un type composé est construit à partir d’autres types. Dans ce cours on compte :

• Le type produit
• Le type somme
• Le type enregistrement
• Le constructeur de tableau

Question 8

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type produit ? En donner un exemple.

Formellement.

Answer 8

Soient T₁, T₂, …, T_n de types.
Le type produit, c’est le produit cartésien des T_i avec comme valeurs (x₁, x₂, …, x_n) pour tout x_i une valeur du type T_i

Par exemple : un tuple en python.

Question 9

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type somme ? En donner un exemple.

Formellement

Answer 9

Soient T₁, T₂, …, T_n de types.
Le type somme T est la somme des T_i si chaque valeur de x est une valeur d’un certain T_i et chaque valeur d’un T_i est une valeur de T.

Par exemple : une union en C.

Question 10

2 - Algo - Variables, Types et Valeurs

Qu’est-ce qu’un type enregistrement ?

Formellement.

Answer 10

Le type enregistrement est composé de pusieurs entités appelées champs, chacun ayant un identifiant, un type et une valeur.

Question 11

2 - Algo - Variables, Types et Valeurs

Quest-ce que le constructeur de tableau ?

Answer 11

Un tableau est un ensemble de valeurs contigues avec accès constant.. Pour réserver la place mémoire pour n valeurs de taille p, on réserver n x p bits.

Question 12

3 - Algo - Types de données abstraits (TDA)

Qu’est-ce qu’un TDA ?

Answer 12

Une TDA c’est une entitée constituée :

1. D’une signature
2. D’une liste d’axiomes

Question 13

3 - Algo - Types de données abstraits (TDA)

Que contient la signature d’un TDA ?

Answer 13

La signature est composée de :

• Un identifiant
• Les identifiants, paramètres et types de retours de chaque opération
• Un ensemble de types prédéfinis à utiliser

Question 14

3 - Algo - Types de données abstraits (TDA)

A quoi servent les axiomes d’un TDA ?

Answer 14

Les axiomes d’un TDA définissent le comportement des opération sur les valeurs du TDA.

Question 15

3 - Algo - Types de données abstraits (TDA)

Qu’est-ce qu’une implémentation ? En quoi cela résulte ?

Answer 15

Une implémentation c’est une façon de représenter en machine le TDA en proposant une façon de manipuler cette représentation au travers des opérations du TDA. Cela résulte en un Type de Données Concret (TDC).

Question 16

3 - Algo - Types de données abstraits (TDA)

Quel est le paradigme d’une pile ?

Answer 16

Last in, First out (LIFO)

Question 17

3 - Algo - Types de données abstraits (TDA)

Quel est le paradigme d’une file ?

Answer 17

First in, First out (FIFO)

Question 18

4 - Algo - Elements de complexité

Qu’est-ce qu’un algorithme valide ?

Answer 18

Un algorithme valide pour un problème est un algorithme qui le résout. Plus précisémment, pour toute instance valide en entrée, l’algorithme doit calculer le résultat attendu.

Question 19

4 - Algo - Elements de complexité

Quels sont les critères de qualité d’un algorithme ?

Answer 19

• La quantité d’espace mémoire utilisée
• Le temps de calcul

Question 20

4 - Algo - Elements de complexité

Comment mesure-t-on la performance temporelle d’un algorithme ?

Answer 20

On donne une valeur à chaque instance et on mesure le nombre d’instructions par rapport à cette valeur.

Question 21

4 - Algo - Elements de complexité

Comment évalue-t-on le nombre d’instructions ?

Answer 21

On utilise la fonction valeur(x) qui est robuste et indépendante de l’encodage. On suppose alors que :

• Les entiers sont représentés en base x, x ≥ 2
• La représentation d’un ensemble E ne dépasse pas :
  (taille d’un élément) x |E| x c

Question 22

4 - Algo - Elements de complexité

Quel est l’ensemble des fonctions majorées par :
f : x ↦ 3x + 5

Answer 22

O(3x + 5)

Question 23

4 - Algo - Elements de complexité

Quel est l’ensemble des fonctions minorées par :
f : x ↦ x²

Answer 23

Ω(x²)

Question 24

4 - Algo - Elements de complexité

Quel est l’ensemble des fonctions bornées par :
f : x ↦ x²

Answer 24

θ(²)

Question 25

4 - Algo - Elements de complexité

Quelle est la complexité d’un algorithme A ?

Formellement

Answer 25

On note C_A le nombre d’instructions de l’algorithme, on a l’égalité suivante :

Question 26

4 - Algo - Elements de complexité

Quelle est la complexité d’une affectation ?

Formellement

Answer 26

Si I est une affection et x une expression, on a l’égalité suivante :

Question 27

4 - Algo - Elements de complexité

Quelle est la complexité d’une expression arithmétique ?

Formellement

Answer 27

Si I est un expression arithmétique, alors on a l’égalité suivante.

Question 28

4 - Algo - Elements de complexité

Quelle est la complexité de lecture d’une variable ?

Answer 28

Une variable se lit en temps constant.

Question 29

4 - Algo - Elements de complexité

Quelle est la complexité d’un appel de fonction ?

Formellement

Answer 29

Si I = f(e₁, e₂, …, e_p), alors on a l’égalité suivante.

Question 30

4 - Algo - Elements de complexité

Quelle est la complexité d’une boucle ?

Formellement

Answer 30

Si I est une boucle avec l itérations et à chaque itération on exécute l’algorithme A_i, alors on a l’égalité suivante.

Question 31

4 - Algo - Elements de complexité

Quelle est la complexité d’une condition ?

Formellement

Answer 31

Si I est une condition, alors on a l’égalité suivante.

Question 32

5 - Algo - TDA Listes

Classez les complexités suivantes :

• logarithmique
• linéaire
• polynomiale
• factorielle
• exponentielle
• constante
• quadratique
• polylogarithmique

Answer 32

• constante : O(1)
• logarithmique : O(log(n))
• polylogarithmique : O(log(n)^c
• linéaire : O(n)
• quadratique : O(n₂)
• polynomiale : O(n^c)
• exponentielle : O(cⁿ)
• factorielle : O(n!) ≃ O(2^nlog(n))

Question 33

5 - Algo - TDA Listes

Qu’est-ce que le TDA liste ?

Answer 33

Le TDA liste est un ensemble ordonné avec un accès direct au premier élément. A partir de ce premier élément, on peut accéder au deuxième, puis au troisième, etc.

Question 34

5 - Algo - TDA Listes

Donnez deux implémentations avec un tableau des listes simplement chaînées.

Answer 34

• Un tableau dont le contenu des cases est la position de l’élément suivant.
• Une tableau dont le contenu des cases est un enregistrement Cellule_T qui contient l’indice de l’élément suivant.

Question 35

5 - Algo - TDA Listes

Comment concaténer deux listes en temps constant ?

• Listes simplement chaînéées
• Listes simplement chaînée circulaires
• Listes doublement chaînées circulaires

Answer 35

• Il faut avoir un accès constant au début et à la fin
• Il faut créer un case tampon que l’on ne supprime jamais et qui sera toujours le premier élément de la liste
• Il faut faire pointer la fin de l’une au début de l’autre et le début de l’autre à la fin de l’une, c’est le cas le plus naturel

Question 36

6 - Algo - Graphes

Quelles sont les deux solutions communes pour représenter un graphe ?

Détaillez les représentations.

Answer 36

• Matrice d’adjacende

Il s’agit (i) d’un tableau de taille n, dont les indices représentent les sommets et les valeurs les couleurs. (ii) d’une matrice booléenne de taille n² telle que la case (i, j) vaut 1 si (i, j) est une arête.

• Matrice d’incidence ou Liste d’adjacence

Il s’agit d’un tableau de taille n, dont les indices représentent les sommet et dont chaque case contient les deux informations suivantes : (i) la couleur, (ii) la liste des sommets voisins.

Question 37

6 - Algo - Graphes

Quelle est la complexité en mémoire de la matrice d’adjacence ?

Answer 37

O(n² + n), avec n le nombre de sommets.

Question 38

6 - Algo - Graphes

Quelle est la complexité en mémoire de la matrice d’incidence ?

Answer 38

O(n + m), avec n le nombre de sommets et m le nombre d’arêtes.