UE Informatique Modalités pratiques Objectifs pédagogiques Plan
Contents
1. Programme Extrait du noyau Linux Algorithme crit dans un langage compris par une machine 457f 464c 0101 0001 0000 0000 0000 0000 0002 0003 0001 0000 86a0 0804 0034 0000 7ae8 0000 0000 0000 0034 0020 0007 0028 0021 001e 0006 0000 0034 0000 8034 0804 8034 0804 00e0 0000 00e0 0000 0005 0000 0004 0000 0003 0000 0114 0000 8114 0804 8114 0804 0013 0000 0013 0000 0004 0000 0001 0000 0001 0000 0000 0000 8000 0804 8000 0804 61a5 0000 61a5 0000 0005 0000 RGUEICIG ne RER z SZ z 7 C est illisible n cessit de langages volu s et donc de Destin une machine doit tre correct et inambigu dudar L1ST Informatique L1 ST Informatique fiches perfor es de m tier tisser Linux Windows ce document page WWW Astrolabe Calcul de la position des toiles et des plan tes Objectif faire faire les calculs par une machine Sage Ross http en wikipedia org wiki Astrolabe LIST Informatique L1 ST Informatique 1694 4 op rations pas fabriqu e l poque Blaise Pascal 1642 additions et soustractions L1ST Informatique LIST Informatique Machine diff rences LEIEL Charles Babbage 1830 calcul de polyn mes Herman Hollerith 1890 x Comptage 150 additions s machine lectrique Utilis e pour recensement USA 1890 M y ar iiy SF Fa 3 LIST Informatique L1 ST Informatique Utilis e pour d chiffrer les messages allemand 2e guerr2. 91 a 5 b 29 cl publique a N cl priv e b N Signature lectronique Alice veut envoyer le message M sign Bob pour retrouver a partir de b et N il faut d abord factoriser N on sait que N p X p2 p et p2 premiers s curit en 2005 factorisation d un entier de 663 bits sur un PC factorisation de 256 bits en un jour cl s courantes de RSA 1024 ou 2048 bits L1 ST Informatique L1 ST Informatique Probl me pour RSA Premi re approche Alice code M avec sa cl priv e elle obtient S elle envoie M S Bob Bob d code S avec la cl publique d Alice s il obtient M tout va bien il est s r que l exp diteur est Alice sinon erreur de transmission ou masquarade x x xti xxx On souhaite calculer x pour de grandes valeurs de n n gt 10500 ou bien quivalemment n x IL i 1 Ceci se fait en n 1 multiplications L1ST Informatique L1 ST Informatique Estimation du temps de calcul pour calculer x10 la m thode effectue 1050 1 multiplications Banc d essai SEQUOIA effectue 1016 multiplications par seconde on utilise SEQUOIA 1016 multiplications par seconde Fe n 10 minimum pour RSA i i 1050 10 secondes pas de r sultats au bout de 3 heures 1016 pas de r sultats au bout de 3 jours pour ce calcul pas de r sultats au bout de 3 semaines on sait q
3. est un multiple de 10 il se termine par 0 l avant dernier chiffre de n est 0 si est un multiple de 10 il se termine par 0 le chiffre de poids k de n est 0 exemples 5021 2301 602215 Pour obtenir 35 x 26 il suffit d additionner les lignes o y 0 35 x 26 70 280 560 910 L1ST Informatique L1 ST Informatique Encore plus de r flexion Algorithme de calcul d un produit Comment savoir si y est nul ou pas si nest pair son criture binaire se termine par 0 On calcule dans Z le produit de X et Y R s WE TST si est pair son criture binaire se termine par 0 le chiffre i a mettre Z z ro de poids k de n est 0 i h b si Y 0 c est fini Z contient le r sultat SA ANE c si Y est impair ajouter X Z Il suffit de diviser Y par 2 jusqu arriver 1 d multiplier X par 2 T2 Tv e diviser Y par 2 f reprendre en b Exemple et disposition pratique X 61 Y 37 x Y Z 61 37 0 61 ru 61 Faisabilit pratique cryptographie 244 9 305 488 4 305 976 2 305 1952 1 2257 3904 0 LLST Informatique L1 ST Informatique Codage d un texte Jules C sar Codage d un texte Blaise de Vigen re Principe d calage des lettres code monoalphab tique Principe une cl donne le d calage code polyalphab tique Exemple la cl est INFO ABCDEF GHI JKLMNOPQRSTUVWXYZ GHIJKLMNOPQRSTUVWXYZABCDEF EE ABCDEFGHI
4. passer dans l tat E et d placer la t te Nombres en base 1 base 10 1 2 3 A Ce base 1 dd GG dd il 2 EU D placement de la t te de lecture criture sur le ruban une case droite not ou une case gauche not Notation d une instruction par ex E s gt E s gt Aaii poe Se d placer gauche jusqu trouver une case vide et y mettre un fil Programme de la machine de Turing correspondante Exemple 1 EI o Er Probl me Calculer n 1 le ruban contient initialement n crit en base 1 La t te de lecture est sur le 1 le plus droite Q D placement il gt A D placement PE Si l tat est uua et que la t te de lecture est sur 1 alors se d placer d une case gauche D placement 0 gt EA le Si l tat est uua et que la t te de lecture est sur une case vide alors crire 1 et passer dans l tat ET o EE EM S o EM 0 ET L1ST Informatique L1 ST Informatique il faut ajouter 1 la case courante mA o EMA c est fini Probl me Calculer n 1 le ruban contient initialement n crit en base 10 La t te de lecture est sur le chiffre le plus droite 0 9 0 ET ES HA gt 3 0 EE E2 5 ES ES o ES EM 0 o ma EM LIST Informatique L1 ST Informatique Solution Un
5. sinon E4 R f rences une simulation en ligne http www bitstorm org gameoflife la page Wikipedia Jeu de la Vie v appel de fonction LIST Informatique L1 ST Informatique DEUX 0 valuation M O L de ii Expr iii Expr iv si E amp E alors E3 sinon E4 v appel de fonction On va supposer que la machine de Peano conna t tous les entiers L1ST Informatique L1 ST Informatique machine de Peano exemples de d finitions Programme A ex cution Addition plus_A X Y si Y 0 alors X sinon plus_ACX Y programme algorithme A X X Y 1 1 X 0 plus_A 2 1 si 1 0 alors 2 sinon plus_A 2 1 plus_A 2 1 plus_A 2 0 si 0 0 alors 2 sinon plus_A 2 0 Addition programme A plus_A X Y si Y 0 alors X sinon tplus_A X Y 2 3 CORRECT machine de Peano exemples de d finitions Programme 2 ex cution Addition programme B plus_B X Y si Y 0 alors X sinon plus_B X Y Addition algorithme B X X Y 1 1 plus_B 2 1 si 1 0 alors 2 sinon plus_B 2 1 plus_B 2 1 plus_B 2 2 si 2 0 alors 2 sinon plus_B 2 2 plus_B 2 2 plus_B 2 3 BO
6. JKLMNOPQRSTUVWXYZ gt di Texte cod final NOPQRSTUVWXYZABCDEFGHIJKLM LSI DDF YTB HOC CSX TBG GCC Faiblesse seulement 26 possibilit s LIST Informatique L1ST Informatique Vigen re avantages et inconv nients Cryptographie cl s publiques principe Principe Force incassable si cl et texte de m me longueur one time pad chaque utilisateur a 2 cl s une publique P une priv e p e un message cod avec P doit tre d cod avec p OUI ABC PWL NON BHX un message cod avec p doit tre d cod avec P Faiblesse P difficile obtenir partir de p et inversement facilement cryptanalys pour les cl s courtes utilis es en Avantage prat que i 7 o z Chaque utilisateur doit conna tre probl me de gestion des cl s syst me priv les utilisateurs doivent s entendre sur les cl s sa cl priv e les cl s publiques des autres utilisateurs annuaire L1ST Informatique L1 ST Informatique Cryptographie cl s publiques utilisation Cryptographie cl s publiques RSA Rivest Shamir et Adleman 1977 e un peu d arithm tique on peut trouver des entiers a b N tels que pour tout entier x Envoi d un message si Alice veut envoyer M Bob elle le code avec la cl publique de Bob lorsque Bob re oit le message il le d code avec sa cl priv e 2 x2 x N Par exemple N
7. Modalit s pratiques Planning UE Informatique d but des TD la semaine prochaine 2 s ances de TD par semaine paire 1 s ance de TD par semaine impaire Philippe EZEQUEL la semaine prochaine est une semaine paire Marc BERNARD milie MORVANT Baptiste JEUDY un contr le d but novembre coefficient 5 un contr le la fin du semestre coefficient 4 Contr le des connaissances L1 ST 2013 2014 Universit Jean Monnet Adresses http webperso univ st etienne fr ezequel 1info ezequel univ st etienne fr LIST Informatique L1 ST Informatique de l UE enti re panorama partiel partial et subjectif de l Informatique en tant que science Introduction Calculabilit Conception d algorithmes et de programmes 4 s quences plus ou moins ind pendantes de ma s quence algorithmes et programmes existence conception faisabilit Faisabilit pratique Avertissement Ces transparents sont volontairement incomplets LIST Informatique L1 ST Informatique Algorithmes et programmes algorithmes Algorithme Suite finie d instructions permettant de r soudre un probl me Introduction au d but sont les programmes uv wv uv partition mode d emploi recette de cuisine Q REMEI Destin un lecteur humain ventuellement vague Algorithmes et programmes programmes Un exemple de vrai programme
8. UCLE Addition programme B plus_B X Y si Y 0 alors X sinon plus_B X Y Il LIST Informatique L1 ST Informatique machine de Peano volu e machine de Peano exemples de d finitions Multiplication algorithme X 0 MaL A n X 1 X ii Expr x Y 1 X iii Expr Multiplication programme mult X Y si Y 0 alors 0 sinon si Y 1 alors X sinon iv si E E2 alors E3 sinon E4 v appel de fonction vi A E ob EE plus X mult X Y machine de Peano encore plus volu e Machine de Turing Fonctionnement d une machine de Turing un ruban infini chaque case du ruban peut contenir un symbole lettre chiffre ou tre vide une t te de lecture criture qui pointe sur une case du ruban la t te de lecture criture est dans un tat parmi une liste Ex cute les instructions d un programme tant que cela est d tats possibles possible Variantes machine plusieurs rubans rubans semi infinis L b a 3 L1ST Informatique L1 ST Informatique Programme d une machine de Turing Exemple 1 Probl me Programme d une machine de Turing liste d instructions Calculer n 1 le ruban contient initialement n crit en base 1 La t te de lecture est sur le 1 le plus droite Les instructions sont du type si l tat est E et le symbole sous la t te est s alors remplacer s par 5
9. demander mon mot de passe Si j ex cute ce programme va t il effacer mon disque dur Ce programme est il un virus En fait la plupart des questions int ressantes sur les programmes sont non calculables LIST Informatique Conception d algorithmes et de programmes L1ST Informatique Une lueur d espoir Non calculable ne veut pas dire impossible calculer existence de cas particuliers gt D autres probl mes au moins aussi int ressants sont calculables L1 ST Informatique Mission Concevoir un nouvel algorithme de multiplication de deux entiers utilisant seulement la multiplication par 2 la division par 2 l addition d entiers le test de parit L1 ST Informatique Un peu de r flexion Un peu plus de r flexion n Arithm tique Soient X et Y deux entiers multiplier On a Y Xyz criture binaire d un entier n avec des 0 et des 1 uniquement i 0 Du coup k n m2 S ia n 2 no 2 y n 2 i 0 XxY NE indice i poids du chiffre i 0 Xx Yn2 1 21 yo 2 X Yn X 1 21 X yo 2 5 y X 21 i 0 m 12 1 22 0 2 O Haii AN OZ ET LOUE Fans 2 1 2 0 22 1 21 0 20 1010 Exemple Encore plus de r flexion X 35 Y 26 Y 16 8 2 1 24 1 23 0 2 1 21 0 20 110102 Comment savoir si y est nul ou pas En base 10 si n est un multiple de 10 il se termine par O si
10. e mondiale longueur 5 23 m hauteur 3 26 m poids 1 tonne voltage de 350V 1250V lampes consommation 3500 W horloge 100 kHz 500 instructions par seconde Quelques chiffres Actuellement juin 2013 Tianhe 2 Chine RE Et ve NN consommation 17 MW Ir ail 34 101 instructions par seconde 34 p taflops D il pe P onee L1 ST Informatique L1 ST Informatique Une photo de Baby 1 Une photo de Tianhe 2 LIST Informatique L1 ST Informatique Mod les de calculabilit Automate cellulaire le jeu de la vie D but du XX si cle qu est ce que calculer syst me semi Thue machine de Peano x X calcul de Church algorithmes de Markov damier infini chaque case appel e cellule est soit vivante soit morte e r gles d volution machine de Turing x une cellule vivante entour e de 2 ou 3 cellules vivantes reste vivante sinon elle meurt une cellule morte entour e de 3 cellules vivantes devient vivante sinon elle reste morte machine de von Neumann automate cellulaire de Conway x clauses de Horn Tous quivalents L1ST Informatique L1 ST Informatique Automate cellulaire le jeu de la vie machine de Peano valuateur d expressions arithm tiques Ba ai i m m possibilit de d finir des fonctions i 0 0 ii Expr eval Expr 1 iii Expr eval Expr 1 iv si 1 E alors E3
11. e machine un peu particuli re il faut ajouter 1 la case courante EU o EM c est fini o ES E3 14 pour i 0 1 2 3 4 5 6 7 8 o m 9 E 0 o m RM Cette machine ne s arr te jamais dans certains cas Lesquels EA E i e pour i 0 1 2 3 4 5 6 7 8 HA gt RE 0 o RE ET LIST Informatique L1 ST Informatique En r sum f A ie e Une machine de Turing prend en entr e une suite de symboles Calculabilit nul n est jamais assez fort pour ce sur le ruban calcul Soit la machine s arr te soit elle ne s arr te pas Si elle s arr te r sultat sur le ruban suite de symboles Exemples Entr e n en base 1 sortie n 1 en base 1 Entr e n en base 10 sortie n 1 en base 10 Luc Etienne L Art du contrepet Entr e 2 entiers n et m sortie n m Entr e formule par ex 45 37 x 12 sortie r sultat LIST Informatique L1 ST Informatique Une machine de Turing calcule une fonction Th se de Church Turing Une suite de symbole lt un entier Donc machine de Turing Pour tout algorithme fonction intuitivement calculable il o Entr e un entier existe une machine de Turing qui l impl mente Sortie un entier Pour chacune des machines r elles il existe une machine de e Autrement dit une machine de Turing calc
12. ormatique 50 Temps de calcul de x1 au plus environ 2 log 10 multiplications log gt 10 166 donc au plus 333 multiplications tout n est pas calculable et m me si c est calculable c est peut tre inaccessible si 10 multiplications par seconde calcul effectu en 10 us x 3 6 s 0 333 us Exemple plus r aliste 20 us amp n 10 00 3 3 o A0 ookee pa cond gt un peu de r flexion ne peut pas nuire au plus 3 321 secondes L1ST Informatique L1 ST Informatique
13. ue 1 an 3 107 secondes il faut donc 10 s amp 3 10 ans 3 107 n pour ce calcul Remarque dans la vraie vie n est plut t proche de 10 00 LIST Informatique L1 ST Informatique Une premi re r action La machine est trop lente il en faut une plus rapide Loi de Moore La puissance des machines double tous les Combien de temps doit prendre une multiplication pour que le 18 mois calcul de xt s effectue en un jour soit 105 secondes Une g n ration de machines dure donc 18 mois On doit avoir Au bout de combien de g n rations de machines peut on esp rer faire une multiplication en 1074 seconde 50 10 Peai tmult X 10 10 secondes la k i me g n ration on fait 1016 x 2 multiplications par 16 c est dire seconde et une multiplication prend donc EA seconde Wo i aut 105 10 seconde L1ST Informatique L1 ST Informatique Plus malin Une multiplication se fera donc en 10 seconde la g n ration k tel que 1016 10 45 2k c est dire o 1 X 2 10 i O o c est dire encore xn xxx J xti xxx x x k log 10 97 l E Ceci se fait en au plus environ 2 log n multiplications Une g n ration dure 18 mois 1 5 ans Cette g n ration de machines verrait le jour dans 97 x 1 5 145 5 ans si aucune limite physique n est rencontr e d ici l gt on ne peut pas utiliser RSA LIST Informatique L1 ST Inf
14. ule une fonction de es A N dans N si elle s arr te Turing qui r sout le m me probl me Une machine de Turing lt une fonction f Entr e de la machine n sortie f n L1ST Informatique L1 ST Informatique Fonctions calculables Une fonction f est calculable si il existe une machine de Turing qui calcule f i e Si le ruban de la machine contient initialement un entier n quelconque alors La machine s arr te le ruban contient la fin f n LIST Informatique Un probl me non calculable Probl me de correspondance de Post dominos aligner CR En m E E E E E E 1 2 3 4 5 Question existe t il un alignement des dominos tel qu il y ait la m me chose en haut et en bas les r p titions de dominos sont autoris es L1ST Informatique Fonctions calculables Toutes les fonctions de IN dans IN sont elles calculables y a autant de machines de Turing que de nombres entiers Il y a autant de fonctions de IN dans IN que de nombres r els Il y a strictement plus de r els que d entiers Donc il y a strictement plus de fonctions de IN dans IN que de machines de Turing donc il existe des fonctions non calculables L1ST Informatique Une solution 5 3 1 2 5 CM E E m HE 5 3 1 2 5 Plus clairement CRE n E E EHNE HE L1 ST Informatique D autres probl mes non calculables Ce programme s arr te t il Ce programme va t il me
Download Pdf Manuals
Related Search