Информатика

Представление данных, алгоритмы и логика вычислений.

Синие фигурные скобки держат между собой оранжевый квадрат.

Решить и понять

Ответ с объяснением каждого шага

Подсеть IPv4 по адресу и префиксу

Сетевой адрес, маска, диапазон и число адресов без обращения к сети.

Попробовать

Объём данных и время передачи

Теоретическое время передачи с различием битов, байтов и двоичных единиц.

Попробовать

Таблица истинности

Построить таблицу для выражения до четырёх логических переменных.

Попробовать

Перевод целых между системами счисления

Перевод числа с основаниями от 2 до 36 с проверкой допустимых цифр.

Попробовать

Объём несжатого растрового изображения

Размер потока пикселей по ширине, высоте и глубине цвета без заголовков и сжатия.

Попробовать

Кратчайший путь поиском в ширину

Путь с минимальным числом рёбер в заданном невзвешенном графе, включая недостижимые вершины.

Попробовать

Порядок зависимостей и поиск цикла

Топологический порядок ориентированного ациклического графа либо конкретный замкнутый путь, мешающий такому порядку.

Попробовать

Сортировка вставками по шагам

Покажите отсортированный префикс после каждой вставки, число сдвигов и исходные номера равных элементов.

Попробовать

Расстояние редактирования с выравниванием

Минимальное число вставок, удалений и замен между двумя короткими строками и один оптимальный путь выравнивания.

Попробовать

Двоичное сложение с переносами

Беззнаковые двоичные числа: бит суммы и входящий/исходящий перенос для каждого разряда полного сумматора.

Попробовать

Двоичный поиск по шагам

Найти первое вхождение числа в отсортированном массиве и проследить сужение полуоткрытого интервала индексов.

Попробовать

Серии в двоичной строке: записать и восстановить

Сгруппировать подряд идущие нули и единицы, восстановить исходную последовательность и сравнить длины текстовых записей.

Попробовать

Исполнитель на поле: путь и первая запрещённая команда

Проследить команды N,E,S,W на прямоугольном поле с препятствиями; показать начальную клетку, каждый шаг и точное место остановки.

Попробовать

Вычитание в системе счисления: цепочка займа

Вычитаем две неотрицательные позиционные записи с основанием от 2 до 16 и показываем входящий и исходящий заём каждого разряда.

Попробовать

Копирование формулы: смешанные ссылки по двум направлениям

Переносим арифметическую формулу между клетками модели A1..ZZ10000, отдельно фиксируя столбец и строку; вычисление формулы не выполняется.

Попробовать

Дискретное преобразование Фурье короткого сигнала

Вычислить комплексные коэффициенты ДПФ, восстановить вещественную последовательность и проверить равенство энергий.

Попробовать

Линейная свёртка двух конечных сигналов

Получить полный отклик конечного фильтра, со всеми краевыми отсчётами и точными рациональными коэффициентами.

Попробовать

LZ78: словарь фраз и проверка восстановления

Разобрать короткую буквенную строку в пары «индекс префикса, новый символ», показать словарь и восстановить исходное сообщение.

Попробовать

CRC без отражения: остаток двоичного полинома

Построить учебное кодовое слово над GF(2), показав деление XOR и проверку нулевого остатка без скрытых параметров CRC-стандарта.

Попробовать

Максимальный поток и сертификат минимального разреза

По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.

Попробовать

Критический путь: ранние и поздние сроки работ

Рассчитать минимальную длительность проекта с зависимостями, резервы работ и все критические вершины в ациклической сети.

Попробовать

Компоненты сильной связности и граф конденсации

Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.

Попробовать

Число полных двудольных назначений: перманент по Райзеру

Посчитать все допустимые взаимно однозначные назначения по квадратной матрице совместимости 0/1, используя включения и исключения по подмножествам столбцов.

Попробовать

Эйлеров маршрут: каждое ребро ровно один раз

Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.

Попробовать

Транзитивная редукция зависимостей DAG

Удалить из ориентированной ациклической сети лишь те прямые дуги, для которых уже существует обходной направленный путь.

Попробовать

Реализовать степени простого графа методом Хавела — Хакими

Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.

Попробовать

Точное хроматическое число малого графа

Найти минимальное число цветов для простого графа до 8 вершин и предъявить допустимую раскраску, перебирая ограниченное число состояний.

Попробовать

Число остовных деревьев по теореме Кирхгофа

Посчитать все разные остовные деревья неориентированного графа точным определителем кофактора лапласиана.

Попробовать

Максимальный вес совместимых временных интервалов

Выбрать непересекающиеся полуоткрытые интервалы с максимальной суммой весов и показать динамическое сравнение включения и пропуска.

Попробовать

Арифметическое кодирование: точный интервал и двоичный префикс

Закодировать короткое сообщение с заданными положительными весами символов, сохранив точные границы и выбрав содержащийся двоичный интервал.

Попробовать

Линейный двоичный код: расстояние и ближайшие слова

По независимым строкам порождающей матрицы перечислить код, проверить минимальный вес и декодировать принятое слово с явным обнаружением ничьей.

Попробовать

Детерминизация НКА с ε-переходами

Построить достижимые состояния ДКА как множества состояний НКА и проверить короткое двоичное слово с учётом ε-замыканий.

Попробовать

Алгебраическая нормальная форма булевой функции

Перевести таблицу из 2ⁿ значений в единственную XOR-сумму мономов, определить алгебраическую степень и проверить обратное восстановление.

Попробовать

Кратчайшая линейная рекурсия конечного префикса над GF(p)

Восстановить минимальную длину линейной рекурсии для заданного конечного набора остатков по одному из малых простых модулей.

Попробовать

Изучать по порядку

Выберите тему — внутри объяснения, примеры и задания

Сортировки и сравнение строк

Различать шаг алгоритма, его инвариант и итог; проверять стоимость исправления строки.

10 тем с практикой

Графы, разрезы и динамические запросы

Отличать компоненту, разделяющее ребро, путь увеличения и структуру для обновляемых сумм.

10 тем с практикой

Запросы, ограничения и устойчивое чтение

Обосновывать результат SQL и его границы, не приписывая запросу неуказанный порядок или изоляцию.

10 тем с практикой

Интернет-протоколы и границы гарантий

Различать доставку, границы сообщений, подтверждение узла и правила чтения ответа браузером.

10 тем с практикой

Цифровая схема и работа вычислителя

Проверять перенос, порядок байтов, адрес и ожидание процесса без скрытых предположений о машине.

10 тем с практикой

Случайность, численные оценки и целостность

Объяснять равновероятность, устойчивую оценку, ошибку фильтра и проверку подлинности.

10 тем с практикой
Практика · вопросов: 236

Разобраться в теме

Объяснение, примеры и вопрос для себя

Как получить полный отклик конечного фильтра свёрткой

Вычислить линейную свёртку конечного сигнала с конечным импульсным откликом, сохранить края и отличить её от круговой.

Читать и практиковаться

Как получить CRC делением двоичных полиномов

Вычислить систематический CRC-остаток над GF(2), проверить делимость кодового слова и отличить учебную модель от параметризованного стандарта.

Читать и практиковаться

Как вычислить резервы работ двумя проходами по зависимостям

Определить ранние и поздние сроки работ ациклического проекта, общую длительность и резервы при неограниченной параллельности ресурсов.

Читать и практиковаться

Как вычислить ДПФ и проверить обратное восстановление

Вычислить комплексные спектральные коэффициенты конечного вещественного сигнала с явной нормировкой и проверить Parseval и обратное ДПФ.

Читать и практиковаться

Как проверить LZ78 по парам, словарю и завершающему хвосту

Разобрать сообщение жадным словарём LZ78, явно передать известный последний хвост и проверить декодирование без оценки выдуманной экономии байтов.

Читать и практиковаться

Как подтвердить максимальный поток минимальным разрезом

Найти поток увеличивающими путями, сохранить обратные остаточные дуги и проверить оптимальность равенством ёмкости разреза.

Читать и практиковаться

Матрица достижимости: как проверить сжатие ориентированного графа

Пошагово замыкаем матрицу смежности логическими переходами, выделяем взаимно достижимые группы и проверяем, почему путь между группами не всегда является прямой дугой конденсации.

Читать и практиковаться

Сообщение как вложенный интервал: что именно передают биты арифметического кода

Построить точный интервал арифметического кодирования короткого сообщения и найти целиком содержащийся в нём двоичный цилиндр.

Читать и практиковаться

Короткая рекурсия объясняет префикс, но не доказывает неизвестное продолжение

Найти минимальную линейную рекурсию конечной последовательности над малым простым полем, проверить знаки коэффициентов и границу прогноза.

Читать и практиковаться

Из таблицы истинности в XOR-многочлен: сначала закрепите порядок переменных

Построить единственную алгебраическую нормальную форму булевой функции преобразованием Мёбиуса и подтвердить её подстановкой на всех наборах.

Читать и практиковаться

CAP начинается с точных определений ответа и согласованности при разрыве связи

Разобрать невозможность одновременно гарантировать линеаризуемый регистр и доступность на обеих сторонах сетевого разделения в асинхронной модели.

Читать и практиковаться

Минимум цветов требует двух доказательств: раскраски и отказа меньшего числа

Найти точное хроматическое число малого простого графа ограниченным полным поиском и предъявить проверяемую раскраску.

Читать и практиковаться

Конфликтный граф транзакций: цикл запрещает перестановку в последовательное расписание

Построить граф предшествования операций транзакций и проверить конфликтную сериализуемость по наличию цикла, отделяя её от более общих критериев эквивалентности.

Читать и практиковаться

Какая стрелка зависимости лишняя: сохранение всех достижимых пар

Построить транзитивную редукцию DAG и проверить, что удаление прямых избыточных дуг сохранило все направленные зависимости по путям.

Читать и практиковаться

Чётной суммы мало: как построить граф по заданным степеням

Проверить графичность списка степеней и построить одну помеченную реализацию простого графа методом Хавела — Хакими.

Читать и практиковаться

Как стек Хиерхольцера собирает маршрут из использованных рёбер

Построить эйлеров маршрут стеком Хиерхольцера и независимо проверить точное совпадение мультимножества пройденных и исходных рёбер.

Читать и практиковаться

FLP ограничивает гарантированное завершение консенсуса, а не запрещает все решения

Правильно сформулировать невозможность детерминированного асинхронного консенсуса при одном возможном crash-отказе и отделить безопасность от живости.

Читать и практиковаться

Объединение HyperLogLog сливает регистры, а не складывает оценки

Объяснить идемпотентное объединение совместимых HyperLogLog-эскизов по покоординатному максимуму и границы оценки мощности пересекающихся множеств.

Читать и практиковаться

Ближайшее кодовое слово и гарантированное исправление — разные утверждения

Перечислить малый двоичный линейный код, установить минимальное расстояние и показать все ближайшие к принятому слову варианты без скрытого выбора.

Читать и практиковаться

История общего регистра: найдите последовательный порядок внутри интервалов операций

Проверить линеаризуемость короткой истории чтений и записей регистра, сохраняя порядок неперекрывающихся операций и последовательную спецификацию.

Читать и практиковаться

Теорема Майхилла — Нероуда: конечные классы продолжений строят минимальный автомат

Доказать эквивалентность регулярности конечности классов правой конгруэнции и построить канонический минимальный ДКА по классам продолжений.

Читать и практиковаться

Один шаг ДКА хранит сразу все возможные состояния НКА

Детерминизировать двоичный недетерминированный автомат с ε-переходами, строя только достижимые подмножества и проверяя принадлежность слова.

Читать и практиковаться

Сколько полных назначений разрешает совместимость: перманент без знаков перестановок

Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.

Читать и практиковаться

Лемма о накачке: разбиение выбирает противник, а степень выбираете вы

Построить корректное доказательство нерегулярности языка по лемме о накачке, сохраняя порядок кванторов и охватывая все допустимые разбиения.

Читать и практиковаться

С чего начать

В информатике полезно различать значение, его запись и правило обработки. Одно число можно записать в разных системах счисления: от этого количество предметов не меняется. Начните с двоичной записи, где каждая позиция имеет свой вес. Пошаговая проверка результата помогает понять запись, не заучивая таблицу переводов.

Полезные ориентиры

Частые вопросы

Число и его запись — одно и то же?

Значение может быть одним, а записи — разными. Например, десятичная и двоичная записи обозначают одно количество при правильно указанном основании.

Как проверить перевод системы счисления?

Разложите полученную запись по весам разрядов и сложите вклады. Для обратной проверки переведите результат обратно другим способом.

Выбрать другой предмет