Buggy3

Clafoutis

Compression

Il existe divers algorithmes de compression de données pour storage qui cherchent

une réduction en volume; certains sont dits lossy, c’est-à-dire impliquent une perte

de fidélité des données, tandis que d’autres ne le sont pas, donc rendent une image

identique à celle d’origine à la décompression. Qu’en est-il?

La notion de lossy prend tout son sens en référence à l’analogique: un morceau de musique, 

une vidéo, peuvent être enregistrés dans des formats bien assez bons, par

exemple un MP3. On reconnaît tout de même de quoi il s’agit. À l’ère du numérique,

on a affaire à du sans perte, car c’est inhérent à la notion. La compression lossless

exploite le fait qu’il y a des répétitions dans les données, des structures. Une plage

de données totalement aléatoire ne saurait être compressée.

Réduites comment? Prenons l’exemple de l’expédition d’un message FAX. À

la inième ligne, il n’y a rien, donc 1 000 blancs. L’envoyeur ne codera pas pour

les mille, mais indiquera en trois temps qu’il s’agit d’une compression, quil y en a mille, 

et que c’est un blanc. Économie réussie.

L’algorithme de Lempel -Ziv, datant de 1977, repose sur l’idée géniale de compressé

par rapport à un dictionnaire unique à chaque document, qui se décompresse par

les mêmes règles; donc, pas besoin d’expédier le dictionnaire à celui qui décompresse.

Dès qu’un caractère répète, il apparaît comme entrée au dico. Plus la compression avance, 

plus il y a d’économies. (Le produit LZ le plus connu  sera la compression

Zip. Il y a aussi Gzip (Gunzip à la décompression)).

En forme Lempel-Ziv-Welch - les caratères d’origines sont donnés - cet algorithme

fait des adeptes. On s’en sert pour la compression des fichiers GIF, mais sans savoir

que l’algoritheme lui-même faisait l’objet d’un copyright. Ce füt un moment difficile

pour l’évolution du Web, résolu maintenant parce que le copyright s’est épuisé en

2003.

Il existe d’autres algorithmes, bien sür. Les différences font souvent sur  à quel moment,

même a posteriori, déclarer un membre du dico.  C’est à explorer.

https://www.grc.com/sn/sn-205.pdf

Buggy2

 

Voici pour l'exercice buggy2, que j'ai ouvert à partir de John Harvard. Pas terrible, le programme. En fait, il n'y a qu'une issue: Boom. La main produit un chiffre aléatoir modulo3, donc 0, 1 ou 2 et

en commençant par binky, on se renvoit jusqu'à satisfaction.

 

Le programme ne s'exécute pas sans heurt. Si je le demande à l'intérieur de GBD, c'est bien une

erreur de segmentation qui se déclare à la ligne 6 ie une lecture en mémoire impossible. Je

recommence et demande un backtrack; et oui. Tout se déroule comme prévu jusqu'au line 6 fatidique.

On ne demande pas une correction, mais la version suivante s'exécute normalement..

 

 



Correcteur

Au Pset4, on nous demande - pour s'échauffer avant d"entreprendre le veritable défi - de se
familiariser avec le correcteur Gnu DGB (debugger). Ce dernier facilite les choses pour
un certain nombre de languages, dont le C et le C++, etg nous permet de voir la valeur
que porte nos variables à toutes les étapes du programme.

Buggy1, le premier programme, ne s'ouvre pas normalement; il faut se servir de gdb pour
en voir le contenu. On execute gdb et ce dernier se présente entre parenthèses, prêt à
l'emploi. On écrit ensuite break main pour s'arrêter au main lors de l'exécution.
On demande son programme qui s'arrête sur main; n return nous fait advancer d'une ligne;
p variable nous permet de voir la valeur d'une variable à tout moment.

Et voilà donc notre Buggy1, qui a besoin d'un argument passé en command-line pour fonctionner:
il s'agit de comparer notre phrase avec CS 50 rocks! On peut aussi nettoyer le printf du else...

Je l'avoue, j'ai beaucoup cherché le problème de ce petit programme qui donnait des A à tout!!
Et puis je me sui souvenue que chaque mot d'un argv forme un string en tant que tel:

Reste à faire travailler GDB.

 

Mémoire

En ce qui a trait à la mémoire au sein de l'ordinateur, rien de bien magique. Si
un ordi code pour la mémoire en 32 bits, on dispose au max de 1 milliard
de blocs avec un ordi de 4 Gigs de RAM, un portable actuel. Pour plus, Windows 8.1
code en 64 bits et peut dénombrer à la limite du RAM dont on dispose.

Sous UNIX, il faut réclamer la mémoire du HEAP à l'intérieur du programme: question
de simple politesse. Les chiffres à l'intérieur d'une function s'effacent dès que l'on quitte la function.
Pas vrai pour les char* (i.e. les strings),les structs définis globalement.... Il faut donner la permission à l'ordi de se servir dudit espace à d'autres fins.

Car c'est bien  d'un overwrite dont il est question. Un ordi n'efface jamais rien, il écrit
par-dessus. Et si on crée des variables sans les initialiser, on risqué d'avoir de très mauvaises
surprises à l'ouverture de notre programme.

Il convient aussi de se souvenir que l'ordi alloue une adresse simplement en indiquant
le premier bit de l'espace mémoire. Il lit ensuite jusqu'à la rencontre d'un NULL pour savoir que c'est terminé.

Ci-bas, j'ai un petit programme bien sage qui convertit la température Celsius en Fahrenheit.
Mais je n'ai pas donné de valeur initiale à mes variables. Je suis chanceuse, le debugger GDB
m'apprend que la valeur par défaut est zéro, signe que c'est un espace mémoire tout propre.
Cela aurait pû être bien different!!

 

Pour myCity défini à l'intérieur de main:

Pour myCity défini globalement:

 

J'ai créé une fuite de mémoire (memory leak)!!

 

 

Swaping

Encryption

Ça me chicotte passablement de ne pas avoir travaillé le pset2 hacker, developper

une attaque sur les mots de passe (fictifs) de l’équipe cs50. On nous apprend qu’ils s

ont tous le fruit de la fonction encryption que l’on retrouve sous Unix, à l’usage

léger des universitaires. La formule est ‘salted’; on ajoute deux caractères au 

mot fourni par l’utilisateur et comme c’est deux sur une liste, et qui peuvent apparaître 

n’importe où dans les 13 caractères de l’encoding, cela ajoute considérablement 

de difficulté à l’apprenti-hacker.

Quelle information pouvons-nous tirer de cette donne? En réfléchissant un peu, il est

bien évident que l’on a tout de même affaire à une véritable encryption: le même mot de

passe doit fournir le même code, sinon l’exercice n’aurait pas d’utilité. L’alternative serait de 

garder une liste des mots de passe et de leur encoding, genre 

Garfield lasagne xxo%86Aptri!k, pas génial car hacker la liste serait passablement

plus simple.

On parle parfois de encoding à sens unique: le codeur lui-même ne saurait retrouver

un mot de passe perdu, on ne peut qu’en fournir un nouveau. Dans ce cas,

il faut que l’impossibilité soit pratique - trop dispendieux en temps ou ressources -

sinon on fabule dans le monde des listes. J’ai d’ailleurs parfois l’impression que les

codes-clients extrêmement longs, par exemple pour accéder à un logiciel chez

Msoft, seront sûrement des listes. Sinon, la production du code devra être optimisée

et la longueur serait une leurre pour faire peur aux pauvres hackers. Et la beauté

d’une encryption, est qu’elle doit bien s’orienter en fonction de ce que l’utilisateur

fourni: une premeir Garfield déclenche une séquence, et un premier Odie en déclenche

une autre.

Tout ça pour conclure que c’est bien une fonction de ressources et d’ingéniosité pour

le hacker: il y a moyen!!

Et maintenant pour la blague, de l’article sur la NSA de Wikipédia. Un haut-fonctionnaire

aurait fait la remarque que la NSA était l’employeur du plus grand nombre d’introvertis

des E.U. Pas mal!

Any Sort

Autre petit exercice de pratique de la Week3, ajouter un algorithme de tri au programme

suivant. J'ai choisi bubble sort - que j'ai trouvé sur le Net - et ça baigne! La formulation

est classique: pour tous les membres de l'array, avec leurs voisins de droite, échanger si

le nombre est plus élevé que le voisin...

Au pire, un bubble sort devra faire n passes (s'il y a inversion totale). Sinon, il

accroche à la première anomalie et fait  des paires pour le reste jusqu'à la prochaine

passe.

L'insertion sort aurait procédé différamment: comme quand on reçoit des cartes à jouer.

On les met à leur place au fur et à mesure.

Le selection sort remplit les cases comme dans une course: on choisit numéro 1, puis numéro2.

À remarquer, l'utilisation de temp, une variable temporaire. Nécessaire car si on échange

a et b, et ensuite b et a, on se ramasse avec b, b!!

Petit Prob

Petit exercice proposé à la semaine 3: compléter le programme ci-bas en définissant un algorithme

de binary search pour la fonction search. On s'en souviendra, le binary search consiste à

couper par deux le nombre de chiffres de l'array. C'est plus grand ou plus petit, à l'instar

du jeu d'enfant...

Hélas, c'est u  peu plus compliqué que le jeu d,enfant. Voici le pseudo-code  d'un binary search:                                            

Le Web à la rescousse. Voici la solution que cs50 propose en ligne:

 

Donc voici l'astuce: on passe outre au placotage sur Min et Max et on se sert tout simplement
des notions mathématiques se upper et lower bound, qui évoluent au gré de l'algorithme. Ce
qui motorise le tout: while notre chiffre reste à l'intérieur de la borne, ce qui oblige le programme à tourner en boucle. Élégant!

DEBUG

Conditional

Define

Le tri

 

 

 

 

http://www.sorting-algorithms.com/

Cent - mille mots!

Notre dictionnaire actuel fonctionne adéquatement, mais il peut être lent En fait, la banque
des mots est parcourue en entier à chaque demande: pas tellement efficace.

On peut court-circuité tout ça grâce au binary search. Cela fonctionne comme suit:

L'exemple classique est le jeu de devinette-enfant. Je choisis un chiffre de 1 à 100 que l'autre doit deviner; à chaque essai, je lui dis s'il se trouve trop haut ou trop bas. D'un point de vue
strictement mathématique, le joueur devient plus efficace s'il procède par tranches de division
par 2.

Le dico s'améliore s'il consulte des lattes de mots qui rétrécissent  de facteur 2 à chaque tour.
On amende aussi la reconnaissance des mots par la précédence lexicographique; le programme
revoit chaque lettre d'un mot, et peut nous informer mi-mot si on est rendu trop loin.

En gardant la forme du dico tel quel, on échange areEqual pour compareStrings et on embarque
une nouvelle fonction lookup.

En comparant dico et search, si dico a une valeur moindre (qui veut dire vient avant), cela
renvoit -1. Égalité renvoit 0, et valeur plus (vient après) 1. Quand low est plus grand que high (on a tout épuisé), le mot ne figure pas.

Sur une banque de 100 000 mots, le gain de performance devient nécessaire.

DicoDico