CPI CM4 CH4 151019 - Cours de CPI L1 Informatique, chapitre 4 Par Pierre Collet PDF

Preview

Summary

Cours de CPI L1 Informatique, chapitre 4
Par Pierre Collet...

Description

CPI Cours 4 CHAPITRE 4 : Les ordis fonctionnants avec l’électricité : 

Représentation des données « binaires » +5V = « 1 » et 0V = «0»

Du coup tout est représenté avec le binaire : des « bits » pour « Binary digITs ». 8bits= 1 octet Hexadecimal ( base 16).4 

Table ASCII : 32 par colonne ( 8 colonnes ) contient 127+0 caractères ( printable characteres) o 65-90 caractères majuscules o 97-122 caractères minuscules o 48 = 0 o 32 = ESPACE

Problème : 256 caractères n’est pas suffisant pour écrire dans toute sles langues. Le codage UTF-8, codage d’un caractère sur 1 à 4 octet(taille variable) compatible avec table ascii. Si le bit de gauche d’un caractère UTF-8 vaut 0 alors c’est un caractère ASCII Si le bit de gauche d’un bit UTF-8 vaut 1 alors c’est un caractère qui tient sur 1 octet. Si les deux premiers bits sont à 1 : codé sur 2 octet ( 3 premiers = 1 alors 3 octet…) Si les deux premiers valent 1 et 0 alors c’est un octet intermédiaire pour rendre le code autosynchronisant.

A. Représentation des données dans les ordis



Représentation en binaire / Octal / hexadécimal 1011(D) = 1*10^3 + 0*10^2+1*10 + 1*10^1 Binaire : 1011(B) = 1*2^3+0*2^2+1*2^1+1*2^0 = 11(D) Octal : 1101(o) = 1*8^3+1*8^2+0*8^1+1*8^0 =

CONNAITRE LES PUISSANCE DE 2 ! 2^5 = 32 2^6=64 2^7 = 128

2^8 = 256 2^9 = 512….

2^32 environ 4 milliards 11(décimale) en binaire = 8+2+1 = 1011(binaire) Binaire -> octal : 2^3=8 ; Ex : 001 011 010 010 100 = 1 3 2 2 4 Binaire -> hexadécimal : 2^4 = 16. Ex : 001 0110 1001 0100 = 1 6 9 4

B. Nombres négatifs en binaires (voir la fiche de BAI avec méthode) Code de Gray: on ne change qu’un bit pour passer d’une valeur à sa voisine. ( 0000,0001,0010,0011…).  Attention il existe plusieurs codes de Gray. La méthode du code de Gray est de prendre un code (type 000) puis pour passer au code suivant de changer le bit le plus à droite et de regarder si ce nouveau code est déjà existant ou non : si oui alors on change le deuxième plus à droite etc. ( méthode classique du codage binaire). Fraction décimale : fraction dont le dénominateur est une puissance de 10 positive.

C. Automates à états finis à REVOIR ! Machine abstraite définie par un quituplet avec : Ensemble fini d’états Alphabet fini Fonction de transition Etat de départ Ensemble d’états acceptants  L’ensemble des états accepté forme la machine abstraite. Exemple de FSM ( final state machine): savoir dessiner le graph de la série d’état (voir powerpoint) : on commence en q0 et on suit les chemins. Le code est accepté si l’état de sortie est dans les états acceptants.

Langage reconnus par les FSM : Les états représentent la mémoire de la machine. PB : une fois la machine définie, on ne peut plus ajouter, modifier ou supprimer d’états. Ceci limite la puissance de la machine. Théorème de Kleene : les langages reconnus par les automates finis sont exactement les langages pouvant être décrits par les expressions régulières.

Les FSM sont beaucoup utilisées en informatique. Machine à état fini qui reconnait trois 0

D. Machine de TURING Machien conçue entre 1930 et 133pour décider de la calculabitité de tout nb réel. Turing a donc mis au point la représentation d’une machine capable d’implémenter un algorithme précis. Puis il a montré qu’a l’aide de la représentation élaborée on pouvait décrire une machine implémentant un autre machine de turing

Intérêt d’une MT par rapport à une FSM

Ce qui empêche les FSM d’accepter autre chose que des entrées définies par une expression régulière, c’est entre autres qu’ils sont figés. Il faut donner aux fsm un calepin modifiable et les moyens de modifier le contenu du calepin Turing imagine un ruban de longueur infinie et un dispositif de modification des informations avec un caractère blanc.

Un caractère de contrôle c’est un caractère non imprimable, un point de code (nombre) dans un jeu de caractères, qui ne représente pas de symbole écrit. Ils sont utilisés comme signalisation intra-bande pour provoquer des effets autres que l'ajout d'un symbole au texte. Une MT se définie par un 7 uplet ( voir poly ). A l’examen il faudra pouvoir écrire le programme de la machine de Turing. En base 1 : un bâton vaut 0 et donc II vaut 1. Conclusion sur les MT Utilisation comme calculateur universel Utilisation comme accepteur universelle....