Декабрьский зачёт
Вопросы из модулей:
- (1) Введение в информатику.
- (2) Элементы Тьюринговской теории алгоритмов.
- (3) Машины фон Неймана
(обычно что-то отсюда попадает в билеты)
Содержание будет прежним.
Но может отличаться нумерация в зависимости от года сдачи.
- (1) Предмет информатики.
- (2) Информация и сообщения. Интерпретация сообщений.
- (3) Знаки и символы.
- (4) Кодирование.
- (5) Системы счисления.
- (6) Обработка сообщений.
- (7) Обработка информации.
- (8) Автоматизация обработки информации.
- (9) Конструктивное описание процесса обработки дискретных сообщений.
- (10) Свойства алгоритмов.
- (11) Сложность алгоритмов.
- (12) Семиотические модели интерпретации дискретных сообщений.
- (13) Необходимость формального определения алгоритма.
- (14) Машины Тьюринга.
- (15) Нормальные алгоритмы Маркова.
- (16) Диаграммы машин Тьюринга.
- (17) Моделирование машин Тьюринга.
- (18) Эквивалентность программ и диаграмм.
- (19) Эквивалентность диаграмм и программ.
- (20) I теорема Шеннона. Доказательство*.
- (21) II теорема Шеннона. Доказательство*.
- (22) Вычислимые функции.
- (23) Нормированные вычисления. Теорема о нормированной вычислимости. Доказательство*.
- (24) Теорема о композиции. Доказательство.
- (25) Теорема о ветвлении. Доказательство.
- (26) Теорема о цикле. Доказательство.
- (27) Схемы машин Тьюринга. Нисходящая разработка.
- (28) Теорема Бойма-Джакопини-Миллса. Доказательство.
- (29) Универсальная машина Тьюринга. Построение*.
- (30) Линейная запись схем машин Тьюринга
- (31) Критика модели вычислений Тьюринга.
Иногда выпадают вопросы отсюда:
- (32) Алгоритмическая модель фон Неймана. Адреса и имена.
- (33) Специализированные процессоры для обработки сообщений.
- (34) Построение универсального процессора фон Неймана.
- (35) Машина фон Неймана: принципы реализации.
- (36) Структура программ для машины фон Неймана.