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

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

Адрес e-mail:

Программа по информатике

  1. Быстрая сортировка
    • Базовый алгоритм
    • Оцените сложность алгоритма в среднем и худшем случае
    • Доказательство сложности алгоритма
    • Быстрая сортировка для строк
    • Какие оптимизации алгоритма существуют (выбор медианы, использование стека, сортировка вставками, разделение на 3 блока)?
    • Сортировка вставками
  2. «Двусвязный список»
    • Расскажите о реализации двусвязного списка
    • Какие структуры для этого требуются?
    • Модифицируйте его для реализации закольцованности.
  3. Задача сортировки N объектов.
    • Базовый алгоритм быстрой сортировки. Его производительность в худшем случае.
    • Что такое стабильная сортировка? Какие сортировки стабильны?
    • Алгоритм бинарного поиска и его модификация для строк.
    • Назовите стандартные реализации сортировок в языке и STL.
    • Предложите алгоритм нахождения k-й порядковой статистики, основанный на идее алгоритма Quick Sort. Напишите иллюстрирующий код.
    • Оцените среднее и худшее время работы этого алгоритма.
  4. Heap Sort
    • На основе какой структуры данных реализуется данный алгоритм?
    • Расскажите сам алгоритм.
    • Какова сложность алгоритма в среднем? А в худшем случае?
    • Напишите код для бинарного поиска.
  5. Binary Search Tree
    • Что такое граф, дерево?
    • Что такое бинарное дерево?
    • Опишите Binary Search Tree. В чем его отличие от кучи?
    • Как его можно реализовать?
  6. Поразрядная сортировка
    • Какие предположения о типе данных требуются?
    • Какие виды поразрядной сортировки известны?
    • Расскажите алгоритм.
    • Какова его сложность?
  7. Сортировка слиянием
    • Какова сложность этого алгоритма? Каковы затраты памяти?
    • Напишите код слияния отсортированных подмассивов.
  8. Сортировка Шелла.
    • Идея сортировки.
    • Лемма об h-сортировке k-упорядоченного файла.
    • Популярные последовательности.
  9. Список, стек, очередь
    • Что такое стек?
    • Что такое очередь?
    • Как эти типы данных можно реализовать?
  10. Жадные алгоритмы и динамическое программирование.
    • Примеры задач
    • Задача о расписании.
    • Варианты задачи о рюкзаке
    • LCS, нахождение длины и восстановление самой последовательности
    • Расстояние Левенштейна и его вариации
    • Алгоритм Хиршберга для LCS
  11. ООП
    • Что такое класс? Чем класс в С++ отличается от структуры? В чем отличие класса от объекта?
    • Основные понятия ООП.
    • Конструкторы/деструкторы.
    • Перегрузка методов. Сокрытие методов. Перегрузка стандартных операторов. Какие способы перегрузки операторов Вы знаете? Какие методы и операторы необходимы для использования типа в качестве параметра стандартного шаблонного контейнера?
    • Ключевые слова virtual и const.
    • Что такое срезка?
    • Множественное наследование.
  12. Исключения.
    • Какие методы сообщения об ошибках есть в языке?
    • Генерирование и перехват исключений.
    • throw-списки. Их изменение в переопределенных методах.
    • Обработка ошибок в конструкторах и деструкторах.
  13. Шаблоны.
  14. АТД «Очередь с приоритетом»
    • Чем отличаются понятия «абстрактный тип данных (АТД)» и «структура данных»
    • Опишите абстрактный тип данных «Очередь с приоритетом»
    • Опишите структуру данных «Двоичная куча»
    • Оцените среднее и худшее время выполнения операций
    • Приведите примеры задач, в которых естественно использовать АТД «Очередь с приоритетом»
    • Можно ли реализовать АТД «Очередь с приоритетом» на базе реализации сбалансированного дерева поиска?
    • Расскажите о стандартных реализациях кучи и очереди с приоритетом в STL.
  15. Последовательные контейнеры STL и адаптеры.
    • [code] Опишите список и приведите примерную реализацию операций ins ert и push_back.
    • Какие последовательные контейнеры Вы знаете? В чем их отличие? Как они устроены?
    • Что такое адаптер над контейнером STL? Зачем они нужны? Приведите известные Вам.
    • В чем отличие vector<bool> от bitset?
  16. STL: итераторы
    • Что такое итератор?
    • Какие бывают итераторы?
    • Чем принципиально отличаются итератор по элементам контейнера set и по элементам контейнера vector?
    • Какие функции и операторы должны быть определены для итератора по элементам двусвязного списка?
    • Что такое итератор с произвольным доступом?
  17. Устройство, основные операции и их стоимость, особенности использования vector.
  18. Устройство, основные операции и их стоимость, особенности использования list.
  19. Устройство, основные операции и их стоимость, особенности использования deque.
  20. Устройство, основные операции и их стоимость, особенности использования stack и queue.
  21. Устройство, основные операции и их стоимость, особенности использования map, se t.
  22. Устройство, основные операции и их стоимость, особенности использования bitset и vector<bool>.
  23. Устройство, основные операции и их стоимость, особенности использования unordered_map.
  24. Устройство, основные операции и их стоимость, особенности использования priority_queue.
  25. Сортировка и поиск в STL. В каких контейнерах элементы хранятся упорядоченно?
  26. Куча в STL. Алгоритмы STL.
  27. Длинная арифметика. Способы реализации. Алгоритм Карацубы.
  28. Матрицы и работа с ними.
  29. Геометрия на плоскости.
    • Определение расстояния до прямой, угла между прямыми, проверка пересечения отрезков
    • Построение выпуклой оболочки точек (алгоритмы Джарвиса, Грэхема).
    • Метод заметающей прямой и его применения.
    • Триангуляция Делоне.
    • Диаграмма Вороного.
  30. Графы. Деревья. Представление графов. Поиск в глубину и в ширину.
  31. Топологическая сортировка
  32. Сильно-связные компоненты. Алгоритм Косарайю.
  33. Ассоциативный массив. Интерфейс, варианты реализации.
  34. Хеш-таблицы.
    • Хеш-функции.
    • Способы разрешения коллизий – цепочки, открытое хеширование, кукушка.
  35. Красно-черные деревья. Основные операции.
  36. B-деревья. Основные операции. Применение на практике.
  37. Задачи кодирования. Коды Хаффмана.

 

 

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

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

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

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

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