Адрес 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] Опишите список и приведите примерную реализацию операций insert и push_back.
      • Какие последовательные контейнеры Вы знаете? В чем их отличие? Как они устроены?
      • Что такое адаптер над контейнером STL? Зачем они нужны? Приведите известные Вам.
      • В чем отличие vector<bool> от bitset?
    16. STL: итераторы
      • Что такое итератор?
      • Какие бывают итераторы?
      • Чем принципиально отличаются итератор по элементам контейнера set и по элементам контейнера vector?
      • Какие функции и операторы должны быть определены для итератора по элементам двусвязного списка?
      • Что такое итератор с произвольным доступом?
    17. Устройство, основные операции и их стоимость, особенности использования vector.
    18. Устройство, основные операции и их стоимость, особенности использования list.
    19. Устройство, основные операции и их стоимость, особенности использования deque.
    20. Устройство, основные операции и их стоимость, особенности использования stack и queue.
    21. Устройство, основные операции и их стоимость, особенности использования map, set.
    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. Задачи кодирования. Коды Хаффмана.

     

     

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

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