ПИ 2020.1 Основы информатики экзамен - ПИ 2020 Основы информатики экзамен

Задача A. ПИ 2020 Основы информатики экзамен ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Входной файл:	Стандартный вход	Ограничение времени:	1 сек
Выходной файл:	Стандартный выход	Ограничение памяти:	512 Мб
Максимальный балл:	10

Условие

Устный экзамен.

Основы информатики

Общее устройство универсального компьютера. Архитектура фон-Неймана. Принцип хранимой программы. Гарвардская архитектура. Представление целых чисел. Прямое, обратное и дополнительное кодирование. Представление вещественных чисел. Проблемы точности вычислений. Абсолютная и относительная погрешность. Основные операторы (не операции!) языка C/С++. Скалярные типы данных языка C/С++. Операции и приоритеты в языке C/С++. Массивы и структуре в языке C/С++. Указатели и управление памятью в языке C/С++. Функции, передача параметров в языке C/С++.

Алгоритмы 1

Ответы на все вопросы должны включать:

Определения структур данных. Описания алгоритмов. Оценки затрат времени и памяти. Неформальные доказательства корректности и эффективности.

Поиск. Бинарный поиск, бинарный поиск строк. Интерполяционный поиск. Бинарный поиск по ответу. Тернарный поиск. Поиск в глубину, поиск в ширину, задачи на лабиринтах. Сортировка слиянием. Сортировка связных списков. Сортировка подсчётом, карманная (bucket) и поразрядная сортировка. Сортировка patience. Быстрая сортировка, порядковые статистики. Нахождение порядковой статистики за линейное в среднем время. Куча. Свойства, операции, построение. Очереди с приоритетами, сортировка кучей. Запросы суммы и минимума на отрезке. Частичные суммы, дерево минимумов. Деревья отрезков, операции обновления и поиска. Запросы суммы и минимума в многомерном случае. Поиск ближайшего общего предка. Простейшие структуры данных. Динамические массивы. Связные списки. Отображения. Хэш-таблицы. Подбор хэш-функции. Способы разрешения коллизий в хэш-таблицах: списки, открытая адресация. Перебор, перебор с возвратом, отсечения, метод ветвей и границ, альфа-бета-отсечение. Динамическое программирование. Принцип оптимальности Беллмана. Задачи о наибольшей общей/возрастающей подпоследовательности, порядке перемножения матриц. Восстановление ответа. Жадные алгоритмы. Эвристические применения. Задача о покрытии отрезка (выборе заявок). Динамическое программирование в пространстве ответа. Задачи о разрезании стержня, рюкзаке дискретном и непрерывном. Поиск подстрок. Префикс-функция. z-функция. Алгоритмы Кнута-Морриса-Пратта, Рабина-Карпа.