Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Программа ПМИ в магистратуру по информатике

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

 

Алгоритмы и структуры данных

  1. Задача сортировки N объектов. Приведите алгоритм, который решает эту задачу за ?(log(N!)). Докажите, что любой алгоритм сортировки в среднем будет тратить время не меньшее ?(log(N!)). Алгоритм Quick Sort, его сложность и оптимизации.
  2. Алгоритм Heap Sort. Сложность алгоритма. Какая структура данных используется? Какие еще сортировки известны?
  3. Структура данных «Хеш-таблица». Что такое хеш-таблица? Какой интерфейс у хеш-таблиц? Есть ли стандартная реализация хеш-таблицы в STL? Какие способы разрешения конфликтов существуют? Приведите реализацию функции insert для открытой адресации.
  4. Структура данных «Красно-чёрное дерево». Что такое сбалансированность дерева и как его можно достигнуть? Каким образом достигается сбалансированность в красно-чёрных деревьях? Какие оценки для времени выполнения операций find, insert, erase? Приведите реализацию функции insert, включая вращения.
  5. Структура данных «Двоичный контейнер» (RMQ). Опишите структуру данных. Опишите следующие алгоритмы и укажите оценку времени их работы:
    • алгоритм построения двоичного контейнера
    • алгоритм выполнения запроса «минимальный элемент в промежутке [i, j)»
    • алгоритм выполнения запроса «10 минимальных элементов в промежутке [i, j)»


    Решение задачи RMQ с помощью таблицы.


  6. Задача LCA. Сведение к задаче RMQ. Сведение RMQ к LCA.
  7. Жадные алгоритмы.
  8. Динамическое программирование.
  9. Дискретная и непрерывная задачи о рюкзаке.
  10. Задача LCS (Longest Common Subsequence). Расстояние Левенштейна.
  11. Алгоритмы обхода графа в глубину и в ширину.
  12.  Система непересекающихся множеств. Алгоритм Крускала.
  13. Алгоритмы Флойда и Дейкстры для поиска кратчайших путей в графе.
  14. Кучи. Бинарная, биномиальная, фибоначчиева. Алгоритмы для работы с кучей в STL. Очередь с приоритетами и реализация в STL.
  15. Поиск подстроки в тексте. Поиск общей подстроки максимальной длины двух текстов. Суффиксное дерево. Построение за линейное время.
  16. Суффиксный массив. Построение за N log N. Линейный алгоритм.
  17. Инфиксная и постфиксная формы записи. Перевод из одной системы в другую. Калькулятор.
  18. ООП в C++.
  19. Шаблоны в C++.
  20. Контейнеры и алгоритмы STL.
  21. Исключения в С++.e,send,recv...).


    Архитектура компьютеров и Операционные системы


  22. Архитектура компьютера: Представление целых чисел: знаковые, беззнаковые, Представление вещественных чисел. Логическая архитектура компьютера. Архитектуры: фон Неймана, гарвардская.
    Средства распараллеливания/ускорения работы процессора: конвейер, кэш, суперскалярная архитектура.
  23. Задачи операционной системы: понятие вычислительной системы, управление физическими/логическими ресурсами, планирование. Типы операционных систем: пакетные, разделения времени, реального времени, сетевые
  24. Структура операционной системы, характеристики, свойства, задачи. Понятие процесса, виды процессов.
  25. Файловые системы: FAT, NTFS, UFS, FFS. Сравнение.
  26. Управление памятью: одиночное распределение, cтраничное, сегментное, сегментно-страничное, свопинг
  27. Взаимодействие процессов, IPC: пайпы, сигналы, очереди сообщений, сокеты, семафоры, shared memory
  28. Сеть: Уровни ISO/OSI, TCP/IP, Передача данных. Системные вызовы для поддержки сети в ОС (socket, bind, listen, access, connect, read, write, send, recv...).


    Базы данных


  29. Классификация БД по модели данных. Реляционная теория. Атрибуты, кортежи, домены, отношения. Первичные и внешние ключи.
  30. Проектирование БД. Функциональные зависимости.Нормальные формы. Декомпозиция.
  31. Реляционные операции. Агрегаты, группировки, аналитические функции.
  32. Физическое устройство БД. Страницы данных. Индексы.
  33. Транзакции, ACID. Атомарность и долговечность. ARIES, логирование.
  34. Конкурентный доступ. Согласованность и изолированность. Виды изоляции.


    Функциональное программирование


  35. Определение функционального программирования. Абстракция и декомпозиция при функциональном подходе. Декларативное программирование. Плюсы и минусы.
  36. Лямбда-исчисление. Редукция. Функции нескольких аргументов. Каррирование.
  37. Виды рекурсии. Рекурсивные структуры данных. Функциональные структуры данных.
  38. Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера и теорема стандартизации. Экстенсиональность. Слабая заголовочная нормальная форма.


    Вычислительная математика


  39. Приближение функций, заданных на дискретном множестве. Существование и единственность алгебраического интерполяционного полинома. Интерполяционный полином в форме Лагранжа и в форме Чебышева.
  40. Численное интегрирование. Квадратурные формулы Ньютона-Котеса и оценка их погрешности. Квадратурные формулы Гаусса.
  41. Решение СЛАУ. Обусловленность. Метод Гаусса, метод Гаусса с выбором главного элемента, метод прогонки. LU-разложение.
  42. Итерационные методы решения СЛАУ. Метод простых итераций, необходимое, достаточное условия его сходимости.
  43. Методы численного решения уравнений и систем нелинейных уравнений. Принцип сжимающих отображений. Метод простых итераций. Метод Ньютона.
  44. Численные методы решения ОДУ. Методы Рунге-Кутты.


    Java


  45. ООП в Java.
  46. Виртуальная машина Java. Управление памятью. Передача примитивных типов в функции. Передача ссылочных типов в функции. Проблема изменения ссылки внутри подпрограммы. Статические инициализаторы. Удаление неиспользуемых объектов и метод finalize. Проблема деструкторов для сложно устроенных объектов. Сборка мусора.
  47. Сетевое программирование на Java. Сериализация/десериализация.
  48. Reflection. Механизмы загрузки классов. Java 2 Security. Средства динамического анализа классов: класс Class, reflection API.
  49. Коллекции и массивы в Java.


    Проектирование программных систем


  50. Моделирование при помощи UML. Статическое представление модели. Диаграммы классов. Виды отношений: ассоциация, зависимость, абстракция, реализация и другие. Ограничения. Экземпляры классов. Варианты использования (прецеденты). Выделение классов. Метод Аббота, карточки Класс-Контракт-Коллеги (CRC), диаграммы устойчивости.
  51. Динамическое представление модели. Поведение. Основные определения.  Структурированный классификатор. Композит и часть. Диаграммы внутренней структуры. Представление взаимодействия. Диаграммы взаимодействия и коммуникации. Роль, спецификация выполнения, сообщение, кооперация. Описание сценариев вариантов использования. Представление деятельности. Представление о сетях Петри. Виды действий, разделы. Контекст выполнения. Потоки управления и данных (объектные). Представление процессов на диаграммах деятельности. Представление конечных автоматов. Диаграммы схем состояний. Состояние, переход, псевдосостояния, составные состояния. Семантика конечных автоматов в UML. Обработка событий, переход по завершении. Моделирование жизненного цикла классификатора с помощью конечных автоматов. Пакеты. Управление моделью.
  52. Методы структурного проектирования. Виды методов: сверху-вниз, снизу-вверх, итеративные. Модульность. Принципы разделения системы на модули. Метрики качества модульной структуры. Метод постепенного уточнения, структурные диаграммы (STD). Диаграммы потоков данных (DFD). Метод структурного программирования Джексона (JSP).
  53. Паттерны проектирования. Структурные, создания и паттерны поведения (GoF). Примеры паттернов. Строитель. Посетитель. Шаблон метода. Фасад. Мост. Метрики качества объектно-ориентированной структуры. Эвристики GRASP.

 

Список литературы

  1. Н.А.Винокуров, А.В.Ворожцов. Практика и теория программирования. В 2-х книгах. – М.: Физматкнига, 2008.
  2. Брюс Эккель, Философия С++. Введение в стандартный С++. – М:Питер, 2004.
  3. Т.Х.Кормен, Ч.И.Лейзерсон, Р.Л.Ривест, К.Штайн. Алгоритмы: построение и анализ, 2-е изд. – М.: Издательский дом «Вильямс», 2006.
  4. Б.У.Керниган, Д.М.Ритчи. Язык программирования С, 2-е издание. – М.: Издательский дом «Вильямс», 2006.
  5. С.Мейерс. Эффективное использование STL . – М.: Питер, 2002.
  6. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2000.
  7. Дж.Бентли. Жемчужины программирования, 2-е изд. – СПб.: Питер, 2002.
  8. Н.Вирт., Алгоритмы + структуры данных = программа. Пер.с англ., – М.: Мир, 1985. – 406 с
  9. Н.Солтер.А., С.Д.Клепер. С++ для профессионалов. М.: Издательский дом «Вильямс», 2006
  10. Г.Шилдт. Полный справочник по С++, 4-е изд. – М.: Издательский дом «Вильямс», 2004
  11. Р.Седжвик. Фундаментальные алгоритмы на C++, 3-е изд. – СПб: ООО «ДиаСофтЮП», 2002.
  12. М.Фаулер. UML. Основы. Третье издание. (любой издатель)
  13. К.Ларман. Применение UML 2.0 и шаблонов проектирования. Введение в объектно-ориентированный анализ, проектирование и итеративную разработку. - «Вильямс» - 2009. - 736 с.
  14. Э.Гамма, Р.Хелм, Р.Джонсон. Приемы объектно-ориентированного проектирования. Паттерны проектирования, любое издание.
  15. R. Pressman. Software Engineering: A Practitioner's Approach, 6th Ed. - McGraw Hill, 2005
  16. С.А.Орлов. Технологии разработки программного обеспечения. Разработка сложных программных систем. Для студентов и преподавателей высших учебных заведений. – «Питер», 2004. – 527с.
  17. Л.Басс, П.Клементс, Р.Кацман. Архитектура программного обеспечения на практике. 2-е изд. – Л.: «Питер», 2006, 576с.
  18. C.Амблер, Гибкие Технологии: Экстремальное Программирование и Унифицированный Процесс Разработки. - «Питер», 2005.
  19. Б.Мейер, Объектно-ориентированное конструирование программных систем. - Русская Редакция, 2005
  20. B.Liskov, J.Guttag. Program Development in Java: Abstraction, Specification and Object-Oriented Design. - Addison-Wesley, 2000
  21. Б.Эккель. Философия Java. – СПб.: Питер, 2009.
  22. А.М.Робачевский. Операционная система UNIX – СПб.: БХВ-Петербург, 2010.
  23. В.Е.Карпов, К.А.Коньков. Операционные системы – М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2005
  24. Э.С.Таненбаум. Современные Операционные системы, 2-е изд. – СПб.: Питер, 2002
  25. У.С.Стивенс. Разработка сетевых приложений. – СПб.: Питер, 2002.
  26. У.С.Стивенс, С.А.Раго. «UNIX. Профессиональное программирование» (Professional Programming UNIX environment). – СПб.: Символ-Плюс, 2007
  27. К.Дж.Дейт. Введение в системы баз данных. 8-е изд. М.: Издательский дом "Вильяме", 2005
  28. В.С.Рябенький. Введение в вычислительную математику. — М.: Наука–Физматлит, 1994. — 335 с. 2-е изд. М.: Физматлит, 2000. — 296с.
  29. Р.П.Федоренко. Введение в вычислительную физику. — М.: Изд-во МФТИ, 1994. — 526с.
  30. Н.Н.Калиткин. Численные методы. — М.: Наука, 1978. — 512с.
  31. А.И.Лобанов., И.Б.Петров. Вычислительные методы для анализа моделей сложных динамических систем. Часть 1. — М.: МФТИ, 2000. — 168с.
  32. В.И.Косарев. 12 лекций по вычислительной математике. 2-е изд. — М.: Изд-во МФТИ, 2000. — 224с.
  33. Д.В.Сошников. Функциональное программирование — М.:Интернет-университет информа-ционных технологий - ИНТУИТ.ру, 2010.
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика