INF3105 - Automne 2019

• Mots clés: do, delete, return, unsigned, char, while, short, new, switch.
• Identificateurs pour des classes, fonctions ou objets de la bibliothèque standard C/C++ : ofstream, cout, string, sin, cin, sqrt, istream.

int f(int x){return 2;}
string f(int x){return string("allo");}
void f(int x, int y) { }
int main(){
    int a = f(2); // théoriquement, on pourrait déduire.
    string s = f(4); // théoriquement, on pourrait déduire.
    f(3); // serait ambiguë.
    f(2, 4); // correct
}

• f1 : aucun objet perdu.
• f2 : 2 objets Rectangle «perdus».
• f3 : à la ligne 39, en réaffectant le pointeur r (r=new Rectangle[4];), on peut les 2 objets Rectangle alloués par le new à la ligne précédente.
• Donc 4 objets Rectangle.
•  4 Rectangle * 2 Point/Rectangle * 3 int/Point = 24 objets int.
  

Analyse du programme

• Ligne 8 : la boucle while itère tant que l'entrée est valide.
• La variable position indique la position du mot courant dans la phrase. Cette variable est incrémenté de 1 à chaque mot et remise à zéro (0) après chaque point («.»).
• Ligne 14
• La première condition «position<=3» vérifie si on est dans les 3 premiers mots d'une phrase.
• La deuxième condition «++compte[mot]>nbmax» est évaluée si seulement si la première est vérifiée.
• meilleur mémorise le mot le plus fréquent en début de phrase (3 premiers mots).
• nbmax mémorise la fréquent de ce mot;
• k17 compte le nombre de fois que la ligne 17 (et 15-16) est exécutée, c-à-d le nombre de fois qu'on détecte un nouveau mot plus fréquent.

Dans texte 1, ce qui est intéressant à retenir, cest les 3 premiers mots par phrase:
a b c d e f g . b c d e f g h j a . c e g z x y a . c b a k a l d b b b b . d c b a k .

Compte:

• a: 2
• b : 4
• c : 5
• d : 2
• e : 1
• g : 1

Mot le plus fréquent : c.

• Lignes 10-12 : on lira nm mots, dont au moins O(nm).
• Ligne 13 : on aurat n phrases, donc O(n).
• Ligne 14:
• La première condition «position<=3» : O(nm).
• La deuxième condition «++compte[mot]>nbmax» est évaluée 3n fois, donc O(n) fois.
• L'expression «compte[mot]» fait une recherche dans dictionnaire. Chaque recherche coûte O(log k), car il y aura au lieu k mots différents. Donc total de 3n log k ===> O(n log k).
• Réponse : O(nm + n log k).
• Autre façon d'exprimer: O(n (m + log k) ).
  

• O(n+7) : non simplifié; il faut enlever le +7.
• O(n² + 8m) : non simplifié; il faut enlever la constante 8 devant le m.
• O(n² + m): forme la plus simple, car m et n indépendantes.
• O(3n + 2m): non simplifié; il faut enlever les constantes 3 et 2.
• O(n + k) : forme la plus simple, car n et k indépendantes.
• O(n! 2^n) : forme la plus simple (ça aurait été autrement si n! et 2^n avaient été additionnés...).
  

• O(5n²+9n) < O(n³) : VRAI, car n³ croît plus rapidement que n².
• O(3n) > O(2n) : FAUX, car même ordre de grandeur O(n).
• O(2^n) > (n⁵) : VRAI, car 2^n croît plus rapidement que n⁵.
• O(n!) > O(2^n) : VRAI, car n! croît plus rapidement que 2^n.

• Une implémentation naïve de la comparaison consiste à itérer sur l'un des deux arbres, et pour chaque élément rencontré, on le recherche dans l'autre arbre. Cette implémentation a une complexité temporelle de O(n log n) si l'arbre est équilibré, et de O(n²) sinon.
• La «meilleure implémentation possible» consiste à parcourir simultanément les 2 arbres en inordre, tel que présenté en classe.

• h1 ≤ h2 : FAUX. C'est uniquement vrai pour le pire cas, c'est-à-dire que la hauteur maximum de l'arbre RN est plus grande que l'arbre AVL.
• h2 ≤ h1 : FAUX.
  
• h1 ≤ 1.5 log₂ n + 1: VRAI. Dans les notes de cours, la hauteur maximum est plus précisiément définie par 1.44 log₂ (n+2) -0.328. Dans les explications, on simplifiait parfois à 1.44 log₂ n, car la différence devient négligeable lorsque n est grand.
• h2 ≤ 1.5 log₂ n + 1 : FAUX.
• h1 ≤ 2 log₂ n + 1: VRAI. Rappel: h ≤ 2 ⌈log₂(n+1)⌉.
• h2 ≤ 2 log₂ n + 1: VRAI. Rappel: h ≤ 2 ⌈log₂(n+1)⌉.
• n < 2^h1 : VRAI.
• h2 ≥ ⌈log₂(n)⌉ : VRAI.

Supposons que l'entier X soit à la racine. Il faut donc placer (63 - X - 1) entiers à droite et X entiers à gauche. Afin de minimiser l'entier X, il faut mettre le plus d'entiers possibles à droite et le moins possible à gauche. Pour maximiser le nombre de noeuds à droite, on peut alterner les couleurs rouge et noir. Pour minimiser le nombre de noeuds à gauche, il faut éviter autant que possible les noeuds rouge à gauche (idéalement aucun).

Pour placer 64 noeuds, il faut une hauteur d'au moins log₂ (64+1)⌉=7.

Si l'arbre a une hauteur minimale de 7, le sous-arbre de droite doit avoir une hauteur d'au moins 6. Avec une hauteur de 6, on peut placer jusqu'à 2⁶-1=63 noeuds.

Réponse: 7.

• Par définition, un ensemble ne peut pas contenir deux fois le même élément. Le deuxième 4 ne devrait pas avoir d'effet. Donc, l'arbre aura une hauteur de 3.
• Cependant, on peut généraliser la structure d'arbre pour permettre de stocker plusieurs fois des objets équivalents (voir std::multiset). Dans ce cas, l'arbre aurait une hauteur de 4.
• Si on remplace le dernier 4 par un 6, cela donne le cas ci-dessous.