• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Подготовка к поступлению

Готовиться к поступлению на программу нужна в первую очередь по  программе собеседования.
Также можно рекомендовать посещать научные мероприятия факультета компьютерных наук, анонсы которых можно найти на главной странице факультета

Дни открытых дверей программ магистратуры факультета компьютерных наук проводятся как правило два раза в год - весной и осенью. Следите за информацией на сайте.
Также ежегодно проходит Зимняя школа по компьютерным наукам.

Программа подготовки к собеседованию для поступающих на образовательную программу магистратуры «Системное программирование»

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

Список тем и вопросов для подготовки
1. Математические основы программирования
·        Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции.
·        Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста. Минимизация булевых функций в классах нормальных форм.
·        Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка.
·        Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка. Теоретико-множественное и алгебраическое определения решетки, их эквивалентность. Свойства решеток. Булевы решетки. Полные решетки.
·        Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе.
·        Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения.
·        Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.
 
2. Вычислительные машины, системы и сети
·        Архитектура современных компьютеров. Организации памяти и архитектура процессора современных вычислительных машин. Страничная и сегментная организация виртуальной памяти. Кэш-память. Командный и арифметический конвейеры, параллельное выполнение независимых команд, векторные команды. Специализированные процессоры. Машины, обеспечивающие выполнение вычислений, управляемых потоком данных. Организация ввода-вывода, каналы и процессоры ввода-вывода, устройства сопряжения с объектами.
·        Классификация вычислительных систем (ВС) по способу организации параллельной обработки. Многопроцессорные и многомашинные комплексы. Вычислительные кластеры. Проблемно-ориентированные параллельные структуры: матричные ВС, систолические структуры, нейросети.
·        Назначение, архитектура и принципы построения информационно - вычислительных сетей (ИВС). Локальные и глобальные ИВС, технические и программные средства объединения различных сетей.
·        Методы и средства передачи данных в ИВС, протоколы передачи данных.
·        Особенности архитектуры локальных сетей (Ethernet, Token Ring, FDDI).
·        Сеть Internet, доменная организация, семейство протоколов TCP/IP. Информационно-вычислительные сети и распределенная обработка информации.
3. Языки и системы программирования. Технология разработки программного обеспечения
·        Языки программирования. Процедурные языки программирования (Си), Функциональные языки программирования (Лисп), объектно-ориентированные языки программирования (Java).
·        Процедурные языки программирования. Основные управляющие конструкции, структура программы. Работа с данными: переменные и константы, типы данных (булевский, целочисленные, плавающие, символьные, типы диапазона и перечисления, указатели), структуры данных (массивы и записи). Процедуры (функции): вызов процедур, передача параметров (по ссылке, по значению, по результату), локализация переменных, побочные эффекты. Обработка исключительных ситуаций. Библиотеки процедур и их использование.
·        Объектно-ориентированное программирование. Классы и объекты, наследование, интерфейсы. Понятие об объектном окружении. Рефлексия. Библиотеки классов. Средства обработки объектов (контейнеры и итераторы).
·        Основы построения трансляторов. Структура оптимизирующего транслятора. Промежуточные представления программы: последовательность символов, последовательность лексем, синтаксическое дерево, абстрактное синтаксическое дерево. Уровни промежуточного представления: высокий, средний, низкий. Формы промежуточного представления.
·        Анализ исходной программы в компиляторе. Автоматные (регулярные) грамматики и сканирование, контекстно свободные грамматики и синтаксический анализ, организация таблицы символов программы, имеющей блочную структуру, хеш-функции. Нисходящие (LL(1)-грамматики) и восходящие (LR(1)-грамматики) методы синтаксического анализа. Атрибутные грамматики и семантические программы, построение абстрактного синтаксического дерева. Автоматическое построение лексических и синтаксических анализаторов по формальным описаниям грамматик. Системы lex и yacc. Система Gentle.
·        Машинно-ориентированные языки, язык ассемблера. Представление машинных команд и констант. Команды транслятору. Их типы, принципы реализации. Макросредства, макровызовы, языки макроопределений, условная макрогенерация, принципы реализации.
·        Системы программирования (СП), типовые компоненты СП: языки, трансляторы, редакторы связей, отладчики, текстовые редакторы. Модульное программирование. Типы модулей. Связывание модулей по управлению и данным.
·        Технология разработки и сопровождения программ. Жизненный цикл программы. Этапы разработки, степень и пути их автоматизации.
·        Отладка, тестирование, верификация и оценивание сложности программ. Генерация тестов.
4. Операционные системы
·        Режимы функционирования вычислительных систем, структура и функции операционных систем. Основные блоки и модули. Основные средства аппаратной поддержки функций операционных систем (ОС): система прерываний, защита памяти, механизмы преобразования адресов в системах виртуальной памяти, управление каналами и периферийными устройствами.
·        Виды процессов и управления ими в современных ОС. Представление процессов, их контексты, иерархии порождения, состояния и взаимодействие. Многозадачный (многопрограммный) режим работы. Команды управления процессами. Средства взаимодействия процессов. Модель клиент-сервер и ее реализация в современных ОС.
·        Параллельные процессы, схемы порождения и управления. Организация взаимодействия между параллельными и асинхронными процессами: обмен сообщениями, организация почтовых ящиков. Критические участки, примитивы взаимоисключения процессов, семафоры Дейкстры и их расширения. Проблема тупиков при асинхронном выполнении процессов, алгоритмы обнаружения и предотвращения тупиков.
·        Операционные средства управления процессами при их реализации на параллельных и распределенных вычислительных системах и сетях: стандарты и программные средства PVM, MPI, OpenMP, POSIX .
·        Одноуровневые и многоуровневые дисциплины циклического обслуживания процессов на центральном процессоре, выбор кванта.
·        Управление доступом к данным. Файловая система, организация, распределение дисковой памяти. Управление обменом данными между дисковой и оперативной памятью. Рабочее множество страниц (сегментов) программы, алгоритмы его определения.
·        Управление внешними устройствами.
·        Оптимизация многозадачной работы компьютеров. Операционные системы Windows, Unix, Linux. Особенности организации, предоставляемые услуги пользовательского взаимодействия.
·        Операционные средства управления сетями. Эталонная модель взаимодействия открытых систем ISO/OSI. Маршрутизация и управление потоками данных в сети. Локальные и глобальные сети.
 
5. Методы хранения данных и доступа к ним. Организация баз данных и знаний
·        Концепция типа данных. Абстрактные типы данных. Объекты (основные свойства и отличительные признаки).
·        Основные структуры данных, алгоритмы обработки и поиска. Сравнительная характеристика методов хранения и поиска данных.
·        Основные понятия реляционной и объектной моделей данных.
·        Теоретические основы реляционной модели данных (РДМ). Реляционная алгебра, реляционное исчисление. Функциональные зависимости и нормализация отношений.
·        CASE-средства и их использование при проектировании базы данных (БД).
·        Организация и проектирование физического уровня БД. Методы индексирования.
·        Обобщенная архитектура, состав и функции системы управления базой данных (СУБД). Характеристика современных технологий БД. Примеры соответствующих СУБД.
·        Основные принципы управления транзакциями, журнализацией и восстановлением.
·        Язык баз данных SQL. Средства определения и изменения схемы БД, определения ограничений целостности. Контроль доступа. Средства манипулирования данными.
·        Стандарты языков SQL. Интерактивный, встроенный, динамический SQL.
·        Основные понятия технологии клиент-сервер. Характеристика SQL-сервера и клиента. Сетевое взаимодействие клиента и сервера.

Основная литература для подготовки
1.     Ахо, Сети Р., Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. - М., 2001. Введение в криптографию / Под ред. В.В. Ященко. - СПб.: МЦНМО, 2001.
2.     Воеводин В.В., Воеводин Вл. В. Параллельное программирование. - СПб.: БХВ- Петербург, 2002.
3.     Галатенко В.А. Основы информационной безопасности. Под ред. В.Б. Бетелина. - М.: ИНТУИТ.РУ, 2003.
4.     Галатенко В.А. Стандарты информационной безопасности. Под ред. В.Б. Бетелина. – М.: ИНТУИТ.РУ, 2004.
5.     Дейт К.Дж. Введение в системы баз данных. - М.: Вильямс, 1999.
6.     Кнут Д. Искусство программирования. Т. 1 – 3. - М., СПб., Киев: ИД «Вильямс», 2000.
7.     Кузнецов С.Д. Базы данных: языки и модели. Учебник. М.: Бином-Пресс, 2008.
8.     Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. - М.: МЦНМО, 2000.
9.     Липаев В.В. Программная инженерия. Методологические основы. М.: Государственный Университет – Высшая школа экономики, 2006.
10. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы, СПб.: Питер, 2000.
11. Стивенс Р., Раго С. UNIX. Профессиональное программирование. - СПб.: Символ-Плюс, 2007.
12. Таненбаум Э. Современные операционные системы. - СПб.:Питер, 2002.
13. Таненбаум Э., Ван Стен М. Распределенные системы. Принципы и парадигмы. - СПб.:Питер, 2003.
14. Танненбаум Э., Уэзеролл Д. Компьютерные сети. СПб.: Питер, 2003.
15. Танненбаум Э. Архитектура компьютера. СПб.: Питер, 2006.
16. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 2001.
17. Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Инфра-М, Новосибирский государственный технический университет (НГТУ), 2009.
18. Дополнительная литература
19. Гласс Г., Эйбле К. Unix для программистов и пользователей. СПб.: БХВ-Петербург, 2004.
20. Корнеев В.В. Вычислительные системы. М.: Гелиос АРВ, 2004.
21. Королев Л.Н. Архитектура процессоров электронных вычислительных машин, М.: Издательский отдел ВМиК МГУ, 2003.
22. Хаулет Т. Защитные средства с открытыми исходными текстами. Пер. с англ. - М.: ИНТУИТ.РУ, БИНОМ. Лаборатория знаний, 2007.
23. Арлоу Д., Нейштадт А. UML 2 и унифицированный процесс. Практический объектно-ориентированный анализ и проектирование. - СПб.: Символ-Плюс. - 2008.
24. Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработка. - СПб.: Питер. - 2007.
25. Гамма Э. и др. Приемы объектно-ориентированного проектирования. Паттерны проектирования.: Пер. с англ. - СПб.: Питер, 2016.
26. Б.Мейер. Объектно-ориентированное конструирование программных систем – М.: Русская Редакция, 2005.
27. Д. Месарош. Шаблоны тестирования xUnit. М.: Вильямс, 2008
28. Материалы курса В.В.Кулямина "Тестирование программного обеспечения": http://mbt-course.narod.ru (доступ 19.01.2017).
29. Ю.Г. Карпов. Model Checking. Верификация параллельных и распределенных программных систем. — СПб.: БХВ-Петербург, 2010.
 
Формат собеседования
Собеседование проводится на русском языке. Допустимо использование дистанционных средств связи.
Собеседование состоит из двух частей. В первой части абитуриент рассказывает о себе, о мотивах, которыми он руководствуется, выбирая системное программирование как направление своего обучения и дальнейшей профессиональной деятельности. На это отводится 5-10 минут.
Затем студент получает 2-3 вопроса и, если нужно, берет время на подготовку. На подготовку и ответ планируется 30-40 минут.