Publier

INFO-H-304 Compléments de programmation et d'algorithmique

< Retour

Oral - 11 Jan 2022 - 27 May 2022

Programmation - delete Head

En C, crée une fonction delete_Head(node* tete) qui efface la tete d’une liste doublement chainée et qui renvoie le pointeur vers la nouvelle tete. En annexe on a le constructeur de node.

Rép :
node* delete_Head(node* tete){
_ if ( tete != NULL && tete-> suivant !=NULL){
_ _ tete = tete->suivant;
_ _ free(tete->previous->data);
_ _ free(tete->previous);
_ _ tete-> previous = NULL;
_ }
_ return tete;
}

Au départ j’avais fait une version avec node* new_tete = tete->suivant, c’était correct mais il voulait savoir si je savais faire qqch de + opti et du coup c’est comme ça qu’il fallait faire pcq ça prend - de mémoire.

Algorithme - Tas et tas-max
Donner la définition d’un tas et d’un tas max. Le tableau donné en exemple est-il un arbre binaire complet ?
Le tableau donné en exemple est-il un tas max ? Si ce n’est pas le cas, comment le corriger ?
Complexité de la fonction max heapify
Quelles sont les 4 fonctions qu’une queue de priorité max doit forcément posséder ? Donner leur complexité

Réponses
Un tas est un tableau que l’on peut illustrer sous la forme d’un arbre binaire. Le tableau donné en exemple n’est pas un arbre binaire complet car l’étage des feuilles n’est pas rempli. Certains parents n’ont pas d’enfant.
Un tas max est un tas où la clé de tout parent est plus grande que celle de ses enfants. /!\\ Bien préciser que cette propriété est valable pour tout parent.
Le tableau n’est pas un tas max car l’un des clés enfant était plus grande que la clé parent. On peut le transformer en tas max en swapant les clés avec max heapify comme vu en cours.
O(logn) -> démo dans le cours
IncreaseKey en O(logn)
ExtractMax en O(logn)
Insert en O(logn)


Programmation - 11 Jan 2021

Réalisez, de la manire la plus concise possible, la fonction C suivante

void substring(char* x, char* y, int i, int j)
qui remplace la chaîne y par la sous-chaîne constituée des caractères aux positions i à j de
de x (le premier caractère correspondant à la position 0). Par exemple, si x contient
la chaine \"abcdef\", la chaîne y devrait être \"bcd\" après appel à substring(x,y,1,3).

Illustrez l\'utilisation de cette fonction en écrivant une fonction main() y faisant appel.

Programmation - 11 Jan 2021

Qu\'est-ce qu\'une fonction de hachage? Quand parle-t-on de collision pour une telle fonction?
Méthode de chaînage:
- Expliquez la méthode de chaînage et la notion de facteur de charge.
- Expliquez le principe des opérations d\'insertion, de recherche et de suppression.

Oral Janvier 2021 - 9 Janvier - 9 Jan 2021

1) Programmation :
C++
\"Ecrire une une fonction void insereElement( int data, Noeud* noeud) qui insère un nouveau noeud dans une liste chainée juste après le noeud pointé par noeud. On peut faire appel au constructeur Noeud(int data=0) de la classe Noeud supposée déjà implémentée\"
Questions subsidiaires :
- ils donnent un bout de code où les attributs suivant et data de la classe Noeud sont en public => il va en faire une question subsidiaire d\'encapsulation.
- Que se passe-t-il si noeud pointe vers null ?

1) Algorithmique : AVL
Définir : arbre binaire, arbre binaire de recherche, arbre binaire de recherche équilibré, AVL.
Faire insertion de l\'élément 20 dans l\'arbre contenant 15 12 25 37 31 42

Il est vraiment gentil et pose des questions pour aiguiller vers la bonne réponse en cas de boulette.

Programmation - 7 Janvier 2021 - 9 Jan 2021

Réalisation d\'une fonction qui vérifié si la chaine de caractère passée en entrée est un palindrome. ( ex : kayak)
Elle doit retourner 1 si c\'est un palindrome et 0 sinon.
-> int strpal(char* s);

Démontrer la borne inférieure de la complexité des tris par comparaison - 7 Jan 2021

Question en quatre partie : définir les tris par comparaison, démontrer la borne inférieure (Omega(nlog(n)) , donner des exemples de tris en cette complexité, possible de faire mieux que cette complexité dans certains cas ?
Le plus important était la compréhension d\'un arbre de décision (feuilles = ?, branches = ?, de quoi dépend la structure ?...). Il y avait aussi beaucoup de petites questions de vérification de compréhensions.

Creation d\'un noeud dans une liste doublement chaînée en C - 5 Jan 2021

Code initial :
typedef struct node_t{
int* data;
struct node_t* next;
struct node_t* previous;
} node;

Réaliser la fonction C suivante :
node* create_node(int data)
qui renvoie un pointeur vers un nouveau noeud dont l\'attribut data pointe vers un nouvel entier ayant la valeur data passée en paramètre

Pas nécessaire d\'implémenter une fonction main

// Code réponse
node* create_node(int data){
node* new_node = malloc(sizeof(node)) ;
new_node->next = NULL ;
new_node->previous = NULL ;

new_node->data = malloc(sizeof(int)) ;
*(new_node->data) = data ; // copie la valeur de data dans l\'adresse pointée par node->data

return new_node ;
}

Analyse du code :
- d\'abord initialiser les pointeurs à NULL. Pourquoi ? Pcq sinon il prend des valeurs qu\'on ne maîtrise pas et qui sont certainement pas celles qu\'on aimerait. Deux possibilités : pointe vers une adresse mémoire hors du tas réservée par un autre programme (segmentation fault), ou pointe vers une adresse du tas du programme, qui n\'est normalement pas libre! et on a alors une perte de données.
-

Tas-Max - 5 Jan 2021

Question brutes :
- définirs tas, tas-max, il donne un exemple (celui du cours!) et demande si c\'est un tas-max, comment faire pour corriger, et corriger la(les) violation(s).
- ensuite : comment extraire le maximum ? Fonctionnement et complexité de la méthode. L\'appliqué à l\'exemple donné.

Questions subsidiaires (il m\'a attendu au tournant !) : déjà à chaque phrase il pose une nouvelle question, et chacune de ses phrases est orientée de sorte à nous faire dire des choses périlleuses !
- Comment je peux lire le tableau ? (facile, on reprend le slide avec Parent(i), Left(i), ...)
- On représente quoi dans le tableau ? des objets ? des clés ? (Rép : des objets qui ont plusieurs attributs, dont la clé)
- Quelle est la condition pour que maxHeapify fonctionne ? (Rép : il faut que ça soit la violation la plus basse qu\'on veuille corriger ! Sinon on peut penser que c\'est ok alors que ça ne l\'est pas en dessous !)

- Pourquoi quand on extrait, on échange avec l\'élément de la fin ? Pourquoi pas juste créer un trou dans le tableau ? (Rép : ça engendrerait trop de faux positifs, pcq il faudrait redéplacer tous les éléments du tableau et qu\'on aurait un coût linéaire en n plutôt qu\'un log(n) comme prévu)

- Alors que la question ne portait pas du tout sur ça : quid de construire un tas-max ? Là j\'ai eu un trou de mémoire ! Je me suis rappelé qu\'il fallait partir du noeud n/2 et remonter progressivement dans les noeuds (n/2 -> 1; n--) en appliquant maxHeapify à tous les noeuds (ce qui a pour effet de corriger toutes les violations en dessous de chaque noeud à chaque étape). Complexité : O(n). Pourquoi est-ce rassurant ? (Rép : pcq on peut alors construire un beau tas-max en un même temps que construire un tableau désordonné)

Algorithmique - 5 Jan 2021

2) Tas et tas max :
Qu’ est ce qu’un tas et tas-max
Comment est stocké un tas en mémoire et comment est ce que l\'ordi accède aux éléments :
par exemple : si j\'ai la position d\'un enfant de gauche comment est ce que je connais son parent : il faut faire position de l\'enfant de gauche/2;
On donne un tableau, dire si c’est un tas max si non pourquoi ?
Correction pour avoir un tas max sur le tableau donné.
Complexité pour la construction d’un tas max à partir d’un tableau non trié.


Programmation - 5 Jan 2021

Introduire un nœud en tête d’une liste doublement chaînée.
void insertHead(){
noeud* new_tete = createNoeud(data);
if (tete != NULL){
new_tete->next=tete;
tete->previous=new_tete;
}
return new_tete; // la fonction createNoeud doit mettre à NULL les pointeurs next et previous;
}

Programmation - 4 Jan 2021

le prof donne un bout de code pour définir un struct node comme le TP2 de C où on implémente une liste doublement chaînée et il faut coder la fonction create_node qui crée un élément dans la liste chaînée

bout de code donné par le prof :
typedef struct node_t {
int* data;
struct node_t* next;
struct node_t* previous;
} node;

code demandé (validé par le prof) :
node* create_node(int data){
// on crée des pointeurs vers new_node et data
// donc on doit appliquer malloc pour leur allouer de la mémoire dynamiquement
node* new_node = malloc(sizeof(node));
new_node->data = malloc(sizeof(int));
// l\'attribut data du new_node est un int*, on utilise donc *(new_node->data) pour définir le int pointé
*(new_node->data) = data;
// on définit les pointeurs \"next\" & \"previous\" à NULL pour ne pas avoir de pointeurs fous
new_node->next = NULL;
new_node->previous = NULL;
return new_node;
}

Algorithmique - 4 Jan 2021

donner et expliquer les complexités de Insert, Delete, Search pour un tableau trié et une liste doublement chaînée non-triée, et quelle structure de données on peut utiliser pour mieux implémenter ces fonctions (parler de table de hachage)

Algorithmique - Hachage - 4 Jan 2021

- fonction de hachage et collision
-méthode d\'adressage ouvert
- facteur de charge
- principe des opérations Insert, Search et Delete
> pour le Delete, bien expliquer qu\'il faut marquer l\'emplacement \"Deleted\" et pourquoi

Questions supplémentaires
- coût des opérations en fonction de alpha ou n et m (theta(1) est ce qu\'on veut, pas toujours ce qu\'on a!)
--> quel serait le alpha optimal (le + faible possible pour que m>>n -> min de collisions)

Programmation - Liste doublement chaînée - 4 Jan 2021

On nous donne la déclaration des classes Liste (doublement chaînée) et Nœud (contenant un entier) et on demande d\'implémenter :
1) les constructeurs de Nœud (\"qui prend en paramètre optionnel un int dont la valeur par défaut est 0\") et de Liste
2) les destructeurs de Nœud et Liste (pour lequel on peut utiliser la fonction supprimeTete() qu’on suppose déjà implémentée et qui supprime le nœud en tête de liste)
Pas besoin de fonction main.

Questions supplémentaires :
- Est-ce vraiment nécessaire de redéfinir le destructeur de Noeud?
> Non, le destructeur par défaut suffit, par contre le destructeur de Liste doit être redéfini!)
- Que se passe-t-il si on delete qqch de NULL?
> On delete un emplacement qui n\'existe pas (/!\\ emplacement qui n\'existe pas != emplacement vide, il insiste sur les termes utilisés) --> erreur de segmentation

4 Janvier 2021 - 4 Jan 2021

Question Algo : Borne inférieur par le pour le tri.
- expliquer la notion d\'algorithme par comparaison
- prouver que tout algorithme de ce type requirte OMEGA(nlogn) comparaison.
- Donnez des exemple d\'algo atteingant cette borne.
est-il dans certains cas possible de trier n éléments en moin de O(nlogn)? expliquez


quesition C : Fonction sous chaine
Réaliser la sous chaine y de avec les élément allant i a j dans x de la fonction suivante :
substring(char* x, char* y, i, j);
implémenter ça dans un code avec un main.

Janvier 2020 - Algorithmique - 1 Jan 2021

1) fonction de hachage ? Qu’est-ce qu’une collision ? Comment l’éviter ? Citer 2 méthodes et un peu leur fonctionnement.
Méthode de chaînage : explication de tout ce qu’il y a sur le slides de cette partie. Qu\'est-ce que la fonction de charge ? Comment l\'optimiser. Expliquer un peu les fonctions d\'insertion, de suppression et de recherche (coût).

2) Qu’est-ce qu’une fonction de hachage ? Qu’est-ce qu’une collision ? Comment l’éviter ? Citer 2 méthodes et un peu leur fonctionnement.
Définir la notion de facteur de charge. Expliquer insert delete search pour l’adressage ouvert et leur complexité.
Dire que c’est une fonction qui va d’un grand ensemble a un petit ensemble. expliquer ce qu’est U (univers = ensemble des clé possibles (attribut des objets d\'un ensemble dynamique)) ce qu’est [m]. Principe de collision et pq ca arrive tout le temps (fonction pas injective). Chaînage et adressage ouvert, bien dire à quoi correspond un élément de la table pour chaque (pointeur vers tête de liste chainée et objet à proprement parlé). alpha = n/m (<= 1 pour adressage ouvert). n est le nbre d’elem dans la table et m est la table. Expliquer la propriété de permutation et expliquer le principe de double de hachage et dire dans quelle circonstances la propriété est vérifiée (m et h’’(k) relativement premiers> ex: m = puissance de 2 et h’’ impaire + donner exemple ou ca marche pas (m = 4 et h’’ = 2))). insert delete search faut juste expliquer avec ses mots et des schémas ça va. Bien expliquer pq on a mis le flag deleted (sinon search marche pas (mais insert fonctionne toujours qu’il y ai le flag deleted ou pas) ). Leur complexité est, sous l’hypothèse de hachage uniforme, en O(1/(1-alpha)). expliquer la signification de ce grand O et dire que si alpha = 1 alors n = m et donc les opérations prennent un temps infini.

3) Expliquer le principe de programmation dynamique. Citer les 5 grandes étapes. ATTENTION APPLIQUER AU PROBLÈME RENDU DE MONNAIE => Relire les exemples du cours sinon tu te fais taht :’( S(h) = min (1+S(h-vi)); S(0) = 0; S(<0) = inf Donner la complexité du problème Theta(m*n) m(rendu) n(nombre de pièce)
Si jamais t’es perdu résout en glouton, vaut mieux ça que rien

4) Borne inférieure pour le tri par comparaison : dire qu’est ce que c’est un tri par comparaison (! faut dire c’est un tri où on fait que des comparaison). Prouver que c’est un opération qui demande au moins n log(n) comparaison. Donner des exemple de tri avec un coût de n log n. Est ce qu’il y a moyen d’avoir un tri qui demande moins d’opération si on n’utilise pas de comparaison ?

5) Quicksort
- Décrire l’algorithme pour un tableau donné (le pseudo code est pas demandé explicitement mais ça me semble indispensable pour expliquer, surtout pour la suite)
- Stable ? (non car la dernière ligne de l’algo (échange du pivot avec l’élément en i+1) change potentiellement l’ordre d’éléments de même valeur de clé)
- En place ? Oui car on fait tout sur le tableau par référence => mémoire supplémentaire requise en O(1) et pas O(n) (définition rigoureuse de en place, il est pas trop fan de “on copie pas le tableau” mais il aide quand on part de là)
- Analyse de complexité en meilleur (nl = nr = n/2, ?(n log n) (voir cours)et pire cas (nl = n-1 et nr = 0 ou inversement, ?(n²)). Question pas sur la fiche : oui mais pour le tri par insertion ? (?(n²) en moyenne et pire cas, ?(n) en meilleur cas) => si on a du linéaire avec insertion pq utiliser quicksort ? pcq en moyenne insertion = n² et quicksort = n log n
- Comment éviter les pires cas ? Quicksort randomisé


6) Arbre binaire
- Définir arbre binaire et arbre binaire de recherche
- Sous quels conditions un arbre est équilibré
- Définir un arbre AVL
- Il donne un arbre et dire comment se fait l’insertion. Dans mon exemple il y avait une violation ligne après l’insertion qu’on corrige.

7) Tas
- Définir Tas et Tas-max (savoir définir structure de donnée+type de donnée)
- donner principale application tas-max
- tableau donné, dire si c’est un tas max et dire pourquoi; si non le corriger et pouvoir donner le coût de l’opération.
- Expliquer comment extraire le max d’un tas-max et donner sa complexité. Savoir expliquer pq la taille h d’un arbre est log(n), et enfin appliquer l’algo pour extraire le max du tableau donné.

8) Tri radix :
- Expliquer le tri
- Est-il en place ? Est-il stable ?
- trouver la complexité du tri, quelle base serait optimale ? (perso je connaissais pas ça du tout, il m’a aidé à retrouver ça)
- Pourrais-t-on faire un tri radix avec autre chose que le tri par comptage ?
- Pourrais-t-on faire un tri radix avec autre chose que le tri par comptage ?


Janvier 2020 - Programmation - 1 Jan 2021

1. Manipulation de pointeur : presque exactement la slide dessus, quelques sous questions : dépassement de tampon et erreur de segmentation; tableau y[6] qu\'est-ce qu\'il se passe si on fait y[11]=x par exemple et pourquoi on peut, pour un pointeur ip, faire ip = y + 2 mais pas y = ip + 2 (car y est un pointeur ET une allocation de mémoire)

2. Compter la longueur d’une chaîne (exemple du cours dans la partie c) : int strlen( char* x) de manière la plus concise possible. Il demande alors tout ce qui pourrait arriver si on essaye de lancer la fonction avec un pointeur char* y non initialisé.
Peut-on égaler un pointeur char* y avec un tableau char x[5] et pourquoi? (dans un sens oui, mais pas l’autre).

3. faire une fonction en C++ qui permet d’imprimer une liste chainé, il donne une feuille avec le fichier .h pour la liste et les Noeud et le fichier .c avec une partie des fonctions écrite

4. fonction en C d’effacement d’un nœud en liste chainée. on donne current et on doit effacer current->next. Attention si data est un pointeur il faut aussi le free (avant de free le pointeur du suivant sinon ca marche pas).

5. Fonction en C qui rajoute une chaîne de caractères au bout d\'un autre, que se passe-t-il si le premier mot n\'est pas assez long pour contenir le deuxième x (dépassement de tampon)?

6. Fonction en C, pour une liste simplement chaînée (avec chaque noeud rpzté par une structure int* data nedo* next) , donner la fonction
void delete_next(nedo* current) qui supprime le nœud suivant le nœud pointé par current.
nedo* temp = current->next;
free(temp->data);
current->next = temp->next;
free(temp);
si tout va bien c’est le bon code

7. Fonction en c pour une liste chaînée, il faut ajouter un nœud en tête d’une liste (il donne une fonction pour créer un nœud et les structures) il faut 3 lignes. Il est plus intéressé par ce qui se passe dans la mémoire.

Janvier 2018 - Algorithmique - 1 Jan 2021

1. Tri fusion (A2)
- Expliquer le principe du tri par fusion
- L’appliquer sur un tableau donné (de 6 éléments dans mon cas) et expliquer avec des schémas. (Dire que c’est du Divide&Conquere, il a kiffé)
- Dire si le tri est en place ? Stable ? Et expliquer.
- Calculer sa complexité et expliquer (arbre de récurrence, hypothèses et tout le blabla).
- Question assez simple dans l’ensemble , il demande surtout bien d’expliquer l’arbre de récurrence, ainsi que toutes les hypothèses qu’on fait pour avoir la récurrence et l’arbre. Surtout bien expliquer pourquoi la hauteur vaut log(n) ! Il insiste aussi sur le “pourquoi au feuille on a 1” et “pourquoi il y a n éléments aux feuilles”. Comparaison avec le tri par insertion, il pose des questions pour voir si on a été un peu plus loin. (tri insertion complexité en n^2 bien pour n petit…) mais il est vraiment cool et aide beaucoup.

2. Hachage/adressage
- Expliquer/définir : fonction de hachage, principe de collision
Voir la théorie, et l’examen de f pour avoir une idée de quoi répondre
Questions en plus :
- Est-il possible de ne pas avoir de collision du tout ?
- Que faudrait-il faire pour ne pas en avoir du tout ?
- Donner 2 moyens d’éviter les collisions (chainage et adressage ouvert)
Faire un schéma pour le premier, bien dessiner la liste chainée avec des (§et des noeuds avec 2 éléments. La 2è réponse mène à la question suivante.

- Expliquer le principe de l’adressage ouvert
- Signification du facteur de charge alpha
- Comment fonctionne la recherche, l’insertion et la suppression pour ce dernier
- Préciser qu’on donne une séquence de case à parcourir.
- Connaitre la propriété de permutation, en quoi elle est utile.
- Pour la suppression, le détail important est qu’une case est marquée supprimée après une telle opération + les conséquences/pourquoi on fait ça

3. définir tas et tas max.
- Principale utilisation du tas max ?
- a partir d’un tableau de tas ( non max ) déterminer si le tas est max ou non, pourquoi ?
- Si non que faire pour le transformer en tas max ? ( fonction, expliquer comment ça fonctionne et complexité ) => appliquer au tas pour obtenir un tas max
- expliquer le principe de l’extraction du maximum, appliquer sur le tas précédent. Compléter avec la complexité

4. Tri Quicksort
- définir le principe du tri Quicksort
- illustrer avec un tableau donné
- quel type de méthode d’algorithmique ? Divide and conquer
- tri en place ? oui, qu’est-ce que ça veut dire, pourquoi ?
- tri stable ? non, qu’est-ce que ça veut dire, pourquoi ? l’échange du pivot à la fin perturbe l’ordre
- meilleur cas, complexité (nlog(n)) montrer via l’arbre de récurrence
- pire cas, complexité (n2) montrer via l’arbre de récurrence
- pourquoi cet algorithme est quand même mieux que le tri par insertion ?


5. Programmation dynamique
- Donner le principe général, les cas d’utilisations et les 5 étapes de mise en oeuvres.
- Savoir faire le lien avec backtracking et donner la complexité

6. Structure de données
- On a un problème dynamique qui utilise les instructions insert, delete et search. On propose 2 structures de données: le tableau trié et la liste chaînée. Il faut donner les complexités de ses 3 instructions pour chacune. Puis proposer une meilleure structure de donnée pour répondre à ce problème.

7. Arbre binaire de recherche et AVL
- Définissez ce qu’est un arbre binaire et arbre de binaire de Recherche
- Quelle est la condition pour que l’arbre binaire de recherche soit équilibré?
- Quelle est la caractéristique particulière d’un arbre AVL?
- Etant donné l’arbre AVL suivant, on souhaite vouloir y insérer l’élément de clé 20. Expliquez les différentes étapes d’insertion et donnez la structure finale de l’arbre

Janvier 2018 - Programmation - 1 Jan 2021


1. (P3) Ecrire un code en C pour implémenter une fonction strconc(char * x, char* y) qui concatène deux chaînes de caractères.
Code simple vu au TP, il demande aussi comment l’écrire sous forme compacte (avec des trucs en mode while(*x++=*y++) et bien expliquer qu’est ce qui est fait avant quoi, la copie ou le test etc..)
Que se passe-t-il si on l’applique a :
char x[]=”hello”;
char y[]=” world”;
strconc(x,y);
? dépassement de tampon.

2. Manipulation de pointeur, notion de pointeur fou.
Le code ci-dessous est (de mémoire) la question de l’examen, mais l’important est de comprendre les opérations effectuées ligne par ligne.
Il fallait donc simplement dire ce qui se passe à chaque étape, le code en lui même n’ayant aucun sens (précisé par le prof). A la fin, il faut donner la valeur de x ainsi que le contenu de y.
Il est fortement recommandé de représenter toutes les variables, sauf i éventuellement dans ce cas-ci.
Question supplémentaire hors énoncé: Quelle est la valeur de x juste après la fin de la boucle (réponse: 4 et non 5 ! Alors ne serait-ce pas plutôt --x qui était écrit?) (peu importe non ? puisque x sera quand même changé juste après la boucle…)Non parce que comme x-- est dans une expression d’affectation, il n’équivaut pas à --x => y[i] = x-- signifie que y[0]=10, y[1]=9….y[5]=5 MAIS y[i]==--x implique y[0]=9, y[1]=8….y[5]=4)? Effectivement, y[5]=5. et comme dans x-- la décrémentation se fait après l’assignation, lorsqu’on sort de la boucle x vaudra alors 4

int main(){
int i, int x = 10, y[6];
int* ip;
for (i=0; i<6; i++)
y[i] = x--; // différent de --x !
ip = &x;
ip++;
(*ip)++;
ip = y+2;
++ip;
++*ip;
// il y a encore un print de x, ainsi que du contenu de y
return 0;
}


Même si vous êtes perdu pour l’une ou l’autre question, le prof vous aide afin d’arriver à la réponse1


3. Liste chainée
Implémenter une fonction qui sur base d’un noeud supprime le noeud suivant sans détruire la liste chainée.

4. implémentation de la fonction “ void imprimeListe() const; “
cette fonction imprime l’ensemble des noeuds => bien comprendre comment agit le const, dans quel cas est il primordial ( pas fonctionnel si le const n’est pas présent )

5. écrire la fonction C++ d’insertion en tête de liste d’un nouvel noeud dans une liste chaînée
à quoi sert const après certaines fonction ? empêche la modification des attributs, utile quand une liste est passée en paramètre par référence constante -> seules des fonctions const peuvent êtres utilisée

6. Ecrire une fonction en C++ qui imprime tout le contenu d’une liste chainée. Pourquoi la fonction doit être const? /!\\ utilité et nécessité du mot clef const (NB : si la fonction est pas const, elle ne peut être appelé par des objets const ? Problème)

7. Etant donné la fonction creer_noeud (int data) fournie, implémenter la fonction insérer_noeu d (int data, noeud* tete) pour insérer un noeud en tête dans une liste chainée

Janvier 2019 - Algorithmique - 1 Jan 2021

1. Tas et tas-max:
- Définir ces deux notions. (Pour tas expliquer comment passer d’un élément à l’autre comment c’est stocké en mémoire, quelle opérations il facilite. Pour le tas max donner la propriété qu’il vérifie ainsi que la complexité des opérations)
- Donner l’application principale du tas-max ( queue de priorité)
- On nous donne un tableau, il faut dire si c’est un exemple de tas max (ce n’est évidemment pas le cas), expliquer ce qu’il faut faire si pour le corriger ( et donner la complexité) et l’appliquer à l’exemple.
- Donner la méthode qui permet d’extraire le maximum ainsi que sa complexité et l’appliquer à l’exemple précédent.
- Questions subsidiaires: comment trier avec les tas-max (+ complexité) et expliquer ce que sont structure de donnée et type de données abstraites.

2. Fonction de hachage
- expliquer ce qu’est une fonction de hachage
- Dans quels cas on a des collisions
- Quelles sont les 2 méthodes les plus courantes pour régler ça
- Expliquer l’adressage ouvert et la notion de facteur de charge
- Expliquer l’insertion, la recherche et la suppression dans un adressage ouvert
- (idem mais avec le chaînage)


3. Tri par fusion
expliquer le fonctionnement du tri
l’appliquer à une liste donnée
dire si le tri est en place et stable et justifier
donner la complexité et justifier

4. Borne inférieure pour le Comparaison
Expliquer le principe d’un tri par comparaison
Démontrer que la borne inférieure vaut Omega(n logn)
Donner des exemples d’algorithmes de tri qui vérifie cette borne
Peut-on faire mieux que ca dans certains cas ?

5. Opérations Insert, Search, Delete dans un tableaux trié et dans une liste doublement chaînée non-triée
Il donne le temps pour insert (O(n) pour TT et O(1) pour LDC)
Il demande le temps de search pour le TT ? O(log n) car on peut utiliser la recherche dichotomique
Il demande le temps de delete pour le TT ? O(n) car on doit décaler les éléments de droite après la suppression
Il demande le temps de search pour la LDC ? O(n)
Il demande le temps de delete pour la LDC ? O(1)
A quoi correspondent ces 3 opérations ? à un dictionnaire
Peut-on faire mieux que le TT et la LDC ? Utiliser une table de hachage si on s’intéresse qu’à ces trois opérations ou un arbre AVL si on veut aussi pouvoir trouver le maximum, minimum, predecessor, successor, etc

6. Arbre de récurrence
Il m’a donné un exo comme ceux du tp 7
Donc une recurrence T(n)=3T(n/2) + 1, avec T(1)=1, il fallait donc calculer T(n) qui etait la complexité d’un certain algorithme (c’est un algo de multiplication de deux nombre de n bits)
Il attendait que je fasse la full demo avec l’arbre et tous les calculs de sommation a la fin(exactement comme au tp)
Je devais comparer le resultat obtenu a la complexité de la mutliplication de deux nombre de n bits ( en n carré )
Et puis des petites questions sur la recurrence et l’arbre, genre la hauteur et tt

7. Tri radix
expliquer le principe
stable? En place? (--> dépend de l’algo de tri choisi)
sa complexité (attention savoir expliquer tout dans la formule!!)

8. Tri par insertion
- expliquer comment ça marche
- stable? En place?
- Complexité dans le pire des cas et quel cas ce serait (->tableau trié dans l’ordre inverse)
- Complexité dans le meilleur des cas et quel cas ce serait(->tableau déjà trié)
- analyse de la complexité, doit y avoir le développement qqpart dans le cours me souviens plus mais il est content si tu te souviens de la - - formule pour les suites arithmétiques n*(n-1)/2
- Et puis il a demandé si complexité en n^2 c’était le mieux qu’on pouvait faire
- non -> donne moi un exemple de tri qui fait mieux
- astuce de sa part pour arriver au tri par fusion
- est ce que c’est toujours avantageux de choisir le tri par fusion par rapport au tri par insertion? (-> non parce que le tri par fusion on peut avoir une grande constante devant le n.log(n) du fait que le coût de chaque n.log(n) opérations peut être élever (ex: la copie d’un tableau à l’autre) et donc pour un petit tableau un algo en n^2 avec petit coût peut être avantageux)
- il aide pas mal il est chouette

Programmation - Janvier 2019 - 1 Jan 2021

Insertion dans une liste chaînée en c++. Il donne un code en annexe avec les fichiers .h et .cpp pour noeud et liste. Dans l’insertion, il faut utiliser la méthode SetSuivant du nœud (donnée en annexe), il faut savoir dire pourquoi il faut passer par cette méthode ( c’est parce qu’on a besoin du setter pour modifier les attributs privés de la classe Noeud).

Il peut aussi demander les conséquences si une méthode qui est supposée être const ne l’est pas et dans quel cas on met des objets const.
Fonction supprimeTete() en C++ avec un code en annexe. Réponse dans le tp 2

Fonction imprimer une liste des string contenus dans les nœuds. Expliquer pourquoi elle doit être const (on l’applique à une variable passée par référence, pourquoi est-ce mieux de le faire comme ça plutôt que par variable -> on évite de copier une longue liste).

En C, implémenter une fonction creer_noeud(int data) qui crée un nouveau noeud, lui assigne l’attribut data et renvoie le noeud
Réaliser, de la manière la plus concise possible, la fonction C suivante “void strcat(char* x, char* y)” qui copie la chaîne y à la fin de la chaîne x. Que se passe-t-il si on appelle la fonction avec les paramètres suivants ? “char x[]=“hello”; char y[]=” World”; strcat(x,y)” (réponses sous-question: dépassement de tampon + impossibilité de modifier x ou y car créés comme constantes ---> mémoire statique)

Implémenter la fonction insérer_noeud(string data) en C++ qui crée un nœud et l’insère en début de liste. Voir tp pour la réponse. Ensuite comprendre le code genre pourquoi on fait un “new” et ->setSuivant. Enfin savoir à quoi sert le mot clé “const” et ce qui se passe si on a pas le mot clé const dans la définition d’une fonction.



Il n'y a pas de publications plus anciennes.
Post Views: 13,994