CS251 : Les grandes idées de l’informatique théorique

 (cs251.com)
34 points par GN⁺ 2024-03-17 | 2 commentaires | Partager sur WhatsApp
  • Le cours CS251 de CMU porte sur l’étude rigoureuse du calcul, un élément fondamental de l’univers, de la société, des nouvelles technologies et de notre esprit qui cherche à les comprendre.
  • Il est important de disposer d’un langage et d’outils adaptés pour étudier le calcul.
  • Ce cours explore les résultats et les questions centrales concernant la nature du calcul.

Formalisation du calcul

Module 1 : Introduction

  • L’objectif principal est d’expliquer à haut niveau ce qu’est l’informatique théorique et de poser le contexte nécessaire pour la suite.
  • Le cours commence par la manière de représenter formellement les données et de définir formellement la notion de problème de calcul.

Module 2 : Automates finis

  • L’objectif est d’introduire les automates finis déterministes (DFA), un modèle de calcul simple et limité.
  • Les DFA sont intéressants en eux-mêmes et ont des applications utiles, mais ils servent aussi de première étape vers une définition formelle de la notion d’algorithme.

Module 3 : Formalisation du calcul

  • L’objectif principal est d’introduire la définition de la machine de Turing, le modèle mathématique standard de tout type de dispositif de calcul.
  • L’étude rigoureuse des machines de Turing apporte des éclairages non seulement sur ce qu’un ordinateur portable peut faire, mais aussi sur ce que l’univers peut ou ne peut pas faire du point de vue computationnel.

Module 4 : Limites du calcul

  • Le cours démontre que la plupart des problèmes sont indécidables et présente des exemples concrets de problèmes indécidables.
  • Deux techniques clés sont utilisées : la diagonalisation et la réduction.

Module 5 : Limites du raisonnement humain

  • Il a été nécessaire de formaliser mathématiquement le raisonnement mathématique, ce qui impliquait de formaliser « l’algorithme » ou le « calcul ».
  • Le langage de l’informatique théorique permet d’apporter efficacement des réponses à des questions importantes sur les fondements des mathématiques.

Complexité du calcul

Module 6 : Complexité temporelle

  • De nombreux problèmes sont en réalité décidables, mais si l’algorithme le plus efficace exige un très grand nombre d’étapes de calcul, alors le problème devient pratiquement indécidable.
  • Le cours étudie la complexité computationnelle selon diverses ressources, dont la complexité temporelle, avec un accent particulier sur cette dernière.

Module 7 : Théorie des graphes

  • Les graphes jouent un rôle très fondamental dans l’abstraction des problèmes de calcul qui apparaissent en informatique.
  • La vaste littérature sur la théorie des graphes permet de mieux comprendre la complexité computationnelle des problèmes sur les graphes.

Module 8 : P contre NP

  • Le cours introduit la classe de complexité NP et discute du problème P contre NP, le plus important problème ouvert de l’informatique.
  • Si l’on pouvait décider en temps polynomial de nombreux langages naturels et bien étudiés appartenant à NP, des applications remarquables deviendraient possibles.

Module 9 : Algorithmes aléatoires

  • Le hasard est un concept et un outil essentiels pour modéliser et analyser la nature.
  • Les algorithmes aléatoires sont des algorithmes qui ont accès à une source d’aléa, comme un générateur de nombres aléatoires, et peuvent se tromper avec une probabilité d’erreur extrêmement faible.

Module 10 : Cryptographie

  • Le domaine de la cryptographie a commencé à prospérer fortement avec la révolution informatique.
  • L’étude de la complexité computationnelle a entièrement transformé la cryptographie.

Temps forts de l’informatique théorique

Module 11 : Sujets supplémentaires

  • Présentation d’une sélection de temps forts de l’informatique théorique.

Avis de GN⁺

  • Ce cours offre une compréhension approfondie des aspects théoriques de l’informatique et permet aux étudiants d’explorer la nature du calcul tout en étudiant des sujets importants comme la théorie de la complexité et la cryptographie.
  • En particulier, les discussions autour de problèmes ouverts comme P contre NP donnent aux étudiants un aperçu des recherches menées à la frontière de l’informatique.
  • Ce cours joue un rôle important dans la consolidation des bases de l’informatique et fournit les connaissances indispensables pour devenir un ingénieur logiciel doté d’un solide bagage théorique.
  • Le module sur la cryptographie souligne l’importance de la sécurité des données et de la protection de la vie privée dans la société moderne, tout en posant les bases pour devenir un expert du domaine.
  • Ce cours est très précieux en ce qu’il aide les étudiants qui souhaitent faire carrière en informatique à acquérir le bagage théorique et les compétences de résolution de problèmes indispensables.

À lire aussi

2 commentaires

 
quack337 2024-03-19

Ah... ça me rappelle quand, à l'université, je m'arrachais les cheveux tellement j'en bavais.
Je ne comprendrai sans doute toujours pas, mais je vais quand même essayer d'écouter sérieusement.
 
GN⁺ 2024-03-17

Avis Hacker News

  • Ce cours présente divers concepts et met particulièrement l’accent sur l’amélioration de la capacité à résoudre des problèmes.

    • La méthode du cours consiste à ne fournir aux étudiants, chaque semaine, que les définitions de base d’un nouveau sujet, puis à leur demander de résoudre des problèmes qu’ils ne seraient normalement capables d’aborder qu’à la troisième semaine d’un cours spécialisé sur ce sujet.
    • Cette approche est appliquée de manière répétée et peut être très frustrante, mais c’est intentionnel.
    • En essayant constamment de résoudre des problèmes difficiles d’accès, on développe de meilleures stratégies de réflexion face à un problème donné.

  • L’informatique théorique peut être amusante, mais elle peut aussi parfois être extrêmement agaçante.

  • J’ai vu sur Reddit un message demandant comment résoudre un problème d’informatique théorique, et il s’est avéré qu’il s’agissait d’une tentative de tricher sur un devoir de COMS 331 (Theory of Computing) à l’Université d’État de l’Iowa.

    • Personne n’a aidé, et l’auteur a supprimé son message.
    • Le problème avait l’air intéressant, alors je l’ai tenté comme un petit défi amusant pour un moment.
    • J’étais diplômé en mathématiques et j’avais suivi tous les cours de premier cycle en informatique théorique ; environ 35 ans plus tard, j’avais oublié beaucoup de choses, mais comme le problème venait du premier ensemble de devoirs de COMS 331, je pensais me souvenir des bases.
    • J’y ai passé plusieurs jours sans aucun progrès, puis je m’en suis souvenu à plusieurs reprises par la suite, y ai repensé pendant des heures ou une journée entière, et j’ai continué à échouer.

  • Si vous voulez apprendre ces idées directement par la programmation, je recommande le livre de Tom Stuart, "Understanding Computation From Simple Machines to Impossible Programs".

  • Une version plus complète de ce cours est disponible dans une playlist YouTube.

  • Il existe d’autres versions de ce cours, y compris avec la « méthode probabiliste », et je ne peux pas imaginer une preuve sur les obstacles dans un espace topologique de solutions sans la manière moderne de penser les preuves existentielles (plutôt que constructives).

  • Si ce sujet vous intéresse, vous pouvez consulter le site web de Boaz Barak ainsi que son manuel disponible en PDF.

  • Les deux idées les plus importantes en informatique théorique :

    1. Une liste Move to front peut prendre jusqu’à deux fois plus de temps que le temps de recherche optimal dans une liste ordonnée, mais elle est souvent bien meilleure qu’un ordre statique de liste.
    2. Les algorithmes aléatoires (comme le quicksort) prennent souvent le même temps, même dans le pire des cas, que les algorithmes non aléatoires, mais en pratique ils sont bien plus rapides que leurs variantes non aléatoires.

  • À quoi ressemblerait une version de ce cours dans d’autres domaines ?

    • On peut imaginer des cours sur les « grandes idées » en physique théorique, en physique expérimentale, en économie, etc.
    • J’ai un jour enseigné un cours intitulé « Inventions de l’ère de l’information », où l’on discutait de toutes les inventions et idées nécessaires pour que la civilisation reproduise notre ère de l’information, depuis l’écriture jusqu’à l’infrastructure informatique moderne. C’était plus amusant justement parce que ce n’était pas un cours centré sur une seule discipline.

  • Je me souviens d’un cours à l’université sur la complexité temporelle. Le professeur désignait au hasard des étudiants et leur demandait la complexité temporelle d’algorithmes compliqués ; si la réponse était fausse, il passait à un autre étudiant.

  • Comment comprendre le calcul en tant que propriété fondamentale de l’univers ? Comment les plantes et les animaux effectuent-ils des calculs ?