Algorithmique puante Flashcards
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un algorithme ?
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.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce que le typage ?
Au sens de la classification.
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.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type ?
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).
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’une donnée ?
Une donnée c’est une constante OU une entité qui possèdde un type, une valeur et un identifiant.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’une variable ?
Une variable est une entité qui va pointer sur un espace mémoire.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type primitif ?
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.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type composé ? Citer les quatre types composés vus en cours.
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
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type produit ? En donner un exemple.
Formellement.
Soient T1, T2, …, Tn de types.
Le type produit, c’est le produit cartésien des Ti avec comme valeurs (x1, x2, …, xn) pour tout xi une valeur du type Ti
Par exemple : un tuple en python.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type somme ? En donner un exemple.
Formellement
Soient T1, T2, …, Tn de types.
Le type somme T est la somme des Ti si chaque valeur de x est une valeur d’un certain Ti et chaque valeur d’un Ti est une valeur de T.
Par exemple : une union en C.
2 - Algo - Variables, Types et Valeurs
Qu’est-ce qu’un type enregistrement ?
Formellement.
Le type enregistrement est composé de pusieurs entités appelées champs, chacun ayant un identifiant, un type et une valeur.
2 - Algo - Variables, Types et Valeurs
Quest-ce que le constructeur de tableau ?
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.
3 - Algo - Types de données abstraits (TDA)
Qu’est-ce qu’un TDA ?
Une TDA c’est une entitée constituée :
- D’une signature
- D’une liste d’axiomes
3 - Algo - Types de données abstraits (TDA)
Que contient la signature d’un TDA ?
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
3 - Algo - Types de données abstraits (TDA)
A quoi servent les axiomes d’un TDA ?
Les axiomes d’un TDA définissent le comportement des opération sur les valeurs du TDA.
3 - Algo - Types de données abstraits (TDA)
Qu’est-ce qu’une implémentation ? En quoi cela résulte ?
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).
3 - Algo - Types de données abstraits (TDA)
Quel est le paradigme d’une pile ?
Last in, First out (LIFO)
3 - Algo - Types de données abstraits (TDA)
Quel est le paradigme d’une file ?
First in, First out (FIFO)
4 - Algo - Elements de complexité
Qu’est-ce qu’un algorithme valide ?
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.
4 - Algo - Elements de complexité
Quels sont les critères de qualité d’un algorithme ?
- La quantité d’espace mémoire utilisée
- Le temps de calcul
4 - Algo - Elements de complexité
Comment mesure-t-on la performance temporelle d’un algorithme ?
On donne une valeur à chaque instance et on mesure le nombre d’instructions par rapport à cette valeur.
4 - Algo - Elements de complexité
Comment évalue-t-on le nombre d’instructions ?
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
4 - Algo - Elements de complexité
Quel est l’ensemble des fonctions majorées par :
f : x ↦ 3x + 5
O(3x + 5)
4 - Algo - Elements de complexité
Quel est l’ensemble des fonctions minorées par :
f : x ↦ x2
Ω(x2)
4 - Algo - Elements de complexité
Quel est l’ensemble des fonctions bornées par :
f : x ↦ x2
θ(2)
4 - Algo - Elements de complexité
Quelle est la complexité d’un algorithme A ?
Formellement
On note CA le nombre d’instructions de l’algorithme, on a l’égalité suivante :
4 - Algo - Elements de complexité
Quelle est la complexité d’une affectation ?
Formellement
Si I est une affection et x une expression, on a l’égalité suivante :
4 - Algo - Elements de complexité
Quelle est la complexité d’une expression arithmétique ?
Formellement
Si I est un expression arithmétique, alors on a l’égalité suivante.
4 - Algo - Elements de complexité
Quelle est la complexité de lecture d’une variable ?
Une variable se lit en temps constant.
4 - Algo - Elements de complexité
Quelle est la complexité d’un appel de fonction ?
Formellement
Si I = f(e1, e2, …, ep), alors on a l’égalité suivante.
4 - Algo - Elements de complexité
Quelle est la complexité d’une boucle ?
Formellement
Si I est une boucle avec l itérations et à chaque itération on exécute l’algorithme Ai, alors on a l’égalité suivante.
4 - Algo - Elements de complexité
Quelle est la complexité d’une condition ?
Formellement
Si I est une condition, alors on a l’égalité suivante.
5 - Algo - TDA Listes
Classez les complexités suivantes :
- logarithmique
- linéaire
- polynomiale
- factorielle
- exponentielle
- constante
- quadratique
- polylogarithmique
- constante : O(1)
- logarithmique : O(log(n))
- polylogarithmique : O(log(n)c
- linéaire : O(n)
- quadratique : O(n2)
- polynomiale : O(nc)
- exponentielle : O(cn)
- factorielle : O(n!) ≃ O(2nlog(n))
5 - Algo - TDA Listes
Qu’est-ce que le TDA liste ?
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.
5 - Algo - TDA Listes
Donnez deux implémentations avec un tableau des listes simplement chaînées.
- 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.
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
- 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
6 - Algo - Graphes
Quelles sont les deux solutions communes pour représenter un graphe ?
Détaillez les représentations.
- 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 n2 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.
6 - Algo - Graphes
Quelle est la complexité en mémoire de la matrice d’adjacence ?
O(n2 + n), avec n le nombre de sommets.
6 - Algo - Graphes
Quelle est la complexité en mémoire de la matrice d’incidence ?
O(n + m), avec n le nombre de sommets et m le nombre d’arêtes.
