Г. 3 поток Бакалавриат ВМК
Вопросы для подготовки к государственному экзамену
(дополнительная часть)
Кафедры:
Автоматизации систем вычислительных комплексов, Суперкомпьютеров и квантовой информатики, Алгоритмических языков, Системного программирования
1. Теорема Поста о полноте систем функций в алгебре логики.
2. Графы, деревья, планарные графы; их свойства. Оценка числа деревьев.
3. Логика 1-го порядка. Выполнимость и общезначимость. Общая схема метода резолюций.
4. Логическое программирование. Декларативная семантика и операционная семантика; соотношение между ними. Стандартная стратегия выполнения логических программ.
5. Сортировка. Простейшие алгоритмы – сортировка выбором, вставками, обменом. Оценка сложности алгоритмов сортировки. Быстрая сортировка и ее сложность в среднем и в наихудшем случаях.
6. Язык ассемблера как машиннозависимый язык низкого уровня. Организация ассемблерной программы, секции кода и данных (на примере ассемблера nasm или masm). Основные этапы подготовки к счёту ассемблерной программы: трансляция, редактирование внешних связей (компоновка), загрузка.
7. Операционные системы. Управление оперативной памятью в вычислительной системе. Алгоритмы и методы организации и управления страничной оперативной памятью.
8. Зависимости в реляционных отношениях: функциональные, многозначные, проекции/соединения. Проектирование реляционных БД на основе принципов нормализации отношений. Нормальные формы.
9. Закон Амдала, его следствия. Граф алгоритма. Критический путь графа алгоритма, ярусно-параллельная форма графа алгоритма. Этапы решения задач на параллельных вычислительных системах.
10. Глобальные и локальные модели освещения в компьютерной графике. Модель Фонга.
11. Коды Боуза-Чоудхури-Хоквингема: определение, алгоритмы кодирования и декодирования.
12. Классификация языков, определяемых конечными автоматами, регулярными выражениями и праволинейными грамматиками. Эквивалентность и минимизация конечных автоматов.
13. Функции FIRST и FOLLOW. LL(l)-грамматики. Конструирование таблицы предсказывающего анализатора.
14. Жизненный цикл программного обеспечения (ПО). Основные виды деятельности при разработке ПО. Каскадная и итерационная модели жизненного цикла.
15. Качество программного обеспечения и методы его контроля. Тестирование и другие методы верификации.
16. Сложность алгоритма как функция одного или нескольких числовых аргументов: сложность в худшем случае и в среднем.
17. Основные принципы построения и архитектура сети Интернет. Алгоритмы и протоколы внешней и внутренней маршрутизации. Явление перегрузки и методы борьбы с ней.
18. Теоретические основы передачи данных, физический уровень стека протоколов. Системы передачи данных Ethernet и Wi-Fi: алгоритмы работы, управление множественным доступом к каналу.
19. Базисные типы данных в языках программирования. Основные проблемы, связанные с базисными типами и способы их решения в различных языках. Понятие абстрактного типа данных и способы его реализации в современных языках программирования.
20. Понятие о парадигме программирования. Основные парадигмы программирования. Языки и парадигмы программирования.
21. Основные характеристики функциональных языков программирования. Использование понятий функционального программирования (замыкания, анонимные функции) в современных объектно-ориентированных языках.
22. Синхронизация в распределенных системах. Синхронизация времени. Логические часы. Выборы координатора. Взаимное исключение. Координация процессов.
23. Отказоустойчивость в распределенных системах. Типы отказов. Фиксация контрольных точек и восстановление после отказа. Репликация и протоколы голосования. Надежная групповая рассылка.
24. Распределенные файловые системы. Доступ к директориям и файлам. Семантика одновременного доступа к одному файлу нескольких процессов. Кэширование и размножение файлов.
25. Промежуточные представления программы: абстрактное синтаксическое дерево; последовательность трехадресных инструкций. Базовые блоки и граф потока управления.
26. Локальная оптимизация при компиляции программы. Ориентированный ациклический граф и метод нумерации значений.
27. Глобальная оптимизация при компиляции программы. Построение передаточных функций базовых блоков. Монотонные и дистрибутивные передаточные функции. Метод неподвижной точки и его применение для нахождения достигающих определений.
28. Постановка задачи дискретной оптимизации. Метод ветвей и границ. Задача целочисленного линейного программирования.
29. Комбинаторные методы нахождения оптимального пути в графе.
30. Потоки в сетях. Алгоритм построения максимального потока. Оценка сложности алгоритма.
Литература к дополнительной части вопросов для кафедр АСВК, СКИ, АЯ, СП.
1. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. - М.: ДИАЛОГ-МИФИ.
2. Яблонский С.В. Введение в дискретную математику. - М.: Высшая школа, 2001.
3. Алексеев В.Б. Лекции по дискретной математике. М.: ИНФРА-М, 2012.
4. Ложкин С.А. Лекции по основам кибернетики. М. Изд-во ф-та ВМК, 2004.
5. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.
6. Братко И. Алгоритмы искусственного интеллекта на языке Пролог. 3-е изд. – М.: Вильямс, 2004.
7. Головин И.Г., Волкова И.А. Языки и методы программирования. – М.: Издательский центр «Академия», 2012.
8. Кауфман В.Ш. Языки программирования: концепции и примеры. М.: Радио и связь, 1993
9.Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий. – 2-е издание – М.: Вильямс. – 2008, 2014, 2016.
10. Cooper K. D., Torczon L. Engineering a Compiler (Second Edition) – Elsevier, Inc. 2012
11. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – М.: Вильямс, 2016.
12. Королев Л.Н. Архитектура ЭВМ М. Научный мир. 2005.
13. Абрамов С.А. Лекции о сложности алгоритмов. Издание второе переработанное. – М.: МЦНМО, 2012.
14. Смелянский Р. Л. Компьютерные сети: в 2 т. Т.1 Системы передачи данных. - Издательский центр "Академия" г.Москва, 2011. — С. 304.
15. Смелянский Р. Л. Компьютерные сети: в 2 т. Т.2. Сети ЭВМ. — Издательский центр "Академия" г.Москва, 2011. — С. 240.
16. Материалы по курсу Компьютерные Сети: https://lvk.cs.msu.su/ru/courses#overlay-context=ru
17. Воеводин В.В., Воеводин Вл.В."Параллельные вычисления", БХВ-Петербург, 2002, 608 стр.
18. Серебряков В.А. Теория и реализация языков программирования. – М.: Физматлит 2012
19. Соммервилл И. Инженерия программного обеспечения. – М.: Вильямс, 2002.
20. Кулямин В.В. Технологии программирования. Компонентный подход. – М.: Интернет-университет информационных технологий, Бином, 2007.
21. Таненбаум Э., Ван Стен М.. Распределенные системы. Принципы и парадигмы.– СПб.: Питер, 2003. – (Серия «Классика Computer Science») – ISBN 5–272–00053–6.
22. Крюков В.А., Бахтин В.А.. Распределенные системы. Материалы по курсу [https://sp.cs.msu.ru/courses/os/distr-sys-2014.zip] [ftp://ftp.keldysh.ru/K_student/distr-sys-2014/distr-sys-2014.zip]
23. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М., Мир, 1984.
24. Кристофидес Н. Теория графов. Алгоритмический подход. М., Мир, 1978
25. Ху Д. Целочисленное программирование и потоки в сетях. М., Мир, 1084
26. Кормен Т., Лейсерзон Ч., Риверст Р., Штайн К. Алгоритмы. Построение и анализ. М., ООО «И.Д.Вильямс», 2013.
27. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. – М.: Вильямс, 2014 – Т. 3.
28. Корухова Л.С., Шура-Бура М.Р. Введение в алгоритмы. Учебное пособие для студентов I курса. – М.: Изд. отдел ф-та ВМК МГУ, 2010 – [https://sp.cs.msu.ru/info/1/vvedalg.pdf]
29. Баула В.Г., Томилин А.Н., Волканов Д.Ю. Архитектура ЭВМ и операционные среды. – М.: Академия, 2011.
30. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. – М., Диалог-МИФИ, 2005.
31. Кузьменкова Е.А., Махнычев В.С., Падарян В.А.. Семинары по курсу «Архитектура ЭВМ и язык ассемблера»: учебно-методическое пособие. Часть 1. – М.: МАКС Пресс, 2014. [https://asmcourse.cs.msu.ru/wp-content/uploads/2015/03/asm-ucebnice-1.pdf]
32. Таненбаум Э. С., Херберт Б. Современные операционные системы. 4-е изд. – СПб.: Питер, 2015.
33. Столлингс В. Операционные системы: Внутреннее устройство и принципы проектирования. – М.: Вильямс. – 2004.
34. Вдовикина Н.В., Машечкин И.В., Терехин А.Н., Томилин. А.Н. “Операционные системы – взаимодействие процессов”, М.,МГУ, 2008 г. 216 с.
35. Материалы по курсу «Операционные системы». – [https://jaffar.cs.msu.su/mash/os/2016%202017/]
36. Дейт К. Введение в системы баз данных – М.: Вильямс, 2016.
37.Кузнецов С.Д. Базы данных. – М.: Издательский центр «Академия», 2012.
38. Журавлёв Ю.И., Флёров Ю.А., Вялый М.Н. Дискретный анализ. Основы высшей алгебры. М.: МЗ Пресс, 2007 (раздел 4.3).
39. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. – М.: Техносфера, 2006 (разделы 3.1.1-3.1.4, 3.5.1, 3.5.4, 3.5.5).
Дополнительная Литература
1. Майника. Алгоритмы оптимизации на сетях и графах. М., Мир, 1981
2. Ахр А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М., Мир, 1979
3. Райгородский А.М. Экстремальные задачи теории графов и интернет. М., Интеллект, 2012.
4. Таненбаум Э., Т. Остин Т. Архитектура компьютера. 6-е изд. – СПб.: Питер, 2016
5. Бордаченкова Е.А. Модельные ЭВМ. М., Изд. отдел ф-та ВМиК МГУ, 2012.
6. Кузьменкова Е.А., Падарян В.А., Соловьев М.А. Семинары по курсу «Архитектура ЭВМ и язык ассемблера»: учебно-методическое пособие. Часть 2. Издательство: МАКС ПРЕСС, 2014, 100 стр.