Задание 1 — граф и таблица смежности
Схема дорог нарисована буквами, таблица расстояний — независимо пронумерована. Сопоставьте буквы и номера по структуре связей, затем ответьте на вопрос.
Задание 2 — таблица истинности
Восстановите соответствие переменных столбцам частично заполненной таблицы истинности.
Ответ запишите подряд, например: yxwz.
Задание 3 — поиск в базе данных
Работайте с тремя связанными листами электронной таблицы и вычислите требуемый показатель.
Задание 4 — кодирование Фано / двоичное представление
Неравенство Крафта и правило Фано, либо перевод последовательности фиксированных двоичных кодов в другую систему счисления.
Задание 5 — системы счисления и обработка записи
Число переводится в другую систему счисления, запись обрабатывается по правилу, ищется наименьшее подходящее N.
Задание 6 — исполнитель Черепаха
Черепаха рисует на координатной плоскости одну или две фигуры, а также фигуры из дуг. Определите числовую характеристику полученной области.
Задание 7 — кодирование звука и изображений
Определите числовую характеристику аудио- или графического файла: объём, глубину кодирования, частоту дискретизации, разрешение, время передачи или соотношение при перезаписи.
Задание 8 — слова и числа: порядок и подсчёт
Слова из букв фиксированного алфавита или числа в позиционной системе счисления: найдите слово/число по номеру, номер по слову, или подсчитайте количество слов/чисел, удовлетворяющих условию.
Задание 9 — обработка числовой информации в электронных таблицах
В файле — таблица из большого числа строк с натуральными числами. Скачайте файл, обработайте его (в редакторе таблиц или программой) и определите, сколько строк удовлетворяет обоим условиям.
Задание 10 — IP-адреса и маски сети
Адрес сети, маска, широковещательный адрес, допустимые адреса узлов и подсчёт адресов по условиям.
Задание 11 — вычисление количества информации
Определите объём памяти, минимальную мощность алфавита или максимальную длину кода — с учётом того, что каждая запись занимает одинаковое и минимально возможное целое число байт.
Задание 12 — исполнитель МТ
Проследите работу машины Тьюринга по таблице команд и определите параметры исходной или полученной последовательности.
Задание 13 — количество программ исполнителя
Подсчитайте количество программ, преобразующих исходное число в требуемое, с учётом условий на команды и траекторию вычислений.
Задание 14 — системы счисления и арифметические выражения
Работайте с большими степенями, неизвестными цифрами и основаниями систем счисления.
Задание 15 — логические выражения с параметром A
Определите значение параметра A, при котором логическое выражение тождественно истинно.
Задание 16 — рекурсивные функции
Вычислите значение рекурсивной функции или восстановите значение n по заданному результату.
Задание 17 — обработка последовательности
Скачайте текстовый файл, обработайте последовательность и запишите два требуемых результата.
Задание 18 — Робот и электронная таблица
Динамическое программирование по клеточному полю: суммы, стены, финишные клетки и расход энергии.
Задания 19–21 — теория игр
У заданий 19, 20 и 21 одно общее условие. Можно решить только одно из них, любые два или все три.
Задание 19
Задание 20
Задание 21
Задание 22 — многопроцессорные системы
Обработка таблицы процессов, их длительностей и зависимостей.
Задание 23 — анализ взвешенного графа
Кратчайший путь в ациклическом ориентированном взвешенном графе, заданном текстовым файлом.
Задание 24 — обработка символьных строк
Обработка больших текстовых файлов: одна строка, много строк и корректные числовые выражения.
Задание 25 — обработка целочисленной информации
Два основных типа: поиск делителей и поиск чисел по маске.
Задание 26 — обработка больших наборов данных
Разные практические алгоритмы: журналы, интервалы, сортировка, жадные стратегии и двумерные данные.
Задание 27 — кластеризация
Работа с координатами точек: центры кластеров, нанокластеры, помехи и классификация звёзд.