Автоматизации систем вычислительных комплексов, Алгоритмических языков, Суперкомпьютеров и квантовой информатики, Системного программирования

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://asvk.cs.msu.su/education/net_fund

17. Воеводин В.В., Воеводин Вл.В."Параллельные вычисления", БХВ-Петербург, 2002, 608 стр.

18. Серебряков В.А. Теория и реализация языков программирования. – М.: Физматлит 2012

19. Соммервилл И. Инженерия программного обеспечения. – М.: Вильямс, 2002.

20. Кулямин В.В. Технологии программирования. Компонентный подход. – М.: Интернет-университет информационных технологий, Бином, 2007.

21. Таненбаум Э., Ван Стен М.. Распределенные системы. Принципы и парадигмы.– СПб.: Питер, 2003. – (Серия «Классика Computer Science») – ISBN 5–272–00053–6.

22. Крюков В.А., Бахтин В.А.. Распределенные системы. Материалы по курсу [http://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 – [http://sp.cs.msu.ru/info/1/vvedalg.pdf]

29. Баула В.Г., Томилин А.Н., Волканов Д.Ю. Архитектура ЭВМ и операционные среды. – М.: Академия, 2011.

30. Пильщиков В.Н. Программирование на языке ассемблера IBM PC. – М., Диалог-МИФИ, 2005.

31. Кузьменкова Е.А., Махнычев В.С., Падарян В.А.. Семинары по курсу «Архитектура ЭВМ и язык ассемблера»: учебно-методическое пособие. Часть 1. – М.: МАКС Пресс, 2014. [http://asmcourse.cs.msu.ru/wp-content/uploads/2015/03/asm-ucebnice-1.pdf]

32. Таненбаум Э., Херберт Б. Современные операционные системы. 4-е изд. – СПб.: Питер, 2015.

33. Столлингс В. Операционные системы: Внутреннее устройство и принципы проектирования. – М.: Вильямс. – 2004.

34. Вдовикина Н.В., Машечкин И.В., Терехин А.Н., Томилин. А.Н. “Операционные системы – взаимодействие процессов”, М.,МГУ, 2008 г. 216 с.

35. Материалы по курсу «Операционные системы». – [http://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).

40. Авдошин С. М., Набебин А. А. Дискретная математика. Модулярная алгебра, криптография, кодирование. – М.: ДМК Пресс, 2017.

41. Токарева Н. Н. Симметричная криптография. Краткий курс: учебное пособие – Новосибирск: Новосибирский государственный университет, 2012.

 

Дополнительная Литература

1. Майника. Алгоритмы оптимизации на сетях и графах. М., Мир, 1981

2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М., Мир, 1979

3. Райгородский А.М. Экстремальные задачи теории графов и интернет. М., Интеллект, 2012.

4. Таненбаум Э., Остин Т. Архитектура компьютера. 6-е изд. – СПб.: Питер, 2016

5. Бордаченкова Е.А. Модельные ЭВМ. М., Изд. отдел ф-та ВМиК МГУ, 2012.

6. Кузьменкова Е.А., Падарян В.А., Соловьев М.А. Семинары по курсу «Архитектура ЭВМ и язык ассемблера»: учебно-методическое пособие. Часть 2. Издательство: МАКС ПРЕСС, 2014, 100 стр. [http://asmcourse.cs.msu.ru/wp-content/uploads/2015/02/asm-ucebnice-2.pdf]