2016 г. 3 поток Бакалавриат ПМиИ

Вопросы для подготовки к государственному экзамену

(дополнительная часть)

Кафедры:

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

1. Теорема Поста о полноте систем функций в алгебре логики.

2. Графы, деревья, планарные графы; их свойства. Оценка числа деревьев.

3. Логика 1-го порядка. Выполнимость и общезначимость. Общая схема метода резолюций.

4. Логическое программирование. Декларативная семантика и операционная семантика; соотношение между ними. Стандартная стратегия выполнения логических программ.

5. Транзакционное управление в СУБД. Методы сериализации транзакций.

6. Аппаратно-программные средства поддержки мультипрограммного режима – система прерываний, защита памяти, привилегированный режим.

7. Организация взаимодействия процессов и средства их синхронизации. Классические задачи синхронизации.

8. Виртуальная память. Модели организации оперативной памяти.

9. Алгоритм Сети-Ульмана оптимального распределения регистров и его обоснование.

1. Основные принципы объектно-ориентированного программирования.

2. Основные этапы компиляции (лексический анализ, синтаксический анализ, семантический анализ, генерация кода и т.д.)

3. Построение детерминированного конечного автомата по регулярному выражению.

4. Построение канонической системы множеств LR(1) ситуаций и таблиц действий и переходов для LR(1) грамматик.

5. Сложность алгоритма как функция одного или нескольких числовых аргументов. Сложность в худшем случае.

6. Сложность в среднем. Сложность рандомизированного алгоритма.

7. Основные принципы построения сети Интернет. Иерархическая модель компьютерной сети. Адресация в сети Интернет, протоколы ARP, DHCP. Модели основных протоколов IP, TCP, ICMP. Модель взаимодействия приложений в Интернет.

8. Физический уровень стека сетевых протоколов. Технологии Ethernet и WiFi. Алгоритмы работы, коллизии, управление множественным доступом к каналу.

9. Коммутация пакетов, устройство пакетов. Как устроен и работает пакетный коммутатор (switch). Виды задержек в компьютерной сети и способы управления ими (приоритеты, веса и гарантированная скорость потока). Управление потоком при пакетной коммутации.

10. Алгоритмы маршрутизации в Интернет: основные подходы. Структура сети Интернет, понятие автономной системы, протокол внешней маршрутизации BGP. Явление перегрузки и основные методы борьбы с ней. Перегрузка: AIMD в случае одного потока и в случае нескольких потоков.

11. Качество программного обеспечения и методы его контроля. Тестирование и другие методы верификации.

12. Виды параллельной обработки данных, их особенности. Компьютеры с общей и распределенной памятью. Вычислительные кластеры: узлы, коммуникационная сеть, способы построения. Производительность вычислительных систем, методы оценки и измерения.

13. Закон Амдала, его следствия. Граф алгоритма. Критический путь графа алгоритм, ярусно-параллельная форма графа алгоритма. Этапы решения задач на параллельных вычислительных системах.

14. Технологии параллельного программирования MPI и OpenMP.

Литература к дополнительной части вопросов для кафедр АСВК, СКИ, АЯ, СП.

1. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. - М.: ДИАЛОГ-МИФИ.

2. Яблонский С.В. Введение в дискретную математику. - М.: Высшая школа, 2001.

3. Алексеев В.Б. Лекции по дискретной математике. М.: ИНФРА-М, 2012.

4. Ложкин С.А. Лекции по основам кибернетики. М. Изд-во ф-та ВМК, 2004.

5. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.

6. Братко И. Алгоритмы искусственного интеллекта на языке Пролог. 3-е изд. – М.: Вильямс, 2004.

7. Введение в системы БД. К.Дейт. Вильямс. 2001.

8. Головин И.Г., Волкова И.А. Языки и методы программирования. – М.: Издательский центр «Академия», 2012.

9. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и трансляции, т.1, т.2.

10. Королев Л.Н. Архитектура ЭВМ М. Научный мир. 2005.

11. А.Ахо, Р.Сети, Д.Ульман. Компиляторы. Принципы, технологии и инструментарий. – М.: Вильямс, 2014.

12. Компьютерные сети. Многоуровневая система Интернета.Д.Кроуз, К.Росс. Питер2004.

13. Компьютерные сети. Э.Таненбаум.Питер 2002.

14. Крюков В.А., Бахтин В.А. Распределенные системы. (http://sp.cs.msu.su/courses/os/distr-sy s-2014.zip

15. Абрамов С.А. Лекции о сложности алгоритмов. Издание второе переработанное. – М.: МЦНМО, 2012.

16. Принципы объектно-ориентированной разработки программ. А.Элиенс.Вильямс.2002.

17.Технологиии передачи данных. Г.Хелд, Питер. 2003.

18. Буч Г., Якобсон А., Рамбо Дж. UML. Классика CS. Издание второе. – СПб: Питер, 2006.

19. Современные компьютерные сети. В. Столингс, Питер, 2003.

20. Смелянский Р.Л. 2011 Компьютерные сети: в 2 т. Т.1 Системы передачи данных, Издательский центр "Академия" г. Москва, 2011.

21. Смелянский Р.Л. 2011 Компьютерные сети: в 2 т. Т.2 Сети ЭВМ, Издательский центр "Академия" г.Москва, 2011.

22. https://lvk.cs.msu.su/ru/courses#overlay-context=ru

23. Робачевский А., Немнюгин С., Стесик О. Операционная система UNIX.2 –е издание. 2005.

24. Операционные системы. Параллельные и распределенные системы. Питер. 2004.

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

26. В.В.Кулямин. Технологии программирования. Компонентный подход. – М.: ИНТУИТ-Бином, 2007. 463 с. (http://panda.ispras.ru/~kuliamin/lectures-sdt/sdt-book-2006.pdf)

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

28. Антонов А.С. Технологии параллельного программирования MPI и OpenMP: Учеб. пособие. Предисл.: В.А.Садовничий.-М.: Издательство Московского университета, 2012.-344 с.-(Серия"Суперкомпьютерное образование")

29. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. -М.: Изд-во МГУ, 2004.-71 с. (http://parallel.ru/info/parallel/)