Vous êtes ici : FIL > Portail > Master Informatique > M1S2 > HECI

HECI : Histoire et Epistémologie du Calcul et de l'Informatique

Au menu : la vérité, la justice, le hasard, la conscience, ... et des logiciels du passé.

Responsable

Charles Bouillaguet

Volume horaire

Cette unité est une unité optionnelle du M1S2 du master science - mention informatique.

L'enseignement est organisé sous la forme d'une séance hebdomadaire de 3h durant 12 semaines. Le contenu de cette séance (cours, TD, TP) varie d'une semaine à l'autre.

Crédits

Valider ce cours rapporte 5 ECTS.
Charles Bouillaguet
dernière modification : 03/09/2016 à 16:29:30

Nouveauté 2017

En 2017, une nouveauté sera introduite dans HECI : une série de TPs sur des systèmes d'exploitations des années 1960-1970.

Objectifs

  • Présenter les moments importants de l'histoire de l'informatique.
  • Montrer comment fonctionnaient certains anciens logiciels.
  • Montrer que le développement de l'informatique produit des outils ayant un contenu philosophique intéressant (qu'est-ce que le hasard ?) et pose des problèmes délicats (qu'est-ce que "l'intelligence" artificelle... ou "naturelle" ?).
  • Discuter, d'un point de vue scientifique et technique, quelques "problèmes" posés à la société actuelle par le développement de l'informatique (est-il possible d'interdire le piratage ? Les ordinateurs vont-ils aggraver le chômage ? La "vie privée" est-elle encore possible ?)

Contenu

Vu le nombre et la variété des sujets mentionnés ici, il ne pourra pas s'agir de développements très poussés dans chaque direction, mais plutôt de dresser un panorama d'un certain nombre de questions. De plus, tous les sujets ne seront pas nécessairement abordés.

Histoire des machines à faire des calculs

  • Instruments de calcul anciens.
  • De Pascal à Babbage.
  • La mécanographie.
  • La naissance du calcul électronique, l'Eniac, Turing et Enigma...
  • Apparition des langages de programmation, des OS, du web, etc.

Histoire des idées liées au développement de l'informatique

Des thèmes possibles :
  • Est-ce que les ordinateurs peuvent devenir intelligents ? Discussions autour de l'intelligence artificielle, le test de Turing, les sciences cognitives et le computationnalisme. L'objection de Lucas. Penrose. "L'intelligence artificielle". Que signifient les victoires des ordinateurs sur des êtres humains dans des jeux ?
  • Y a-t-il des calculs impossibles ? La théorie du calcul. Où se situe la limite de ce qui est calculable ? Thèse de Church (équivalence des modèles de calcul), qu'est-ce qu'un ordinateur ? L'indécidabilité et son interpréation. La machine de Turing. La faillite du programme de Hilbert, Gödel (le concept de système formel, l'opposition vrai/démontrable, la notion de modèle, etc.)
  • Qu'est-ce qu'un calcul difficile ? Effectivité et praticabilité. Classes de complexité, notion de faisabilité. Modèles de calcul classique et quantique. Franchissement de la barrière de Turing. Rapports avec la physique.
  • Programmer et démontrer un théorème mathématique, est-ce différent ? Isomorphisme de Curry-Howard. Lambda-calcul, preuves dans des systèmes logiques et programmes correctement typés.
  • Une démonstration faite par ordinateur et trop complexe pour être vérifiée par l'homme est-elle valide ? Réflexion sur la notion de "preuve" et de démonstration automatique. Exemple du théorème des 4 couleurs et de sa preuve assistée par ordinateur. Preuves formelles. Les ordinateurs peuvent-ils mettre les mathématiciens au chômage ?
  • Qu'est-ce que le hasard ? Des machines (déterministes...) peuvent-elles choisir "au hasard" ? Différentes notions, plus ou moins fortes, de hasard. Les fonctions rand() sont-elles "vraiment" aléatoires ? Comment un ordinateur peut vérifier si quelque chose est "aléatoire" ? Comment tester la "qualité" d'un générateur aléatoire ? Hasard et secret, application à la cryptographie.
  • Est-ce que le génome humain contient plus d'information que Wikipedia ? Comment "mesurer" l'information ? Comment peut-on dire qu'une donnée contient beaucoup ou peu d'information ? Y a-t-il des données "simples" et d'autres "complexes" ? La théorie (classique et algorithmique) de l'information et son utilisation en épistémologie (le principe du rasoir d'Occam), en physique (entropie....), en mathématiques (décimales de pi).

Problèmes "sociétaux" liés au développement de l'informatique

  • Est-il possible d'empêcher la copie non-autorisée de films ? Le partage sur internet de tout et n'importe quoi ? Peut-on faire des programmes impossible à pirater ou à "cracker" ? La notion de propriété intellectuelle a-t-elle encore un sens ?
  • Les ordinateurs sont capables d'accomplir des tâches "intellectuelles" de plus en plus sophistiquées (par exemple de battre un champion d'echecs en 1997, de Go en 2008, de Jeopardy en 2011.....). Est-ce qu'un grand nobmre de tâches actuellement accomplies par des êtres humains ne risquent pas d'être effectuées par des machines dans l'avenir ? Cela ne risque-t-il pas d'aggraver le chômage ?
  • L'affaire PRISM a révélé que les agences de renseignements de tous les pays espionnent les communications de tous les citoyens de manière assez étendue. Les grandes entreprises de l'internet vivent en partie grâce aux données qu'elles accumulent sur nous tous. Est-il techniquement possible de partager de plus en plus d'informations en ligne... tout en restant anonyme ?

Bibliographie

A venir...
Charles Bouillaguet
dernière modification : 03/09/2016 à 16:45:08
Séance Thème Cours Remarque
1 20/01/17 Histoire La mécanographie
2 27/01/17 Société Peut-on empêcher le téléchargement illégal ? BONUS : HECI Challenge #1
3 3/02/17 Société Peut-on faire des programmes impossibles à pirater ?.
4 10/02/17 Vérité (NEW) L'informatique bouscule les maths : le théorème des 4 couleurs, partie I (notes, slides)
17/02/17 Relache cette semaine
interruption pédagogique de printemps
5 2/03/17 TP : assistant de preuve en Haskell. Cours : machines de Turing et indécidabilité
6 10/03/17 Prof malade
7 17/03/17 Histoire TP : VM/370. Cours : les ordinateurs de 1960 : IBM 1401 et IBM 7090
8 24/03/17 Données Y a-t-il plus de données dans Wikipédia ou dans votre ADN ?
9 31/03/17 Hasard Peut-on génerer des nombres aléatoires avec une machine déterministe ? Deadline "plan détaillé"
0xa 7/04/17 Données Face à une nature hostile, peut-on sauver nos données ?
interruption pédagogique de printemps
interruption pédagogique de printemps
0xb 27/04/17 Intelligence Qu'est-ce que l'apprentissage ?
0xc à définir Intelligence Jeux de stratégie : la victoire des programmes
Charles Bouillaguet
dernière modification : 06/05/2017 à 09:51:04

L'évaluation s'effectue avec un examen en fin de semestre et le rendu d'un mémoire. Deux notes seront attribuées à chaque étudiant durant le semestre :

  • M : une note sur 20 évaluant un mémoire rendu en fin de semestre
  • EX : une note sur 20 d'un devoir surveillé en fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne pondérée de ces notes :

N = sup(EX, (2EX+M)/3)

Pour la seconde session d'examen, la note M de mémoire est conservée. Seule la note EX d'examen est remplacée par la note obtenue lors de la seconde session.

L'unité acquise apporte 5 ECTS.

Annales

Charles Bouillaguet
dernière modification : 06/05/2017 à 08:54:12
  1. HECI Challenge #1 (closed)
  2. HECI Challenge #2 (closed)
  3. HECI Challenge #3 (closed)
  4. HECI Challenge #4
  5. HECI Challenge #5
  6. HECI Challenge #6

HECI Challenge #1

L'énoncé est disponible ici.

Le jury a constaté que :

  • N. Berveglieri a envoyé a envoyé un mail le samedi 28 janvier, à 01:58 du matin, dans lequel il mettait simultanément en doute l'existence de solutions et sa santé mentale. Dans ce mail, il reconnaissait être sous l'influence de substances certes légales mais qui modifient le fonctionnement du cerveau (café).
  • N. Berveglieri a envoyé par mail une solution correcte de toutes les instances du HECI Challenge #1 le 4 février 2017 à 02:50 du matin.
  • A. Dazemar a envoyé un mail vendredi 10 février à 06:47, prétendant qu'une solution correcte de la 2ème instance était en pièce-jointe. Bien sûr, il n'y avait pas de pièce-jointe. Le mail était accompagné de vagues excuses : son auteur n'aurait pas assez dormi et il ne pouvait donc pas venir en HECI ; il aurait réalisé des programmes peu efficaces qui consomment toute sa RAM, etc.
  • A. Dazemar a envoyé le vendredi 10 février à 06:49 un email contenant une solution correcte de la 2ème instance en pièce-jointe.

Par conséquent, Le jury proclame que :

  • N. Berveglieri a (pleinement) résolu le HECI Challenge #1.
  • A. Dazemar a (très partiellement) résolu le HECI Challenge #1.
  • La consommation excessive de café et le manque de sommeil sont mauvais pour la santé.
  • Le challenge s'est terminé le vendredi 10 février à 08:29 du matin.

HECI Challenge #2 (3/2/2017)

Un code C obfusqué est disponible ici. L'objectif consiste à modifier le programme pour qu'il affiche "HECI 2017"

Le jury a constaté que :

  • A. Dazemar a envoyé a envoyé un mail le lundi 6 février, à 20:09, contenant une version modifiée du code C du challenge. Le code fourni affiche l'image ci-dessous :
    Le nom de l'UE n'est pas en majuscule. L'auteur du mail reconnait de plus n'avoir "pas du tout compris comment fonctionnait le coeur du code" et avoue avoir "jsute (sic) bidouillé la 1ere ligne du main".
  • François Lemaire a envoyé a envoyé un mail le samedi 11 février à 15:42, contenant une version modifiée du code C du challenge. Il prétend avoir résolu le challenge en 2h. Le code fourni affiche l'image ci-dessous :
    L'auteur du mail a réussi pendant au moins 3 minutes à se faire passer pour un étudiant qui suit HECI. La technique principale a consisté à écrire "Bonjour Monsieur" en tête du mail.
  • E. Delbar a envoyé un mail le dimanche 12 février à 19:37, dans lequel il affirme qu'il "n'est pas assez malin". Le mail contient des explications assez détaillées sur le fonctionnement du code obfusqué.
  • M. Eloidi a envoyé un mail le dimanche 12 février à 20:02, dans lequel elle affirme qu'elle n'a "pas non plus compris grand chose dans le code". Le mail prétend que "après maintes (sic) essais" son auteur a réussi à écrire "heci 2017", sans les majuscules.
  • N. Berveglieri a envoyé un mail le lundi 13 février à 18:36, dans lequel il affirme que son complice V. Oudjail et lui on réussi à afficher "heci 2017" (en minuscules) mais que "on galère pour mettre heci en majuscule". L'auteur du mail, comme d'habitude, a remis en question l'existence d'une solution. Il note aussi qu'il n'a pas réussi à afficher la solution, mais "pleins (sic) d'autres conneries".
  • V. Ryckewaert a envoyé un mail laconique le mardi 14 février à 13:52 (pendant le cours CAR). Le code en pièce-jointe affiche "heci 2017" mais en basse qualité (sans reflexions, etc.) :
  • A. Dazémar a encore envoyé un mail le mercredi 15 février à 23:59 contenant un code C qui génère l'image suivante :
    L'auteur indique qu'il a "jsute (sic) trouvé une version commentée du code source sur internet" grace à un certain V. Oudjail et que sa contribution se résume à avoir "suivi les instructions".
  • E. Delbar a encore envoyé un mail jeudi 16 février à 13:39 contenant de nouvelles précisions sur la représentation des caractères dans le code original, ainsi que l'image suivante :
    L'auteur, qui ne fournit PAS de code C, précise que "il y a peut être des erreurs".

Par conséquent, Le jury proclame que :

  • A. Dazemar, F. Lemaire, E. Delbar, M. Eloidi, N. Berveglieri, V. Ryckewaert ont résolu, au moins partiellement, le HECI Challenge #2.
  • F. Lemaire, E. Delbar et A. Dazemar ont pleinement résolu le HECI Challenge #2.
  • Même si on ne comprend rien, on peut quand même progresser.
  • Le challenge est terminé.
Par ailleurs, le jury tient a décerner les distinctions suivantes :
  • Catégorie "Social Engineering" : F. Lemaire
  • Catégorie "Moindre effort" : A. Dazemar ("un travailleur efficace est un fainéant malin" -- dicton populaire)
  • Catégorie "Meilleure compréhension" : E. Delbar
  • Catégorie "Meilleur outsider" : V. Oudjail
  • Catégorie "Moins bonne qualité visuelle" : V. Ryckewaert
  • Catégorie "Doute systématique" : N. Berveglieri
  • Catégorie "Première participation" : M. Eloidi

HECI Challenge #3 (10/2/2017)

Deux fichiers source Haskell sont disponibles ici et . L'objectif consiste à écrire des programmes qui ont des types spécifiés grace à une petite API.

Le challenge est ouvert jusqu'au vendredi 3 mars à 8:29.

Le jury a constaté que :
  • A. Lemba Nsimba a envoyé un mail le mardi 23 février à 20:38, dans lequel il dit qu'il "débute en haskell". Il répond aux questions 4,5,6.
  • A. d'Azémar a envoyé un mail le mardi 1 mars à 22:13, dans lequel il répond à toutes les questions en trichant avec une mauvaise foi parfaitement assumée.
  • E. Delbar a envoyé a envoyé un mail le mercredi 1er mars à 22:07 avec une réponse aux questions 9, 12 et 13. Il dit que le challenge "lui a cassé les pattes" et qu'il "n'a pas le courage d'aller plus loin".
  • T. De-Wyse a envoyé a envoyé un mail laconique le jeudi 2 mars à 21:49 avec une réponse aux questions 9 à 15.
  • A. d'Azémar a envoyé un mail le mardi 2 mars à 23:51, dans lequel il dit qu'il n'a "pas pris le temps de faire quelque chose d'honnête". Il contient une réponse honnête aux questions 9 à 15, puis il commence à tricher avec des opérateurs monadiques. La réponse à la question 20 est correcte, mais il triche pour la 21 et la 22.

Par conséquent, Le jury proclame que :

  • A. Lemba Nsimba, A. d'Azémar, E. Delbar et T. De-Wyse ont partiellement résolu le HECI Challenge #3.
  • Tricher ne paye pas toujours.
  • Le challenge est terminé.
Par ailleurs, le jury tient a décerner les distinctions suivantes :
  • Catégorie "Meilleures tentatives de triche" : A. d'Azémar
  • Catégorie "Meilleure réalisation" : T. De-Wyse
  • Catégorie "Meilleure interprétation" : E. Delbar
  • Catégorie "Meilleur débutant" : A. Lemba Nsimba

HECI Challenge #4 (3/3/2017)

Déterminez la valeur de Foo(4), où Foo(x) := Bar(x,x), Bar(0, n) := n+1, Bar(m, 0) := Bar(m-1, 1) et Bar(m,n) := Bar(m-1, Bar(m, n-1)).

Le challenge est ouvert jusqu'au vendredi 10 mars à 8:29.

Le jury a constaté que :
  • T. De-Wyse a envoyé un mail le dimanche 5 mars à 21:37, dans lequel elle dit qu'elle "ne possède malheureusement pas une machine capable de calculer et d'afficher la valeur de foo(4)". En pièce-jointe, se trouve un programme Python, qui, effectivement, ne peut pas calculer Foo(4). Elle donne également le nom de la fonction en question.
  • M. Eloidi a envoyé un mail le mercredi 8 mars à 00:13, dans lequel elle dit que son " programme en Java avec de la programmation dynamique [...] n'arrivait pas du tout à calculer Foo(4) à cause d'une mémoire insuffisante". Ceci dit, le mail contient la bonne valeur, pompée sur Wikipedia.
  • M. Eloidi a envoyé un mail le mercredi 8 mars à 21:01, dans lequel elle corrige une affirmation erronée de son mail précédent.
  • A. D'Azémar a envoyé un mail le jeudi 9 mars à 01:47 dans lequel il dit que "là, j’avoue que j’ai eu peur [...] Je me suis trompé [...] il est impossible pour un étudiant normal en master 1 de calculer bar(4,4) avec seulement une semaine de travail [...] ce challenge est potentiellement dangereux pour les étudiants qui s'y essaient". Enfin, l'auteur fait preuve de lucidité en écrivant : "On peut d’ailleurs se poser des questions sur les véritables intentions de son créateur". Par ailleurs, le mail contient la valeur de Bar(4,2).

Par conséquent, Le jury proclame que :

  • M. Eloidi a pleinement résolu le HECI Challenge #4.
  • A. D'Azémar et T. De-Wyse ont partiellement résolu le HECI Challenge #4.
  • Parfois, il suffit de lire Wikipédia.
  • Le challenge est terminé.
Par ailleurs, le jury tient a décerner les distinctions suivantes :
  • Catégorie "Réaction rapide" : T. De-Wyse
  • Catégorie "Wikipédia ça déchire" : M. Eloidi
  • Catégorie "J'ai eu très mal" : A. d'Azémar

HECI Challenge #5 (3/3/2017)

Partie 1

Ecrivez, dans le langage de votre choix, un simulateur de machine de Turing (déterministe). Votre simulateur doit prendre en entrée des programmes écrits dans la syntaxe suivante :

  • Chaque ligne doit contenir un tuple de la forme '<current state> <current symbol> <new symbol> <direction> <new state>'.
  • Les noms des états (<current state> et <new state>) peuvent être n'importe quel séquence de chiffres et de lettres, par ex. 10, a, state1. Ils sont sensibles à la casse
  • Les symboles (<current symbol> et <new symbol>) peuvent être n'importe quel caractère, ou bien '_' pour représenter un "blanc". Ils sont sensibles à la casse.
  • <direction> doit être 'l', 'r' ou '*', pour "Gauche" (left), "Droite" (right) ou "ne pas bouger".
  • Tout ce qui suit ';' est du commentaire, et est ignoré.
  • La machine s'arrête quand elle entre dans un état dont le nom commence par 'halt', par ex. halt, halt-accept.
De plus :
  • La machine commence dans le premier état décrit dans le code, et sa tête de lecture est à gauche de la bande.
  • '*' peut être utilisé comme joker pour <current symbol> ou <current state>. Cela correspond à n'importe quel symbole / état.
  • '*' peut également être utilisé pour <new symbol> ou <new state> pour dire "pas de changement".

Partie 2

Ecrivez des programmes pour votre simulateur, accomplissant les tâches suivantes :
  1. Reconnaissance de a^n b^n c^n
  2. Retournement d'une chaine de caractères
  3. Test de bon parenthésage d'une chaine de caractères
  4. Addition de deux nombres codés en binaires
  5. Multiplication de deux nombres codés en binaires
  6. Calcul de la factorielle
  7. Test de primalité
  8. Test de la conjecture de Goldbach
  9. Simulateur de machine de turing
Il n'est pas indispensable que vous programmes soient de complexité optimale.

Le challenge est ouvert jusqu'au vendredi 17 mars à 8:29.

HECI Challenge #6 (5/5/2017)

Lisez les règles du jeu et Améliorez le code fourni.

L'objectif consiste à écrire une stratégie qui puisse se mesurer à la stratégie fournie, avec le même temps de reflexion. Envoyez vos stratégies (code C) par email. Un tournoi sera organisé pour départager les participants.

INDICE n°1 : la stratégie fournie a un gros bug, dont la conséquence est qu'elle joue très mal lorsqu'elle a la possibilité de rejouer.

INDICE n°2 : la fonction d'évaluation fournie est particulièrement naïve.

INDICE n°3 : la stratégie fournie "oublie" de vérifier si la partie s'arrête.

Charles Bouillaguet
dernière modification :

Travail à faire

Si vous êtes un groupe de n personnes, vous devez rédiger un mémoire de 20'000*n signes sur un sujet lié à l'histoire de l'informatique.

A titre indicatif, quand on lit à voix haute, on lit environ 1000 signes par minute.

Les valeurs admissibles de n sont 1, 2, 3 ou 4. À mon avis, la valeur 4 n'est pas la plus facile à gérer pour vous.

Organisation

  • 10 mars 2017 : les groupes doivent choisir (c.a.d. avoir déclaré leur choix par email)
  • 31 mars 2017 : les groupes doivent avoir mis au point (c.a.d. envoyé par email) un plan détaillé (axes, problématique, parties, sous-parties, idées, etc.)
  • 20 mai 2017 : les mémoires doivent être rendus par email.

Sujets possibles

Voici une liste de sujets potentiels. Si vous avez d'autres idées, le responsable est ouvert à toutes vos suggestions.

  1. Les systèmes d'exploitation avant 1975.
  2. lambda-calcul, machines de turing, Plankalkül, FLOW-MATIC, ... : les langages de programmations, des années 1930 jusqu'à 1961.
  3. Histoires des réseaux, de 1945 à TCP/IP.
  4. Le développement des bases de données, de leur naissance à la standardisation de SQL.
  5. La course à la puissance : histoire des supercalculateurs de 1940 à 1990.
  6. Alan Turing, Konrad Zuse, John von Neumann : leurs vies, leurs oeuvres.
  7. L'enseignement de l'informatique à Lille-1, des années 1970 aux années 1990 (cours, hardware, langages, ...).
  8. Histoire des "ordinateurs" du Z3 (1941) à 1955 (hardware, "programmation").
  9. Histoire des ordinateurs de 1955 à 1975.
  10. La cryptanalyse de la machine Enigma.
  11. Histoire du traitement automatisé des données dans le secteur bancaire.
  12. Histoire des système de réservation de billets (d'avion, de train, ...).

Groupes constitués

Si un sujet n'apparaît pas à côté de votre nom, c'est que vous devez m'envoyer un email rapidement

.

Si votre nom n'apparaît pas, c'est que vous devez m'envoyer un email TRÈS rapidement.

  • Alexis Verhaeghe, Thomas Hayaert, Pierre Preuss : systèmes de réservation
  • Maryem Eloidi, Théophile Blavoet : bases de données
  • Douae Mahroug, Hui Su, Nabila Dehouche, Claire Hunter : Lille-1
  • Benjamin Bermont, Mickaël Matuchak : Zuse, Turing, von Neumann
  • Marion Noirbent, Tatiana De-Wyse : Réseaux
  • Edouard Delbar, Matthieu Bellamy, Arthur d'Azémar, Sofiane Kaci : Super-calculateurs
  • Nicolas Berveglieri : super-calculateurs
  • Maxence Brusc, Timothée Laval, Valentin Ryckewaert : Enigma
  • Victor Bourquin : super-calculateur
  • Arnaud Lemba, Safir Talbi, Pierre-Claver Diarra : Bases de données
  • Adrien Béguin : Enigma
Charles Bouillaguet
dernière modification :

Avec quoi peut-on faire des calculs ?

Qu'est-ce qu'une preuve mathématique ?

  • E : un programme dont la vocation est de (tenter de) décider des formules de la logique du premier ordre. Il se classe régulièrement dans les premières places de la Competition organisée par la conférence annuelle sur la démonstration automatique.
  • Robbins Algebras Are Boolean : une page de William McCune qui raconte comment la conjecture vieille de 60 ans a finalement été démontrée par ce programme.
  • La page Wikipedia sur le théorème des 4 couleurs.
  • Un article de "vulgarisation" sur la preuve formelle du théorème des 4 couleurs

Autour de l'indécidabilité

Peut-on empêcher le partage illégal de fichiers ?

Peut-on faire des programmes impossibles à pirater ?

Y a-til plus d'information dans Wikipédia ou bien dans votre ADN ?

Petit guide de survie pour vos données

Un ordinateur peut-il avoir un esprit ?

Un ordinateur peut-il apprendre

  • L'article de 1988 qui montre qu'on peut apprendre des disjonctions en-ligne de manière efficace.
  • L'article de 1984 qui pose le problème de l'apprentissage de manière rigoureuse, et démontre que des classes non-triviales de fonctions booléennes sont apprenables.
Charles Bouillaguet
dernière modification :