Vous êtes ici : FIL > Portail > Master Info > 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
1 18/01/2019 Histoire La mécanographie
Annulé
2 1/02/2019 Peut-on mesurer l'information ?
3 8/02/2019 Peut-on produire du hasard avec un programme ?
4 15/02/2019 Comment conserver des données ?
Interruption pédagogique
4 1/03/2019
6
7
8
9
10
11
12
Charles Bouillaguet
dernière modification : 14/02/2019 à 19:56:58

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

Travail à faire

Si vous êtes un groupe de n personnes, vous devez rédiger un mémoire d'environ 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

  • 1er fevrier 2019 : les groupes doivent choisir (c.a.d. avoir déclaré leur choix par email)
  • 15 mars 2019 : les groupes doivent avoir remis une première version.
  • 31 mars 2019 : les groupes doivent avoir remis les rapports sur les travaux des autres.
  • 20 mai 2019 : 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. Histoire des "ordinateurs" du Z3 (1941) à 1955 (hardware, "programmation").
  8. Histoire des ordinateurs de 1955 à 1975.
  9. La cryptanalyse de la machine Enigma.
  10. Histoire du traitement automatisé des données dans le secteur bancaire.
  11. Histoire des systèmes de réservation de billets (d'avion, de train, ...).
  12. Histoire du machine learning.

Groupes constitués

Les binomes portent un numéro (arbitraire) :

  1. Zoé Canoen : lambda-calcul, machines de turing, Plankalkül, FLOW-MATIC
  2. Emeline Dieu, Guillaume Lepretre, Thomas Moreau : bases de données
  3. Ellie BEAUPREZ et Marie MONS : machine Enigma
  4. Amandine Watrelos : systèmes de réservation de billets
  5. Camelea Ouarkoub, Allyson Bazir : l'évolution du 7e art grâce à l'informatique
  6. Gautier Kasperek : supercalculateurs
  7. Mohand Outioua : machine learning
  8. Azzedine Ait Elhaj : Turing, Zuse, von Neumann
  9. Sarah Ben Abdesslem, Samson Vasseur : Turing, Zuse, von Neumann
  10. Antoine Perrot, Maxime Catteau, Pierre Tsaplayeu : systèmes de réservation de billets

Rédaction des rapports sur les versions intermédiaires

Chaque personne doit rédiger deux rapports sur deux mémoires d'autres binomes (cf. tableau ci-dessous). Le rapport doit contenir :

  • Un bref résumé (10 lignes...)
  • Une critique détaillée du travail : tel aspect est bien, je trouve tel passage flou, tel autre passage est complètement pipeauté, il manque une explication sur telle chose, il faudrait une image, l'image fournie ne va pas, il y a une incohérence, j'aimerai en savoir plus sur tel aspect...
  • Une synthèse de votre avis (le mémoire reste à la surface des choses, le fond est bien mais la forme est à améliorer, le rapport m'a donné envie d'en savoir plus sur tel truc, le rapport est intéressant, le rapport est ennuyeux, etc.).
  • Ne pas hésiter à relever les fautes d'orthographe ou autres erreurs

L'idéal est d'être critique (relever les défauts éventuels) mais constructif (proposer des solutions ou des idées d'amélioration). Pour ne pas faire des reproches (ou des éloges) gratuits à quelqu'un, il faut justifier son avis.

On peut traiter le mémoire de manière linéaire : écrire son opinion sur chaque paragraphe, dans l'ordre. Ou bien on peut classer ses remarques par thème (d'abord les aspects positifs, puis les parties floues, puis les parties incompréhensibles...)

NomRapport #1Rapport #2rapports rendus ?

le script AMPL qui a affecté les rapports aux personnes et le script Python qui a parsé la sortie... Optimisation effectuée par GLPK (glpsol --math reviews.ampl).

Charles Bouillaguet
dernière modification : 26/11/2018 à 16:24:34

Travail à faire

Il s'agit d'écrire un programme qui résoud l'un des deux problèmes suivants :

Option A

Le programme lira les grammaires (dans des fichiers textes) en Forme de Backus-Naur. Le format de la forme de Backus-Naur est (en forme de Backus-Naur) :

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= '' | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <letter>         ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
 <digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <symbol>         ::=  "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

"L'axiome" (le non-terminal de départ) est le premier qui est défini. L'alphabet est implicitement composé de tous les symboles rencontrés dans la description de la grammaire.

Instances d'exemples :

Instance "challenge" :
  1. Instance challenge 1 (v1.0)

Option B

  • INPUT : un ensemble matrices M0, ..., Mk de taille n * n.
  • OUTPUT : Un produit de ces matrices (avec répétition) qui donne la matrice nulle

Par exemple, si on donne trois matrices A, B et C, et que A*B*B*A = 0, alors il faut renvoyer [0, 1, 1, 0]. Il est garanti qu'un tel produit existe.

Le programme lira les matrices dans un fichier texte au format suivant :

# les lignes qui commencent par # sont des commentaires
# la première ligne contient : [nombre de matrices] [taille des matrices]
2 2
# ensuite viennent les coefficient de la première matrice,
# un coefficient par ligne, la première ligne d'abord. 
# Par exemple la matrice :
#
#	[a b]
#	[c d]
#
# sera représentée par :
# 	a
#	b
#	c
#	d
#
# Voici la première matrice (c'est l'identité) :
1
0
0
1
# la fin d'une matrice est signalée (de manière redondante) 
# par une ligne qui commence par "---".
--------------------------------
# Voici la deuxième matrice :
0
-1
1
0
---------------------------
# Dans ce cas précis, les deux matrices sont immortelles : 
# leur déterminant vaut 1, donc le déterminant de n'importe quel
# produit de ces matrices vaut également 1. Or le déterminant de la matrice
# nulle vaut... zéro.
Instances "challenge" :
  1. Easy v1.0
  2. Medium v1.0
  3. Hard v1.0
  4. Nightmare v1.0

Organisation

Vous pouvez travailler seul ou en binôme.

Le programme peut être écrit dans le langage de votre choix. Par contre, vous devez écrire un programme documenté par la technique de la programation lettrée. Utilisez l'outil noweb (lisez la doc en une page). Les commentaires doivent être du bon niveau de détail. Vous rendrez un fichier noweb, qui doit contenir des directives permettant de compiler (si nécessaire) et d'exécuter le code.

  • 1er mars 2019 : une première version doit être rendue.
  • indeterminé : séance de relecture des travaux.
  • 20 mai 2019 : une deuxième version doit être rendue.
Charles Bouillaguet
dernière modification : 26/11/2018 à 16:24:34

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 : 26/11/2018 à 16:24:34