cs110.md

CS110

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Fall 2013: Information, Calcul, Communication

[TOC]

Module 1 : information

Calcul et algorithmes

• instructions

  • élémentaire, coût fixe ($delta = b^2-4ac$)
  • non-élémentaire, coût en fonction de n (boucle)

• structures de contrôle

  • branchements conditionnels

  • boucles conditionnelles

  • itérations

• algorithmes

  • entrées / sortie
  • séquentiel / parallèle / réparti

• complexité

  • focus / forget
  • scalable $O(1)$ < $O(log(n))$ < $O(n)$ < $O(n*log(n))$ < $O(n^k)$
  • non-scalable $O(e^n)$ < $O(n!)$

• recherche

  • non-ordonnée $O(n)$
  • dichotomie (ordonnée) $O(log_2(n))$

• tris

  • tri par insertion $O(n^2)$
  • quick sort $O(n*log(n))$ max $O(n^2))$
  • par tas $O(log(n))$

• plus court chemin

  • Floyd (any two stations) $O(n^3)$
  • Dijkstra (one particular station to others) $O(n^2)$
  • Viterbi (two particular station) $O(n)$
  • traveling salesman tour (fastest to visit all stations) $O(n!)$

Stratégies de calcul

• résolution d'algorithmes
  • descendante/ascendante (création de sous-problèmes)
  • diviser pour régner (très souvent récursif)
  • glouton (ne réévalue pas une heuristique calculée)
  • programmation dynamique (apparition du même sous-problème plusieurs fois, enregistrement de la solution)
• Floyd
  • $D(i,j) = \left{ \begin{array}{l l} \text{distance between i&j}\ & \quad \text{if i and j connected}\ infinity & \quad \text{otherwise}\end{array} \right}$
  • $D_k(i,j)=min{d_{k-1}(i,j), d_{k-1}(i,k)+d_{k-1}(k,j)}$

Théorie du calcul

• ensemble infini
  • dénombrable si une function en fait le numérotage (nombre relatif, pair d'entier selon leur somme, etc.)
  • non-dénombrable selon la diagonal, en cas de déplacement des éléments la diagonal ne suit pas le même schéma (ensemble fonctions booléennes, nombre relatif, etc.)
  • grand hôtel de Hilbert, de l'infini par décalage
• paradoxe
  • problème de l'arrêt, pas d'algorithme pour déterminer si un programme va se terminer ou non
  • problème de la longueur minimale de description, pas d'algorithme pour déterminer la longueur minimal d'un programme donné
• classe de complexité
  • $P$ algorithme efficace, généralement $\le O(n^3)$ (recherche, alignement séquences ADN, optimisation réseau entre deux points)
  • $NP$ algorithme non-déterministe, non-résoluble mais vérifiable (coloriage avec trois couleurs, optimisation réseau entier)
  • $P \subseteq NP$
  • vérification probabiliste pour $NP$

Représentation de l'information

• bits
  • suite de 0 ou 1
  • n bits permettent de représenter K éléments $n = \lceil log_2 K \rceil $
• bytes
  • motif binaire de 8 bits
  • $1011_2=110^3+010^2+110^1+110^0=8+2+1=11_{10}$
  • $1.01_2=110^0+010^-1+1*10^-2=1+\frac{1}{2^2}=1+0.25=1.25_{10}$
  • $\begin{array}{c|c c} 11 & 2 & 1\ 5 & 2 & 1\ 2 & 2 & 0\ 1 & 2 & 1\ 0 & 2 & 0\ 0 & 2 & 0\ 0 & 2 & 0\ 0 & 2 & 0\ \end{array}\uparrow 11{10} = 00001011_2$
  • domaine couvert positif $2^{32}$ pour 32 bits
  • attention au dépassement de capacité, si "box" de la retenue $&lt; 2^{31}$
  • généralement 1 bits pour le signe et 7 bits pour la valeur absolue
  • complément à 1, inversion des 0 et 1
  • complément à 2, complément à 1 plus la valeur binaire de 1
  • si un byte/décimal est négatif, il faut prendre complément à 2 pour calculer sa valeur absolue dans le type inverse
  • dépassement de capacité apparait chaque fois qu'on a un nombre positif et un négatif donnant un résultat positif
  • représentation binaire relative est limitée donc génération d'imprécision
• exemples
  • un symbole peut-être codé par 1 à 4 bytes en UFT-8 (mais plus d'information pour la police et l'intensité des pixels)
  • pixel en couleur, 3 bytes d'intensité rouge, vert et bleu

Module 2 : information et communication

Echantillonnage de signaux

• signal est une fonction $ X: \Bbb R^d \to \Bbb R^k$
• sinusoïde pure $ X(t)=asin(2\pi ft+\delta) $
  • amplitude $ a $
  • fréquence $ f=\frac{1}{\text{sec}} $ en hertz Hz
  • déphasage $ \delta $
  • période $ T=\frac{1}{f} $ en sec
  • bande passante $ B = f_\text{max} = \text{max}{f_1,\dotsc,f_n}$ en Hz
• tous signal est une somme de sinusoïdes $ X(t)=a_1sin(2\pi f_1t+\delta_1)+\dotsc+a_nsin(2\pi f_nt+\delta_n) $
  • 20Hz à 20kHz audible
  • 150kHz à 3GHz ondes radio

  • 3GHz micro-onde, radar, infrarouge, lumière visible ($ 10^{14} $)

• Filtres $ X(t) \to \widehat{X}(t) , t \in \Bbb R$
  • passe-bas idéal avec une fréquence de coupure $ f_c $ supprime les hautes fréquences
  • moyenne mobile (passe-bas) $ \widehat{X}(t)=\frac{1}{T} \int^t_{t-T} X(s)ds $ (créé un décalage)
  • $ \widehat{X}(t)=\frac{1}{T} \int^t_{t-T} sin(2\pi fs)ds=\frac{cos(2\pi f(t-T))-cos(2\pi ft)}{2\pi fT} $
  • $ |\widehat{X}(t)|\leq\frac{1}{2\pi fT} $
• Echantillonnage $ X(t), t \in \Bbb R \to X(nT_e), n \in \Bbb Z $
  • $ f_e >2f $ ou $ T_e < \frac{1}{2}T $ sinon effet stroboscopique (perte de donnée)
• Reconstruction
  • $ sinc(t)=\frac{sin(\pi t)}{\pi t} $
  • $ X_I{t}=\sum_{n \in \Bbb Z} X(nT_e)sinc(\frac{t-nT_e}{T_e}) $
  • si la condition d'échantillonnage est respecté, alors tout signal est reconstructible (si et seulement si)
• $ a,b,u,v \in \Bbb R $
  • $ cos(b)-cos(a)=2sin(\frac{a+b}{2})sin(\frac{a-b}{2}) $
  • $ sin(b)-sin(a)=2cos(\frac{a+b}{2})sin(\frac{a-b}{2}) $
  • $ 2sin(u)sin(v)=cos(u-v)-cos(u+v) $
  • $ 2cos(u)sin(v)=sin(u-v)-sin(u+v) $
• périodique si $ \exists T \text{ } x(t_o+T)=x(t_0) $
  • addition même période = même période
  • addition période différente, le rapport $ T_1/T_2 $ doit être rationnel = période est le $ ppcm(T_1,T_2) $

Compression de données

• entropie $ H(X)=p_1 log_2(\frac{1}{p_1})+\dotsc+p_n log_2(\frac{1}{p_n}) $ où $ p_i $ est la probalité d'apparition d'une lettre dans séquence
• plus il y a de répétition , plus l'entropie est faible
• Shannon
  • règle 1 : le nombre de bits attribuées à chaque lettre est égal au nombre de question nécessaire pour la deviner
  • règle 2 : la valeur 1 est attribué si la première question était un oui, sinon 0
  • le code binaire doit être sans préfixe
  • théorème : $ L(C)\geq H(X) $ sinon perte
• longueur moyenne du code binaire $ L(C)=p_1l_1+\dotsc+p_nl_n $ où $ l_i $ est la longueur du code binaire $ c_i $ (ex : 010) pour une lettre donnée

Module 3 : systèmes

Ordinateur à programme enregistré

• algorithme > réécriture formelle > comprehension de la machine > machine > électronique
• assembleur
  • registre r1, r2, ..
  • charge a, b (a=b)
  • somme/soustrait/multiplie a, b, c (a=b*c)
  • continue a (continue à la line a)
  • cont_egal a, b, c (if a=b continue ligne c
  • cont_le0 a, b (if a<=0, continue ligne b)
• processeur
  • unité arithmétique
  • mémoire (banc de registres)
  • pointeur de ligne
  • clock (+1)
  • mémoire pour instruction (encodé en bits)
• transistors
  • n-mos (1=passe, 0=bloque)
  • p-mos (1=bloque, 0=passe) (petit rond sur l'illustration)
  • inverseur (triangle suivi d'un rond)
  • mémoire est un circuit bistable
• amélioration
  • réduire le délais (raccourcir)
  • augmenter le débit (dédoubler)
  • parallélisme des opérations (si detection des dépendances) superscalaire

Hiérarchie des mémoires

• stockage
  • Mémoire, disque dur, flash, grappes (disk array), robot de sauvegarde (tape robot)
  • grand vs petit
  • non-volatile vs volatile
  • non-gourmand vs gourmand
  • lenteur vs vitesse
  • bande passante augmente inversement à la capacité
  • processeur rapide mais petit
  • disque lent mais grand
  • tics unité temporel
  • mot = 4 bytes = 32 bits
  • bloc = 16 à 128 bytes
  • cache afin d'accélérer l'accès aux éléments fréquemment utilisés
  • si pas en cache, défaut de cache
  • localité spatiale (ex: même bloc)
  • localité temporel (ex: plusieurs accès à la suite)
• cache
  • calcul en fonction du cache
  • addition de matrice, pas d'ordre dans les blocs
  • multiplication, meilleur temps de transpose la deuxième matrice

Stockage et réseau d'informations

• stockage
  • stockage = transmission dans le temps
  • communication = transmission dans l'espace
  • données non-structurées vs structurées
  • disque en 2 parties, répertoire des relations structurelles (méta-données) et les données
  • différentes médiathèque
  • séquentielle (par dates)
  • hiérarchique (arborescence)
  • rationnelle (par types/catégories)
  • maillée (relations entre les entités)
  • information a du sens uniquement dans son contexte spatio-temporel
  • procédure : identification, localisation, accès
• réseau
  • protocoles par couche sinon aucune exploitation possible
  • application (but)
  • présentation (langage)
  • session (syntaxe)
  • transport (sonnerie)
  • réseau (n° téléphone)
  • lien (central)
  • physique (ligne téléphonique)
  • encapsulation protocole précédent dans le nouvel encodage
  • internet (dns,http > tls,tcp > ip > CSMA (collisions) > fibres optiques)
  • WAN (wide-area international) / MAN (metropolitan régional) / LAN (local bâtiment) / PAN (personal pupitre)
  • IPv4 32 bits vs IPv6 128 bits
  • chaque noeud connait la longueur des chemins des noeuds voisinants
  • paradigmes réseaux homme-machine vs machine-machine vs homme-homme vs ...

Sécurité de l'information, de la communication et du calcul

• information
  • pas de sécurité total, meilleur est l'éducation
  • facilité avec les maillons faibles (hommes)
  • disponibilité, cryptage, intégrité, authenticité
  • cryptage symétrique (clé secrète, DES, AES) vs asymétrique (clé publique RSA, DH)
  • identité, sphère privée, réputation
• communication
  • bon mot de passe, résiste plus longtemps aux attaques par dictionnaire et brute force
  • authentification à 2 étapes ou double facteur (biométrie)
• calcul
  • droits d'accès R/W/X
• cheval de Troie (pas de propagation, caché), virus (dans logiciel, propage), ver (indépendant, auto-propage)