Читать. Думать. Пробовать.
Статьи по школьным предметам — страница 106
Объяснения по школьным предметам. В каждом — главная мысль, примеры и маленькая проверка себя.
Информатика
Fisher—Yates: почему случайный обмен требует правильной границы
Перемешивание Fisher—Yates: выбор из оставшегося диапазона, равномерность перестановок и ошибка обмена со всем массивом.
Разобраться и проверить себяИнформатика
Поток и разрез: как получить проверяемую верхнюю границу
Разрез сети как доказательство оптимальности: направленные ёмкости через границу, верхняя оценка потока и совпадение с допустимым решением.
Разобраться и проверить себяИнформатика
Полный сумматор: бит результата и перенос из трёх входов
Полный сумматор на трёх битах: младший бит суммы, перенос в соседний разряд и сложение многобитных беззнаковых чисел.
Разобраться и проверить себяИнформатика
Мост графа: удаление какого ребра разрывает связность
Мосты в неориентированном графе: удаление одного ребра, обходной путь, значения tin/low и осторожность с параллельными рёбрами.
Разобраться и проверить себяИнформатика
Синдром Хэмминга: как проверки указывают ошибочный разряд
Синдром кода Хэмминга (7,4): проверки чётности, нумерация позиций и граница исправления одной ошибки.
Разобраться и проверить себяИнформатика
ETag и 304: как проверить, можно ли повторно использовать представление
ETag и условный GET: сохранённое представление, If-None-Match, ответ 304 и отличие метки версии от содержимого страницы.
Разобраться и проверить себяИнформатика
Редирект: когда следующий запрос сохраняет метод и тело
Переход после отправки формы: чем 303 отличается от 307 и 308 и почему 301 или 302 могут изменить POST на GET.
Разобраться и проверить себяИнформатика
Сортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
Разобраться и проверить себяИнформатика
Пагинация по ключу: как стабильный порядок помогает продолжить выборку
Постраничная выдача по последнему ключу: уникальный порядок, составной курсор и ограничения при изменении каталога.
Разобраться и проверить себяИнформатика
LFU: частота обращений и правило разрешения равенства
LFU на короткой трассе: счётчики обращений, частота против недавности и явное правило для одинаковых частот.
Разобраться и проверить себяИнформатика
Логическое и побитовое И: когда вычисляется правый операнд
Логическое and и побитовое&в Python: значение операнда, короткое вычисление и независимое сравнение двоичных разрядов.
Разобраться и проверить себяИнформатика
Длиннейший путь в DAG: когда работает топологический порядок
Максимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.
Разобраться и проверить себяИнформатика
LRU: как последнее обращение меняет следующего кандидата на удаление
LRU на трассе запросов: порядок последнего использования, попадание и вытеснение, различие с FIFO и сроком годности.
Разобраться и проверить себяИнформатика
Локальность памяти: почему порядок обхода меняет обращения к строкам кэша
Временная и пространственная локальность памяти: собственные трассы обращений, размер блока и пределы предсказания.
Разобраться и проверить себяИнформатика
Слияние отсортированных частей: два указателя и стабильность
Слияние двух готовых массивов: сравнение первых оставшихся элементов, обработка хвоста и правило стабильности при равенстве.
Разобраться и проверить себяИнформатика
Дерево Меркла: как ветвь проверки связана с доверенным корнем
Доказательство включения в дерево Меркла: соседние хеши, порядок объединения и необходимость доверенного корня.
Разобраться и проверить себяИнформатика
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция строки: собственная граница, суффикс обработанного префикса и переход к более короткому совпадению.
Разобраться и проверить себяИнформатика
Процесс и поток: какие данные общие, а какие отдельные
Процесс и поток: общее адресное пространство, собственный ход исполнения и ошибка несогласованного обновления.
Разобраться и проверить себяИнформатика
План запроса: что показывает индексный поиск без обещания секунд
Как читать EXPLAIN QUERY PLAN в SQLite: SCAN, SEARCH, покрывающий индекс и проверка гипотезы на настоящем запросе.
Разобраться и проверить себяИнформатика
Порядковая статистика: найти k-й элемент без полной сортировки
Поиск k-го наименьшего элемента: локальный ранг после разбиения, повторяющиеся значения и выбор только нужной области.
Разобраться и проверить себяИнформатика
Разбиение около опорного: что гарантирует один шаг быстрой сортировки
Что делает разбиение около опорного элемента: области меньше, равно и больше, их инварианты и границы обещания одного шага.
Разобраться и проверить себяИнформатика
Поразрядная сортировка: зачем каждому проходу стабильность
LSD-сортировка по разрядам: проход от единиц к старшим цифрам, сохранение прежнего порядка и границы числовой модели.
Разобраться и проверить себяИнформатика
RANK и DENSE_RANK: откуда берутся пропуски номеров
Чем RANK отличается от DENSE_RANK: равные баллы, группы сверстников и пропуски мест на собственном примере.
Разобраться и проверить себяИнформатика
Рекурсивный CTE: начальные строки, шаг и условие остановки
Разбираем рекурсивный CTE на дереве учебных разделов: начальная строка, следующий уровень, остановка и защита от циклов.
Разобраться и проверить себяБольше о русском языке
Правописание, грамматика, разборы, слова и работа с текстом — в отдельной библиотеке.
