1. Calculabilité
2. Complexité
3. Algorithmes simples
4. Programmation
5. Vaste domaine scientifique
6. Organisation des cours
7. Contenu du Tronc Commun

• le jeu 1 peut ne pas terminer
• le jeu 2 termine toujours
• la terminaison du jeu 3 est un problème ouvert

Un ensemble		Paver un carré
de p = 4 motifs		de taille n = 6
(carrés à bords colorés)

4096 solutions

3 solutions

• Données: p motifs et un carré de taille n.
  
  
• Algorithme: énumérer les pⁿ² pavages possibles et ne garder que les pavages licites.
  
  
• Complexité: O(pⁿ²)

• Données: p motifs
  
  
• Problème: paver tout le plan

• Données: p motifs
  
  
• Problème: paver les carrés de taille n pour tout n ³ 0

• problèmes indécidables
• problèmes décidables de complexité élevée

• problèmes ou sous-cas de faible complexité algorithmique,
  typiquement en O(n^a) avec a £ 3
  
  
• suffisant pour construire les cathédrales informatiques des années 2000

• tri
• recherche en table
• gestion d'une file de priorité
• analyse syntaxique
• évaluation des expressions arithmétiques
• marche du cavalier sur un échiquier (algorithme glouton)
• parcours en profondeur d'abord (connexité dans un graphe)
• recherche du plus court chemin dans un graphe
• etc.

• exécution par une machine Þ précision supplémentaire
  
  
• complexité dans l'organisation des programmes et des données Þ modularité
  
  
• catalogue de méthodes de programmation bien connues
  qui s'apprennent
  
  
• choix important du langage de programmation

static void copie (char[] s, int s_pos, char[] d, int d_pos, 
                   int longueur) {

  for (int i = 0; i < longueur; ++i)
    d [d_pos + i] = s [s_pos + i];
}

static void copie (char[] s, int s_pos, char[] d, int d_pos, 
                   int longueur) {
  if ( s != d || d_pos <= s_pos) 
    for (int i = 0; i < longueur; ++i)
      d [d_pos + i] = s [s_pos + i];
  else
    for (int i = longueur - 1; i >= 0; --i)
      d [d_pos + i] = s [s_pos + i];
}

static String paques (int y){         y = 11571
    int g = (y % 19) + 1;             g = 1
    int c = y / 100 + 1;              c = 116
    int x = 3 * c / 4 - 12;           x = 75
    int z = (8 * c + 5) / 25 - 5;     z = 32
    int d = 5 * y / 4 - x - 10;       d = 14378
    int e = (11 * g + 20 + z - x) % 30;      e = -12
    if ( e == 25 && g > 11 || e == 24 )  
        ++e;                           
    int n = 44 - e;                    n = 56
    if (n < 21)                        
        n = n + 30;                    
    int j = n + 7 - ((d + n) % 7);     j = 63
    if (j > 31)                        
        return (j - 31) + " avril";    32 avril
    else
        return j + " mars";
  }

• Ariane 501: dépassement de capacité dans le système de guidage par inertie en convertissant un flottant 64 bits en entier 16 bits Þ exception processeur Þ traitement de l'exception en basculant sur le processeur de secours Þ arrêt puisque ce processeur exécutait le même programme qui avait lui aussi fait la même exception.
  
  
• Coût: 10⁹FF
  
  
• Leçon: ne pas penser qu'aux erreurs matérielles.
  Le logiciel peut aussi être erronné.

• certification des programmes
  
  
• logique mathématique et preuves mécaniques
  
  
• systèmes d'exploitation
  
  
• architecture des processeurs et ordinateurs
  
  
• compilation
  
  
• CAO de circuits
  
  
• technologie (semi-conducteurs, physique quantique)
  
  
• réseaux
  
  
• protocoles et sécurité
  
  
• bases de données distribuées (Web)
  
  
• traitement et synthèse d'images
  
  
• etc.

• Transports/Espace
• Médecine
• Biologie
• Télécommunications
• Monétique
• Environnement/Météo
• Cinéma/Multimédia
• Productique/Robotique
• Documentation/Enseignement
• Jeux
• Impact sur l'économie (start-ups)
• etc.

• charger de nouveaux services (banques multiples, carte téléphone, carte médicale, programmes de fidélisation, etc)
  
  
• programmation des services dans un langage de haut niveau

• puissance de calcul dans un téléphone mobile est de 40 MFlops (opérations flottantes par seconde)
  
  
• 600 Gbits/sec passent sur un fil sans répéteur sur 10000km

• Processeur à 750 MHz, 10M transistors, (» 1300 × Vax)
• RAM 128 Mbits, 133 MHz
• Disques 2.5" à 18GO, 3.5" à 20GO (1 kF)
• Réseaux ATM à 640 M bits/sec
• Internet avec 80 M machines

• F9 = 2 ⁵¹² + 1 =
  1340780792994259709957402499820584612747936582059239337772356144372176
  4030073546976801874298166903427690031858186486050853753882811946569946
  433649006084097 = 2424833 × 7455602825647884208337395736200454918783366342657 ×
  7416400626275308015247871419019374740599407810975190239058213161444157
  59504705008092818711693940737 [Manasse, Lenstra] en 1990.
  
  
• RSA-155 = 1094173864157052742180970732204035761200373294544920599091384213147634
  9984288934784717997257891267332497625752899781833797076537244027146743
  531593354333897 =
  1026395928297411057720541965739916759007165678080380668033419335217907
  11307779 × 106603488380168454820927220360012878679207958575989291
  522270608237193062808643 (35 ans de machine de 400 MHz avec 300 machines en 7 mois) [Lenstra, Odlysko, ...Morain] en 1999.
  
  
• ECC2K-108. Soient P et Q deux points sur une courbe elliptique munie d'une opération Ä formant un groupe de ~ 2¹⁰⁸ éléments. Trouver n tel que Pⁿ = Q.
  Réponse:
  n = 47455661896223045299748316018941 mod 324518553658426701487448656461467 (500 ans de machine de 450 MHz avec 9500 machines de 40 pays en 5 mois) [Harley et al] en 2000.
  
• ...à l'écoute des extra terrestres (projet SETI)

• Futurs ingénieurs doivent connaître l'informatique
• Former de bons informaticiens (vs ENS, ETH, MIT)
  
  
• Recherche en informatique en plein essor
  
  
• Mathématiques Þ rigueur Þ atout en informatique
  (vrai en général)
  
  
• Formation initiale très hétérogène des élèves
  (dramatique)
  
  
• L'environnement informatique de l'X est bon. Il faut s'en servir.
  
  
• Format du cours demande un peu de travail personnel
  (beaucoup moins que les 15h/semaine de cours analogues)

Tronc Commun: algorithmes et programmation
Lévy   (projet informatique Gonthier)

Voie C: optimisation combinatoire
Steyaert

Majeure 1: mathématiques et informatique
Steyaert
automates et calculabilité, architecture [Vuillemin],
algèbre Ú bases de donnée Ú lang. de programmation,
1 cours au choix   (automates, vision, objets, ...)

Majeure 2: informatique
Cori et Toueg
systèmes et réseaux, complexité,
algorithmes distribués Ú compilation,
1 cours au choix   (crypto, synthèse d'images, ...)

• 2.5 travaux dirigés d'initiation
• 10 petites classes + 10 travaux dirigés
• contrôle hors-classement, 2h;
  composition de classement, 4h,
  Coefficient 10. Théorique.
• projets de programmation,
  ~1000 lignes de Java (en binôme)
  20 sujets différents de difficultés variées,
  Coefficient 8. Pratique, travail personnel.

• Ecole polytechnique: 1 professeur, 10 maîtres de conférences, 11 chefs de travaux pratiques, 11 vacataires, 1 secrétaire.
  
  
• Cours: 4 prof. univ., 5 DR, 1 CR, 1 ingénieur Mines
  
  
• TD: 6 CR, 3 MdC, 1 ingénieur Mines, 10 thésards.
  
  
• les enseignants sur poste sont tous des chercheurs reconnus.

• Climat de confiance. Très difficile à 460 (900) élèves.
  
  
• Impression (» 10-20 centimes la page). Ne pas faire des impressions inutiles. Utiliser les photocopieuses.

Java, [Gosling et Sun microsystems]
langage typé + garbage collector

This document was translated from L^AT_EX by H^EV^EA.