Nous présentons et étudions des algorithmes classiques pour deux problèmes fondamentaux, dans le contexte d'applications réalistes. Notre message est que les algorithmes efficaces (la recherche binaire et le mergesort, dans ce cas) sont un ingrédient clé pour aborder les problèmes informatiques avec des solutions évolutives qui peuvent traiter des instances énormes, et que la méthode scientifique est essentielle pour évaluer l'efficacité de ces solutions.

Notre introduction aux structures de données est un regard attentif sur les abstractions fondamentales des piles et des files d'attente, y compris les spécifications de performance. Nous introduisons ensuite le concept de structures liées et nous nous concentrons sur leur utilité dans le développement d'implémentations simples, sûres, claires et efficaces des piles et des files d'attente.

L'abstraction de la table des symboles est l'un des outils de programmation les plus importants et les plus utiles, comme nous l'illustrerons à l'aide de plusieurs exemples dans cet exposé. En prolongeant l'approche scientifique des deux cours précédents, nous introduisons et étudions les arbres de recherche binaires, une structure de données classique qui supporte des implémentations efficaces de cette abstraction.

La théorie de l'informatique nous aide à répondre à des questions fondamentales sur la nature de l'informatique tout en nous aidant à mieux comprendre la façon dont nous interagissons avec l'ordinateur. Dans cet exposé, nous présentons les langages formels et les machines abstraites, en nous concentrant sur des modèles simples qui sont en fait largement utiles dans les applications pratiques.

En 1936, Alan Turing a publié un article qui est largement salué comme l'un des articles scientifiques les plus importants du 20e siècle. Cette conférence est consacrée aux deux idées centrales de grande portée de cet article : Tous les dispositifs de calcul ont une puissance de calcul équivalente et cette puissance est limitée.

Avec le développement des applications informatiques, les informaticiens et les mathématiciens ont compris qu'il fallait affiner les idées de Turing. Quels sont les problèmes informatiques que nous pouvons résoudre avec les limitations de ressources qui sont inéluctables dans le monde réel ? Comme nous le verrons dans cette conférence, cette question reste fondamentalement sans réponse.

Tout programmeur doit comprendre les caractéristiques de base du processeur informatique sous-jacent qu'il utilise. Heureusement, la conception fondamentale des processeurs informatiques a peu changé depuis les années 1960. Dans ce cours, nous vous proposons de comprendre comment votre code Java effectue réellement son travail en introduisant un ordinateur imaginaire qui est similaire à la fois aux mini-ordinateurs des années 1960 et aux microprocesseurs que l'on trouve dans les ordinateurs portables et les appareils mobiles d'aujourd'hui.

Poursuivant notre description de la conception des processeurs et de la programmation de bas niveau, nous fournissons un contexte remontant aux années 1950 et discutons des implications futures de la machine de von Neumann, où les programmes et les données sont conservés dans la même mémoire. Nous examinons en détail l'idée selon laquelle nous concevons de nouveaux ordinateurs en les simulant sur d'anciens ordinateurs, ce que la théorie de Turing garantit comme étant toujours efficace.

En commençant par quelques abstractions simples (des fils qui peuvent transporter des valeurs on/off et des interrupteurs qui peuvent contrôler les valeurs transportées par les fils), nous abordons dans ce cours la conception des circuits qui mettent en œuvre les processeurs d'ordinateur. Nous considérons les portes qui mettent en œuvre des fonctions logiques simples et les composants pour les fonctions de plus haut niveau, telles que l'addition. Le cours se termine par la présentation d'un circuit complet pour une unité arithmétique/logique.

Dans ce cours, nous apportons la dernière partie de notre réponse à la question "Comment fonctionne un ordinateur ?" en développant un circuit complet pour un processeur d'ordinateur, où chaque interrupteur et chaque fil est visible. Bien qu'à une échelle très différente, ce circuit présente, du point de vue de la conception, de nombreuses caractéristiques similaires à celles des circuits que l'on trouve dans votre ordinateur et votre téléphone.