Курс "Низкоуровневое программирование"

Введение

Задания на чтение

  • Стивен Леви. "Хакеры: Герои компьютерной революции".

Рекомендуемая литература

  • Нассим Николас Талеб. "Черный лебедь. Под знаком непредсказуемости" (как относится к большому объему рекомендуемой литературы)
    • пролог, раздел "О птичьем оперении";
    • часть I, раздел "Антибиблиотека Умберто Эко, или О поиске подтверждений".

Лекция 1 (вычислимость)

Задания на чтение

  • Эдсгер Дейкстра. "Дисциплина программирования"
    • глава 0 "Абстракция исполнения";
  • Марвин Минский. "Вычисления и автоматы"
    • глава 5 "Вычислимость, эффективные процедуры и алгоритмы. Бесконечные машины";
    • глава 6 "Машины Тьюринга";
    • глава 7 "Универсальные машины Тьюринга";
  • Дональд Кнут. "Искусство программирования" т.1
    • параграф 1.1 "Алгоритмы".

Рекомендуемая литература

  • Марвин Минский. "Вычисления и автоматы" ("Основной предмет книги - эффективная вычислимость - представляет собой столь простое и столь фундаментальное понятие, что оно должно быть атрибутом мышления всякого образованного человека").
  • Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман "Построение и анализ вычислительных алгоритмов" (простой способ быстро разобраться, что такое NP-полнота, в чем состоит проблема "P=NP" и др.)
    • параграф 1.6 "Простейшая модель вычислений: машина Тьюринга";
    • глава 10 "NP-полные задачи";
  • Charles Petzold. "The Annotated Turing. A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine" (подробный разбор основополагающей работы в области теоретической информатики).

Лекция 2 (вычислимость)

Задания на чтение

  • Марвин Минский. "Вычисления и автоматы"
    • глава 7 "Универсальные машины Тьюринга";
    • глава 8 "Ограничения эффективной вычислимости: некоторые проблемы, не разрешимые машинами, выполняющими предписания".

Рекомендуемая литература

  • Christopher Strachey. An impossible program (элементарное доказательство невозможности программы, решающей проблему останова).
  • Марвин Минский. "Вычисления и автоматы" ("Основной предмет книги - эффективная вычислимость - представляет собой столь простое и столь фундаментальное понятие, что оно должно быть атрибутом мышления всякого образованного человека").
  • Charles Petzold. "The Annotated Turing. A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine" (подробный разбор основополагающей работы в области теоретической информатики).
  • С.К. Клини. "Математическая логика". ("Имя одного из крупнейших современных специалистов в области математической логики С.К. Клини знакомо советскому читателю по русскому переводу его фундаментального труда "Введение в метаматематику", ставшего настольной книгой для всех, кто занимается математической логикой, рекурсивными, функциями и основаниями математики. Новая его книга представляет собой существенно усовершенствованный, расширенный и приближенный к нуждам университетского преподавания вариант "чисто логической" части этой всемирно известной монографии").

Лекция 3 (тезис Черча-Тьюринга, предыстория ЭВМ)

Задания на чтение

Рекомендуемая литература

  • Herman H. Goldstine. "The computer from Pascal to von Neumann" (история появления ЭВМ от непосредственного участника событий).
  • Б.Н. Малиновский. "История вычислительной техники в лицах" (история ЭВМ в СССР).
  • Роджер Пенроуз. "Новый ум короля: О компьютерах, мышлении и законах физики" ("...Пенроуз обсуждает широчайший круг явлений: алгоритмизацию математического мышления, машины Тьюринга, теорию сложности, теорему Геделя...").
  • Stan Augarten “Bit by bit: An Illustrated History of Computers” (история ЭВМ).
  • Martin Campbell-Kelly, William Aspray, Nathan Ensmenger, and Jeffrey R. Yost "Computer: a history of the information machine", 3rd ed. (история ЭВМ).
  • Martin Davis. "Engines of Logic. Mathematicians and the Origin of the Computer" ("This book is about the underlying concepts on which our modern computers are based and about the people who developed these concepts").
  • Michael R. Williams "History of Computing Technology", 2nd ed. (история ЭВМ).
  • Р.С.Гутер, Ю.Л.Полунов "От абака до компьютера", 2-е изд.:

Лекция 4 (архитектура фон Неймана)

Рекомендуемая литература

Лекция 5 (архитектура фон Неймана)

Задания на чтение

  • Эндрю Таненбаум, Тодд Остин. "Архитектура компьютера", 6-е изд.
    • Глава 1 "Введение"
      • "Многоуровневая компьютерная организация";
      • "Развитие компьютерной архитектуры".
    • Глава 2 "Организация компьютерных систем"
      • "Процессоры";
      • "Основная память";
      • "Вспомогательная память", подраздел "Иерархическая структура памяти".

Лекция 6 (развитие архитектуры системы команд в ЭВМ второго и третьего поколений)

Рекомендуемая литература

  • Дональд Кнут. "Искусство программирования" т.1:
    • параграф 1.3.1 "Описание MIX";
    • параграф 1.3.2 "Язык ассемблера компьютера MIX";
    • параграф 1.4.1 "Подпрограммы".

Лекция 7 (развитие архитектуры системы команд в ЭВМ второго и третьего поколений)

Задания на чтение

  • Эндрю Таненбаум, Тодд Остин. "Архитектура компьютера", 6-е изд.
    • Глава 5 "Уровень архитектуры набора команд"
      • "Общий обзор уровня архитектуры набора команд";
      • "Форматы команд";
      • "Адресация";
      • "Типы команд".

Рекомендуемая литература

Лекция 8, лекция 9 (архитектура системы команд современного процессора на примере RISC-V)

Задания на чтение

Рекомендуемая литература

Слайды

Методические материалы

Задания