Алгоритмы, компиляторы и сети

Алгоритмы, компиляторы и сети: графы, LL(1), SSA, IPv4, TCP, DNS и маршрутизация. Авторские разборы и инструменты для своих данных.

В цепочке A→B→C кратчайший путь A→C содержит два ребра, хотя в матрице можно проверить наличие прямого ребра одной операцией. Представление данных меняет стоимость операций, но не меняет вопрос задачи. Поэтому алгоритм выбирают вместе с моделью входа и требуемым результатом.

Здесь доступны графы, поиск и сравнение строк, точные графовые сертификаты, двоичные представления и автоматы. Для начала полезно решить одну задачу вручную, сформулировать инвариант и только затем оценить время. Совпадение на примере проверяет запуск; корректность требует рассуждения обо всех допустимых входах.

Основные идеи

Представление графа

Список смежности хранит соседей каждой вершины, матрица — значение для каждой пары. При n вершинах матрица занимает порядок n² ячеек, а списки — порядок n+m при m рёбрах. Выбор зависит от нужных запросов.

Для длинной редкой цепочки список хранит почти по одному ребру на вершину, а матрица всё равно содержит квадратное число позиций.

Инвариант обхода в ширину

В невзвешенном графе BFS обрабатывает вершины по неубыванию расстояния в рёбрах от старта. При первом обнаружении вершины записывается кратчайшая длина. Для произвольных весов эта гарантия не переносится.

Если A связана с B и C, а обе — с D, расстояния от A равны 0,1,1,2 независимо от порядка B и C в очереди.

Ответ и сертификат

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

Раскраска четырьмя цветами доказывает верхнюю границу 4, но без нижней границы не доказывает, что трёх цветов недостаточно.

Основные методы

Беллман–Форд: где отрицательный цикл действительно портит ответ

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

Перед началом: Ориентированный взвешенный граф; Обход достижимых вершин; Инвариант и оценка сложности.

Три разных состояния вершины

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

Маршрут допускает повторение рёбер. Отрицательность отдельного ребра без отрицательного цикла не мешает конечному минимуму. Обозначения различаются: конечное число, +∞ для недостижимости и −∞ для неограниченного уменьшения. Символ −∞ не является очень большим отрицательным числом, пригодным для восстановления обычного кратчайшего пути.

Релаксация строит гарантию по числу рёбер

Инициализируем расстояние старта нулём, остальные значения бесконечностью. Для ребра u→v проверяем, улучшает ли d[u]+w(u,v) текущее d[v]. Сравнение выполняется только при достижимом u. Иначе арифметика с условным машинным числом вместо бесконечности способна породить ложный путь. При улучшении запоминаем предшественника, если планируется восстановление конечного маршрута.

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

Почему нужны дополнительный проход и обход потомков

Если отрицательных циклов на подходящих маршрутах нет, конечный оптимальный маршрут можно очистить от повторных вершин. Он содержит не больше |V|−1 рёбер. После стольких полных проходов дальнейшее улучшение служит свидетельством достижимого отрицательного цикла. При проверке надо снова исключить недостижимые начала рёбер: цикл в отдельной компоненте к запросу от данного старта отношения не имеет.

Соберите вершины, которые ещё можно улучшить, и обойдите из них исходящие рёбра. Все достигнутые вершины получают состояние отсутствия конечного минимума. Распространять метку против направления рёбер нельзя. Сам старт может остаться конечным, если из отрицательного цикла к нему нет пути. Одного сообщения «цикл найден» недостаточно, если пользователь спрашивает расстояния до нескольких конкретных целей.

Проверьте остановку и формат результата

Полный проход без единого улучшения означает, что все достижимые оценки уже стабилизировались; можно остановиться раньше. Но отсутствие улучшения на одном ребре или у выбранной цели этого не гарантирует. Классическая верхняя оценка времени — O(|V||E|). Дополнительный обход влияния цикла занимает O(|V|+|E|) при хранении списков смежности.

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

Цикл влияет на одну ветвь, но не на другую

Условие. Старт S. Рёбра: S→A:4, A→B:2, B→A:−5, B→C:1, C→T:2, S→U:7, X→Y:−2, Y→X:1. Других рёбер нет.

  1. Цикл A→B→A имеет вес 2−5=−3 и достижим из S.
  2. Из этого цикла достижимы C и T, поэтому A,B,C,T не имеют конечного минимума.
  3. Маршрут до T с k обходами цикла имеет вес 4−3k+2+1+2=9−3k.
  4. До U есть только ветвь S→U весом 7; обратно к S цикл не ведёт. X и Y из S недостижимы.

Ответ. d(S)=0, d(U)=7; для A,B,C,T значение −∞; для X,Y значение +∞.

Проверка. Последовательность 9−3k не ограничена снизу. Отдельный отрицательный цикл X→Y→X не влияет на запрос: пути из S к нему нет.

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

Кратчайшие пути и достижимые отрицательные циклы

Ориентированный граф: до 12 вершин и 60 дуг. Имена латиницей, например S A B. Каждая строка дуг: откуда куда целый вес. Отсутствующий путь отличается от пути без конечного минимума.

Данные для расчёта

Проверьте понимание

Из S достижим отрицательный цикл. До U есть путь из S, но из цикла до U пути нет. Обязательно ли d(U)=−∞?

Вопросы к этой главе

Может ли цель быть достижима и всё же не иметь кратчайшего маршрута?

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

Почему недостижимое отрицательное ребро нельзя релаксировать?

Его начало не имеет маршрута от старта. Прибавление веса к условной бесконечности не создаёт такого маршрута.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 6.006, Lecture 16: Bellman–Ford

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

Динамическое программирование: состояние важнее порядка циклов

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

Перед началом: Массивы и вложенные циклы; Максимум конечного набора; Индукция по обработанным объектам.

Одна строка программы может разрешить лишние предметы

Есть один предмет веса 2 и ценности 4, вместимость равна 6. Для рюкзака без повторений ответ не больше 4. Если одномерную таблицу обновлять по возрастанию вместимости, можно получить значения 4,8,12 для вместимостей 2,4,6. Программа отработает без ошибки доступа к памяти, но возьмёт один предмет трижды. Ошибка находится в смысле состояния, а не в арифметике.

Начнём с полной таблицы F_i(c): лучшая ценность предметов среди первых i при суммарном весе не больше c. Предметы различимы, каждый разрешён не более одного раза, веса положительны и целочисленны. Пустой выбор допустим. Эти соглашения объясняют нулевую начальную строку и не позволяют незаметно заменить задачу точного заполнения задачей с ограничением сверху.

Переход доказывается разбиением допустимых решений

Решение либо не содержит предмет i, либо содержит его ровно один раз. В первом случае значение ограничено F_(i−1)(c). Во втором после удаления предмета остаётся вместимость c−w_i и только предыдущие предметы: получаем v_i+F_(i−1)(c−w_i). Выбираем максимум допустимых ветвей. Если w_i>c, второй ветви нет. Это доказательство одновременно показывает, какие индексы должны стоять справа.

Корректность получается индукцией. Начальная строка описывает единственный пустой выбор. Если предыдущая строка верна, каждое допустимое решение попадает в одну из двух ветвей, а каждое решение, построенное переходом, допустимо. Поэтому максимум не пропускает лучший вариант и не добавляет невозможный. Для задачи с обязательным точным весом базу меняют: недостижимые веса помечают невозможными, а не нулевой ценностью.

Сжатие памяти требует нового инварианта

Две строки можно заменить одной, если пройти c от W вниз до w_i. Тогда ячейка c−w_i ещё хранит значение до обработки текущего предмета. Обновление dp[c]=max(dp[c],dp[c−w_i]+v_i) использует предмет только один раз. Сохранение прежнего слоя становится обязанностью порядка обхода, которую раньше обеспечивал отдельный индекс i.

При проходе вверх источник dp[c−w_i] уже мог измениться с помощью того же предмета. Такой порядок подходит некоторым задачам с неограниченным повторением, но не нашей. Универсального правила «динамику всегда считают слева направо» нет. Направление зависит от графа зависимостей и того, какую версию значения требует правая часть перехода. Изменение цикла проверяют на маленьком контрпримере до запуска большого набора.

Ответ, восстановление и реальная сложность

После вычисления значения нужно восстановить набор. В полной таблице сравнивают F_i(c) с F_(i−1)(c): если выбран предмет, переходят к предыдущей строке и уменьшают вместимость. При равенстве ветвей можно выбрать любую согласованную. Хранить только изменяемый указатель в сжатой таблице опасно: поздние обновления способны испортить историю, по которой восстанавливается набор.

Таблица содержит порядка nW состояний и столько же простых переходов. Это псевдополиномиальное время: вместимость W записывается примерно log₂W битами, поэтому линейность по самому W не означает полиномиальность по длине входа. Память для значений можно уменьшить до O(W), но выбранный способ восстановления тоже должен быть включён в оценку. Сначала докажите состояние, потом сокращайте таблицу.

Проверяем таблицу перечислением наборов

Условие. Вместимость W=6. Три предмета имеют пары (вес,ценность): (2,4), (3,5), (4,7). Повторов нет.

  1. После первого предмета при c=0,…,6 строка равна 0,0,4,4,4,4,4.
  2. После второго предмета строка становится 0,0,4,5,5,9,9.
  3. После третьего предмета строка равна 0,0,4,5,7,9,11.
  4. Значение 11 получено предметами весов 2 и 4. Их суммарный вес 6; пара весов 3 и 4 уже недопустима.

Ответ. Максимальная ценность 11, выбираются первый и третий предметы.

Проверка. Допустимые непустые наборы имеют ценности 4,5,7,9,11. Остальные пары и тройка превышают вместимость. Верхний результат таблицы совпадает с полным перебором.

Где легко ошибиться. Одинаковая формула присваивания с другим порядком обхода может решать другую задачу. Сжатие памяти не освобождает от доказательства версий читаемых ячеек.

Проверьте понимание

Один предмет (вес 2, ценность 4), W=6. Что выдаст неверный для 0/1-рюкзака проход вместимости вверх?

Вопросы к этой главе

Почему начальная строка здесь вся нулевая?

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

Достаточно проверить только итоговое число?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Stanford CS161, Lecture 13: zero-one knapsack

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

Хеш-таблица: что именно амортизируется при увеличении размера

Отделяем стоимость коллизий от стоимости переноса элементов и проверяем суммарную работу на последовательности вставок.

Перед началом: Хеширование и коллизии; Сумма геометрической прогрессии; Асимптотическая оценка последовательности операций.

Дорогая вставка не опровергает хорошую суммарную оценку

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

Амортизированная оценка относится к полной последовательности допустимых операций. Она распределяет редкие дорогие действия между многими дешёвыми и не требует случайного выбора момента наблюдения. Это не среднее по измеренному тестовому набору. Обещание должно включать начальное состояние и политику изменения ёмкости: произвольная предварительно заполненная структура может уже содержать будущий долг по переносу.

Удвоение ограничивает суммарное число переносов

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

При старте с постоянной ёмкости размеры переносов образуют последовательность 4,8,16,… . Сумма этих чисел до последнего переноса меньше удвоенного последнего размера. Поэтому для n вставок суммарные переносы имеют порядок O(n), как и сами размещения новых ключей. Одна перестройка остаётся линейной. Амортизация ограничивает общую работу, а не отменяет отдельную задержку интерфейса или сервиса.

Коллизии требуют отдельного предположения

Ожидаемая стоимость поиска в таблице с цепочками имеет порядок O(1+α), где α=n/m. Такой вывод опирается на подходящую модель распределения хешей. Постоянная загрузка без этого предположения не мешает всем ключам попасть в одну цепочку. Удвоение таблицы само по себе не исправляет плохую хеш-функцию и не доказывает устойчивость к специально подобранным ключам.

Поэтому выражение «ожидаемое амортизированное постоянное время» содержит две разные части. Ожидание связано с коллизиями, амортизация — с перестройками. Для длинных строк вычисление хеша и проверка равенства также требуют времени по длине ключа; считать их единичными действиями можно только в явно выбранной модели. Перенос сохранённого хеша и повторное хеширование строки дают разные практические затраты.

Удаления не должны немедленно отменять расширение

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

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

Десять вставок и две перестройки

Условие. Пустая таблица имеет ёмкость 4. Перед превышением ёмкости она удваивается. Вставляем десять разных ключей; считаем одно размещение нового или переносимого ключа за единицу.

  1. Первые четыре ключа требуют четыре размещения без переноса.
  2. Перед пятым ключом ёмкость увеличивается до 8: переносятся четыре старых ключа.
  3. Перед девятым ключом ёмкость увеличивается до 16: переносятся восемь старых ключей.
  4. Десять новых ключей плюс двенадцать переносов дают 22 размещения; итоговая загрузка равна 10/16.

Ответ. 22 размещения, из них 12 повторных; конечная ёмкость 16.

Проверка. Перестройки произошли только перед вставками 5 и 9. В подсчёт не включены сравнения, вычисление хешей и инициализация массива: это явно выбранная единица работы.

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

Проверьте понимание

При тех же правилах ёмкости 4 сколько ключей переносится за первые девять вставок?

Вопросы к этой главе

Почему увеличение на одну ячейку хуже удвоения?

При каждом новом ключе пришлось бы переносить почти весь текущий набор. Сумма переносов 1+2+…+n имеет квадратичный порядок.

Ожидаемое и амортизированное время — одно понятие?

Нет. Первое усредняет по вероятностной модели, второе ограничивает суммарную стоимость последовательности операций. Они могут одновременно участвовать в одной оценке.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 6.006, Lecture 9: Hashing II

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

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

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

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

Одно дерево может проиграть по другому критерию

Пусть рёбра AB и BC имеют вес 2, а AC — вес 3. Самая дешёвая связная сеть из этих рёбер использует AB и BC и стоит 4. Но путь от A до C по ней имеет длину 4, хотя в исходном графе есть прямое ребро длины 3. Никакого противоречия нет: минимизировались разные величины.

Минимальный остов соединяет все вершины и минимизирует сумму весов выбранных рёбер. Дерево кратчайших путей фиксирует источник и сохраняет кратчайшее расстояние от него до каждой достижимой вершины. Сумма рёбер такого дерева не обязана быть минимальной. При равных оптимальных расстояниях возможны разные деревья, поэтому даже слово «дерево» не делает критерии одинаковыми.

Уточните модель задачи до выбора алгоритма

Для остова рассматриваем связный неориентированный граф. Дерево содержит ровно |V|−1 ребро и не имеет циклов. Если граф несвязен, общего остова нет, но можно искать минимальный остовный лес по компонентам. Выделенного источника в этой постановке нет: выбор вершины для запуска алгоритма Прима не меняет сам критерий минимальности сети.

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

Почему жадный шаг остова безопасен

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

Проверка опирается на обмен. Добавим выбранное ребро к остову, где его нет: возникнет цикл. На этом цикле есть другое ребро, пересекающее тот же разрез. Его удаление восстанавливает дерево, а вес не увеличивается. Алгоритмы Прима и Краскала используют этот принцип, сохраняя возможность дополнить уже выбранные рёбра до оптимального дерева. Для произвольного дешёвого ребра без проверки циклов такой гарантии нет.

Выберите проверяемый сертификат ответа

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

Для дерева кратчайших путей сложите веса вдоль пути от источника до каждой вершины и сравните с расстояниями исходного графа. Стоимость прокладки сети и длины маршрутов — разные критерии. Если важны оба, сначала задайте целевую функцию и ограничения. Совпадение оптимумов в конкретном графе возможно, но не гарантировано.

Полный перебор трёх деревьев

Условие. В неориентированном графе веса AB=2, BC=2, AC=3. Сравнить минимальный остов и дерево кратчайших путей от A.

  1. Возможные деревья: AB+BC весом 4, AB+AC весом 5, BC+AC весом 5.
  2. Минимальный остов использует AB и BC, его вес 4.
  3. В исходном графе d(A,B)=2, d(A,C)=3: прямой путь к C короче пути через B весом 4.
  4. Поэтому дерево кратчайших путей от A содержит AB и AC. Его суммарный вес 5.

Ответ. Минимальный остов весит 4; дерево кратчайших путей от A весит 5 и даёт расстояния 0,2,3.

Проверка. Путь A→C в минимальном остове имеет вес 4 и не сохраняет исходное расстояние 3. Перебор всех трёх деревьев подтверждает минимальность суммы 4.

Где легко ошибиться. Слова «минимальный путь» и «минимальный остов» нельзя заменять друг другом. В первом случае складывают рёбра конкретного маршрута, во втором — всей выбранной сети.

Проверьте понимание

Если минимальный остов имеет наименьшую сумму рёбер, что гарантируется для пути между двумя его вершинами?

Вопросы к этой главе

Могут два вида дерева совпасть?

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

Нужно ли выбирать старт для самого определения остова?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 6.046J, Lecture 12: minimum spanning trees

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

  • MIT 6.006, Lecture 16: shortest paths

    Для различения расстояния от источника и общей стоимости сети; не является источником разобранного графа.

Компиляторы

Лексер: самое длинное совпадение и приоритет правил

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

Перед началом: Регулярные выражения; Полуоткрытые интервалы индексов; Различие символа, лексемы и токена.

Ключевое слово может быть только началом идентификатора

В учебном языке есть ключевое слово in, идентификаторы из строчных латинских букв и цифр, а также операторы <, <=, = и ==. Строка inside<=27==x2 должна начинаться одним идентификатором inside. Если сначала узнавать любое ключевое слово по префиксу, получится ошибочное разбиение на in и side. Лексер обязан сравнить длины допустимых совпадений из текущей позиции.

Токен содержит категорию и, при необходимости, значение или ссылку на лексему. Сама лексема — конкретный кусок исходного текста. Два разных идентификатора имеют одну категорию, но разные написания. Операторы сравнения могут иметь разные категории. Нельзя восстановить исходную программу из одних названий категорий, поэтому для диагностики сохраняют также диапазон исходных символов и соглашение о координатах.

Длина выбирается раньше приоритета

Правило longest match выбирает самый длинный префикс, который подходит хотя бы одному правилу токенов. Только если несколько категорий распознают одну и ту же максимальную длину, применяется заранее установленный приоритет. Поэтому слово in целиком может стать ключевым словом вместо идентификатора, но более длинное inside не должно проиграть короткому ключевому префиксу.

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

Автомат должен помнить последнее принятие

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

Пробелы и комментарии тоже распознаются по установленным правилам, хотя могут не попадать в поток токенов. Строковые литералы и комментарии иногда требуют отдельных состояний сканера. Не следует удалять все пробелы заранее: это может склеить два идентификатора и испортить номера строк. Для примера используем ASCII, поэтому индекс символа не конфликтует с многобайтовой кодировкой; в реальном редакторе эти единицы нужно согласовать.

Ошибка обязана сохранять продвижение и контекст

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

Правило, выдающее обычный токен без потребления символов, способно зациклить сканирование. Конец ввода поэтому обрабатывается отдельным соглашением, а не бесконечной последовательностью пустых лексем. После реализации проверьте склейку полученных диапазонов, граничные операторы и пары «ключевое слово — его продолжение». Такие короткие тесты обнаруживают неправильный порядок правил лучше, чем один большой корректный исходник.

Пять токенов из четырнадцати символов

Условие. Правила: ID=[a-z][a-z0-9]*, INT=[0-9]+, ключевое слово in, операторы <,<=,=,==. Разобрать inside<=27==x2; индексы с нуля, интервалы полуоткрытые.

  1. В позиции 0 longest match даёт ID inside на [0,6); короткое ключевое слово in не выбирается.
  2. На [6,8) выбирается <=, затем INT 27 на [8,10).
  3. На [10,12) выбирается ==, а не два отдельных =.
  4. Последний ID x2 занимает [12,14). Все диапазоны идут подряд и покрывают исходную строку.

Ответ. ID(inside), <=, INT(27), ==, ID(x2).

Проверка. Длины 6+2+2+2+2 дают 14. Отдельная строка in при равной длине правил должна получить категорию ключевого слова по приоритету.

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

Проверьте понимание

При правилах ID и ключевом слове in как следует распознать inside?

Вопросы к этой главе

Лексер проверяет, объявлено ли имя inside?

Нет. Он распознаёт форму идентификатора. Связь использования с объявлением проверяет последующий семантический анализ.

Почему нельзя просто разделить исходник по пробелам?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Stanford CS143, Lecture 4: lexical specification

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

FIRST, FOLLOW и LL(1): куда поставить пустую продукцию

Строим таблицу для собственной грамматики и получаем конфликт не по общему префиксу, а через nullable и FOLLOW.

Перед началом: Контекстно-свободная грамматика; Вывод строки; Множества и неподвижная точка.

Один символ просмотра выбирает продукцию

Для грамматики S→aAB|b, A→cA|@, B→d|@ символ @ обозначает пустую строку. При входном a начальное правило выбирается сразу, но после него A может либо породить несколько c, либо исчезнуть. Чтобы решить, когда исчезновение допустимо, недостаточно посмотреть только на первые символы правых частей A. Нужна информация о том, что разрешено после A.

LL(1) описывает левосторонний вывод при чтении слева направо с одним токеном просмотра. Один токен не обязательно равен одному символу исходного файла, но в нашей лаборатории терминалы односимвольные. Таблица должна назначать не более одной продукции каждой паре «нетерминал, следующий терминал». Пустая ячейка означает отсутствие допустимого выбора для этой пары, а несколько правил в одной ячейке — конфликт.

FIRST относится к целой последовательности

FIRST последовательности содержит терминалы, с которых могут начинаться порождённые ею строки. Пустота включается, если исчезнуть может вся последовательность. Для AB сначала берут FIRST(A) без пустоты, а если A nullable, добавляют FIRST(B). Остановиться после первого символа правой части было бы ошибкой: nullable-префикс позволяет следующему нетерминалу определить начало строки.

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

FOLLOW не содержит пустую строку

FOLLOW(A) содержит терминалы, которые могут идти сразу после A в выводе из стартового символа. Для стартового символа добавляется маркер конца $. Если в правиле после A стоит последовательность β, добавляют FIRST(β) без пустоты. Когда β может исчезнуть, дополнительно передают FOLLOW левой части правила. Это распространение тоже продолжают до устойчивого состояния.

Пустота не является очередным входным символом и не добавляется в FOLLOW. Для правила A→α запись в таблице выполняют по FIRST(α) без пустоты. Если α nullable, то то же правило добавляют в столбцы FOLLOW(A), включая конец ввода при его наличии. Поэтому пустая продукция действует по контексту продолжения, а не по воображаемому символу @ во входной строке.

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

В нашей грамматике FOLLOW(A) содержит d и $, поскольку B может либо дать d, либо исчезнуть. Следовательно, A→@ занимает соответствующие два столбца. Если добавить альтернативу A→d, ячейка для A и d получит уже два кандидата. Один предлагает начать d внутри A, другой — закончить A и оставить d для B. Автоматическое предпочтение первого скроет проблему грамматики.

Конфликт доказывает, что данная грамматика не подходит для этой таблицы LL(1), но сам по себе не доказывает неоднозначность языка. Иногда помогают преобразования грамматики, иногда нужен другой метод разбора. Лаборатория вычисляет FIRST, FOLLOW, таблицу и конфликты; она не исполняет программу и не проверяет конкретную входную цепочку как готовый парсер. Это граница демонстрации, которую важно не расширять по одному успешному расчёту множеств.

Три нетерминала и семь заполненных ячеек

Условие. Ввести S→aAB|b; A→cA|@; B→d|@. Старт S, @ — пустота, $ — конец ввода.

  1. FIRST(A)={c,@}, FIRST(B)={d,@}, FIRST(S)={a,b}.
  2. FOLLOW(S)={$}; FOLLOW(B)={$}; FOLLOW(A)={d,$}.
  3. Строка S: по a выбрать aAB, по b выбрать b. Строка A: по c выбрать cA, по d или $ выбрать @.
  4. Строка B: по d выбрать d, по $ выбрать @. Имеется семь заполненных ячеек без конфликтов.

Ответ. Грамматика LL(1). Добавление альтернативы A→d создаст конфликт в ячейке (A,d).

Проверка. Число ячеек: две для S, три для A, две для B. Маркер @ присутствует в FIRST nullable-символов, но не в FOLLOW.

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

FIRST, FOLLOW и таблица LL(1)

До шести нетерминалов A–Z и 15 правил. Каждый символ — отдельный токен: a–z, 0–9, (, ), + или *. Запись S -> a A | @; @ — пустая цепочка, $ — конец входа. Это анализ грамматики: программы и правила как код не запускаются.

Данные для расчёта

Проверьте понимание

Какая дополнительная альтернатива создаёт конфликт в (A,d) разобранной грамматики?

Вопросы к этой главе

Почему FOLLOW(A) содержит конец ввода?

В правиле S→aAB следующий B может исчезнуть, после чего A окажется последним символом выводимой строки. Поэтому к нему передаётся FOLLOW(S).

Одна непустая ячейка с двумя правилами допустима?

Для детерминированной таблицы LL(1) это конфликт. Нужно показать оба правила и причину их появления, а не молча сохранить первое.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Stanford CS143, Lecture 7: predictive parsing

    Проверка правил FIRST/FOLLOW и заполнения LL(1)-таблицы. Грамматика и дополнительный конфликтующий вариант составлены отдельно.

Области видимости и типы: имя ещё не обозначает одну переменную

Разрешаем затенённое имя по объявлению и проверяем тип инициализатора до вычисления примера.

Перед началом: Блоки программы; Синтаксическое дерево; Целочисленный и логический тип.

Одинаковое написание связывает разные объявления

Внешнее n может иметь тип int, а вложенное n — тип bool. Это не обязательно ошибка: язык может разрешать затенение в новом блоке. При каждом использовании компилятор должен установить конкретное объявление, а затем взять тип именно из него. Поиск одного глобального словаря по написанию имени смешал бы две независимые переменные и испортил проверку корректной программы.

Для примера зададим язык явно: объявления видны после вычисления своего инициализатора, одинаковое имя в одном блоке запрещено, а вложенное затенение разрешено. Условие if требует bool; сложение требует int и не приводит bool к числу. Эти соглашения учебные. Другой язык может вводить объявление раньше, иметь отдельные пространства имён или разрешать иные преобразования типов.

Стек окружений делает выбор воспроизводимым

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

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

Тип выражения выводится из его операции

Для сравнения двух целых можно получить bool. Для сложения двух целых получается int. Объявленный тип переменной проверяется против типа инициализатора, а при присваивании — против типа правой части. Одного факта, что программа синтаксически разобрана, недостаточно: дерево n+1 имеет правильную форму и может оказаться неверным по типам, если связанное n логическое.

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

Диагностика должна показывать выбранное объявление

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

При проверке собственной реализации создайте пару случаев с одинаковым написанием и разной областью действия. Затем измените только правило видимости инициализатора и проверьте, где меняется связь. Такая проверка исследует семантику языка, а не удачную последовательность значений. Ещё один полезный тест — выход из вложенного блока: внутреннее имя не должно случайно оставаться последним значением в общей таблице символов.

Внутренний bool создаётся из внешнего int

Условие. По правилам главы: let n:int=4; затем вложенный блок let n:bool=(n<6); if(n){let z:int=2;}; после выхода n=n+1.

  1. Во внешнем окружении появляется объявление n:int со значением 4.
  2. Во внутреннем инициализаторе новое n ещё не видно. Выражение использует внешний int: 4<6 даёт bool true.
  3. После инициализации внутреннее n связывается с bool и подходит для условия if. z существует только в своём блоке.
  4. После выхода внутреннее объявление исчезает из поиска. Последнее n+1 использует внешний int и даёт 5.

Ответ. Программа корректна в заданном учебном языке; итоговое внешнее n:int равно 5.

Проверка. Выражение n+1 внутри области внутреннего n было бы ошибкой bool+int. Тот же текст после выхода из блока корректен, потому что ссылается на другое объявление.

Где легко ошибиться. Не переносите правило одного языка на все остальные. Момент видимости объявления и разрешённые преобразования типов задаются спецификацией языка.

Проверьте понимание

Почему n+1 в примере корректно после блока, но некорректно внутри него после объявления bool?

Вопросы к этой главе

Затенение меняет тип внешней переменной?

Нет. Создаётся другое объявление с тем же написанием. Внешнее остаётся прежним и снова доступно после выхода из вложенной области.

Можно определить тип имени только по его текущему значению?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

IR и SSA: какое значение приходит из каждой ветви

Переводим ветвление в промежуточное представление и проверяем φ по предшественнику, а не по текстовому порядку строк.

Перед началом: Базовый блок и граф управления; Присваивание и использование значения; Условное ветвление.

Переименование не устраняет вопрос о ветвлении

Пусть при условии p переменная x получает a+2, иначе a−3; затем вычисляются y=x·4 и x=y+1. Простая замена каждого присваивания новым именем создаст два кандидата для первого использования x после ветвей. Нельзя взять последний по расположению в файле: программа проходит только по одной ветви, и текстовый порядок не задаёт реально пришедшее значение.

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

Одно определение относится к имени в тексте IR

В форме SSA каждое имя значения имеет одно определяющее место. Изменение исходной переменной создаёт новую версию: x₁, x₂ и так далее. Это не обещание, что инструкция в цикле выполнится лишь однажды во время запуска. Одно текстовое определение может вычисляться много раз, а экземпляры исполнения следуют правилам графа управления.

Обычное определение должно доминировать над своим использованием: каждый путь от входа к этому месту проходит через определяющий блок. Две разные ветви по отдельности не доминируют над общим продолжением. Поэтому в точке слияния вводится φ с парами «предшественник, значение». Выбор определяется тем ребром, по которому выполнение вошло в блок, а не повторным вычислением исходного условия где-то внизу.

φ не является вычислением обеих альтернатив

Запись x₃=φ(Then:x₁,Else:x₂) означает получение значения от соответствующего предшественника. При входе из Else используется x₂. Нельзя реализовать φ как обычный вызов функции, которому сначала вычисляют оба аргумента: один из них мог вообще не быть определён на данном пути. Если невыбранная ветвь содержит опасную операцию, её предварительное исполнение ещё и меняет поведение программы.

В SSA использование входного аргумента φ рассматривается на соответствующем ребре. Такое уточнение важно при проверке доминирования и живости. В цикле φ может объединять начальное значение и значение обратного ребра; это не нарушение единственности определения результата φ. Число и размещение таких узлов выбирают по структуре графа и нужным переменным, а не добавляют произвольно после каждой закрывающей скобки.

Регистровые значения не отменяют изменяемую память

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

Для проверки перевода полезно исполнить исходную и промежуточную программы на обеих ветвях, а затем проверить структурные условия: единственность имён, правильных предшественников φ и доминирование обычных использований. Совпадение двух численных примеров не является общим доказательством эквивалентности, но обнаруживает типичные ошибки выбора версии. После выхода из SSA обычно добавляют согласованные копирования на рёбрах; их порядок тоже должен сохранять необходимые значения.

Два пути к одному возвращаемому значению

Условие. if p: x=a+2; else: x=a−3; затем y=x·4; x=y+1; return x. Взять a=7.

  1. Во входе обозначим аргументы a₀,p₀. В Then определим x₁=a₀+2, в Else — x₂=a₀−3.
  2. В Join определим x₃=φ(Then:x₁,Else:x₂). Затем y₁=x₃·4 и x₄=y₁+1.
  3. При p=false вход выполнен из Else: x₂=4, x₃=4, y₁=16, x₄=17.
  4. При p=true вход выполнен из Then: x₁=9, x₃=9, y₁=36, x₄=37. Возвращается x₄.

Ответ. При a=7: false→17, true→37. Каждое имя SSA имеет одно определение.

Проверка. Исходная программа даёт те же значения на обеих ветвях. В Join нельзя без φ использовать только x₁: оно не определено на пути Else.

Где легко ошибиться. Текстовая близость определения к использованию не заменяет доминирование. Значение из одной ветви может отсутствовать на другом пути к той же строке.

Проверьте понимание

В Join пришли из Else. Какой аргумент выбирает φ(Then:x₁,Else:x₂)?

Вопросы к этой главе

Почему φ выбирает по предшественнику, а не просто по p?

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

SSA запрещает циклы?

Нет. Одна инструкция остаётся одним текстовым определением при многократном исполнении. φ на заголовке объединяет входное значение с версией обратного ребра.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • LLVM Language Reference: phi instruction

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

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

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

Перед началом: Граф управления; Множества USE и DEF; Чистая операция и побочный эффект.

Использование в ненужном вычислении тоже выглядит использованием

После x=5 и y=8 программа по условию p либо увеличивает x, либо вычисляет y=y−2, а затем возвращает только x. На первый взгляд вся цепочка y бесполезна. Но обычный анализ живости сначала заметит чтение y во второй ветви и сочтёт его значение нужным перед ней. Это не ошибка формул: анализ выполняется для текущего графа, где ненужное вычисление ещё существует.

Значение живо в точке, если существует путь к его использованию без промежуточного переопределения. Это свойство возможности, поэтому объединяются сведения обо всех допустимых продолжениях графа. Оно не утверждает, что значение понадобится в каждом запуске. Анализ может быть консервативным и учитывать синтаксические пути, которые более точное доказательство позднее исключит как невозможные.

Обратный анализ передаёт множества по рёбрам

Для блока OUT равен объединению IN всех его преемников. Затем IN=USE∪(OUT∖DEF). USE содержит значения, прочитанные до их определения внутри блока; DEF — определённые там переменные. Поэтому недостаточно собрать все правые части блока без учёта порядка локальных команд. У присваивания x=x+1 прежнее x читается, хотя новое x одновременно входит в DEF.

Начав с пустых множеств и корректных граничных условий выхода, применяют уравнения до неподвижной точки. На цикле один обратный проход может не донести сведения до всех предшественников. Конечность множества переменных и монотонное добавление информации дают завершение итераций. В форме SSA входные значения φ относятся к соответствующим рёбрам: механическое добавление всех вариантов во все ветви ухудшит точность анализа.

Ненужный результат ещё не разрешает удаление инструкции

Если определяемая переменная не жива после присваивания, её новое значение не потребуется. Но правая часть может выполнять наблюдаемое действие или завершаться исключением. Удаление записи в устройство, вызова с эффектами или проверяемого деления на ноль способно изменить программу, даже если вычисленное значение нигде не используется. Анализ живости не описывает все такие свойства операции.

В нашей задаче сложение и вычитание выполняются над тридцатидвухразрядными целыми по модулю 2³² и не вызывают исключений. Это явно выбранная семантика IR, при которой ненужное y=y−2 можно удалить. Она не переносится автоматически на язык с проверкой переполнения. Для вызова функции отдельно проверяются эффекты памяти, возможность исключения и другие оговорённые наблюдения программы.

Удаление меняет исходные данные самого анализа

После удаления вычисления y=y−2 исчезает его чтение y. Во второй ветви теперь достаточно сохранить x для возврата. Повторный анализ покажет, что и начальное y=8 больше не нужно. Если пользоваться только старой таблицей живости, эта возможность останется незамеченной. Поэтому оптимизации часто чередуют с обновлением анализов либо используют корректно поддерживаемые зависимости изменения графа.

Проверять нужно и то, что осталось. Условное ветвление по p здесь нельзя убрать только из-за исчезновения второй команды: первая ветвь всё ещё изменяет x. Для выбранной программы p=false возвращает 5, а p=true возвращает 6. Сравните обе ветви до и после преобразования, затем проверьте общее основание удаления: отсутствие используемого результата и отсутствие запрещённых побочных наблюдений, а не только совпадение одного удачного теста.

Два раунда удаления

Условие. B0: x=5;y=8; if p goto B1 else B2. B1: x=x+1;goto B3. B2: y=y−2;goto B3. B3:return x. Арифметика модульная и не бросает исключений.

  1. IN(B3)={x}. Для B1: OUT={x}, IN={x}. Для B2: OUT={x}, IN={x,y}.
  2. У B0 получаем OUT={x,y}, IN={p}: начальное y пока нужно существующей второй ветви.
  3. В B2 результат y не входит в OUT, а вычитание чистое. Удаляем присваивание и пересчитываем живость.
  4. Теперь IN(B2)={x}, OUT(B0)={x}. Инициализацию y=8 можно удалить. Ветвление и увеличение x сохраняются.

Ответ. Обе команды над y удалены; возврат остался 5 при false и 6 при true.

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

Где легко ошибиться. Мёртвый результат не означает ненаблюдаемую инструкцию. Без проверки эффектов удаление может убрать исключение, ввод-вывод или изменение общей памяти.

Проверьте понимание

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

Вопросы к этой главе

Почему живость идёт против направления исполнения?

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

Нужно ли заново проверять все свойства после каждого изменения?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Stanford CS143, Lecture 15: liveness and dataflow

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

Компьютерные сети

CIDR: почему правило «минус два» не подходит для /31 и /32

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

Перед началом: Двоичная маска; IPv4 как 32-битное число; Деление диапазона на блоки.

Префикс задаёт блок, а не автоматически число устройств

Запись 10.42.7.15/31 содержит тридцать один фиксированный бит и один изменяемый. Поэтому в блоке два адреса: 10.42.7.14 и 10.42.7.15. В привычной многоузловой подсети крайние адреса часто исключают из назначения узлам, но для связи точка-точка RFC 3021 определяет другое соглашение: оба адреса являются адресами концов линии. Механическое вычитание двух дало бы бессмысленный ноль.

Нужно разделить арифметический диапазон и правила использования адресов. Размер блока определяется длиной префикса: 2^(32−p). Назначение первого и последнего адресов зависит от контекста. Лаборатория показывает это явно для /31 и /32, но не проверяет поддержку конкретного оборудования и не настраивает интерфейсы. Расчёт адресов не является сканированием доступных машин.

Маска оставляет сетевые биты

Адрес сети получают побитовым AND адреса и маски. Для /31 маска равна 255.255.255.254: младший бит обнуляется. Поэтому нечётное последнее число 15 превращается в начало блока 14. Любой адрес того же блока даёт один и тот же сетевой результат. Простого поиска общей десятичной части для этого недостаточно, особенно когда префикс проходит внутри октета.

Полезно представить адрес как целое число и выделить младшие 32−p битов. Верхняя граница блока получается заполнением этих битов единицами. Все адреса между границами принадлежат префиксу. Это вычисление работает и для префиксов, не кратных восьми. Затем уже применяется соглашение, какие элементы диапазона используются как адреса узлов в рассматриваемой модели.

Два особых граничных префикса

В /31 для линии точка-точка нет отдельного направленного широковещательного адреса внутри этой пары: два значения представляют два конца соединения. Это исключение не следует безусловно переносить на любую многоадресную локальную сеть. В учебном ответе рядом с двумя доступными адресами должно быть указано соответствующее условие, иначе правильная арифметика превратится в неправильную рекомендацию по развёртыванию.

В /32 изменяемых битов нет. Блок содержит ровно один адрес, который удобно использовать как адрес узла или точный маршрут. Здесь также нельзя получить число адресов вычитанием двух. Запись /32 сама по себе не описывает соседей, шлюз и способ разрешения канального адреса. Это отдельные параметры сети, которые не выводятся из одного префикса.

Проверки диапазона не требуют обращения к сети

Для заданного блока проверьте три свойства: количество адресов равно степени двойки, начало выровнено по этому размеру, а исходный адрес находится между границами. Затем проверьте исключения назначения. Сеть может нормализоваться из записи с установленными битами узла; некоторые инструменты вместо этого требуют строго сетевой адрес. Такое различие ввода не меняет математику маски.

Для планирования дополнительно учитывают резервирование, маршруты и поддержку оборудования, но эти сведения не появляются из результата калькулятора. Обратная проверка особенно полезна при /31: оба конца после маскирования должны дать один блок. Для /32 совпадут начало, конец и сам адрес. Ни одно из этих равенств не доказывает, что адрес уже назначен или отвечает на пакеты.

Один адрес, два разных префикса

Условие. Рассмотреть 10.42.7.15/31 для соединения точка-точка и 10.42.7.15/32 для точного адресного блока.

  1. Маска /31 равна 255.255.255.254; последний бит 15 обнуляется, начало равно 10.42.7.14.
  2. Размер /31 равен 2^(32−31)=2: диапазон заканчивается на 10.42.7.15.
  3. При соглашении RFC 3021 оба адреса .14 и .15 могут обозначать концы линии.
  4. Для /32 размер равен 1; начало и конец совпадают с 10.42.7.15.

Ответ. /31: два конца .14 и .15 при условии точка-точка. /32: один адрес .15.

Проверка. Маскирование .14 и .15 маской /31 даёт .14. Для /32 маска сохраняет все 32 бита.

Где легко ошибиться. Формула количества обычных назначаемых узлов с вычитанием двух имеет условия. Она не является определением размера CIDR-блока.

IPv4-подсеть из адреса и длины префикса

Введите IPv4/CIDR. Для префиксов до /30 показан обычный диапазон узлов без адресов сети и broadcast. /31 трактуется отдельно как point-to-point по RFC 3021; /32 — один адрес. Сетевые запросы не выполняются.

Данные для расчёта

Проверьте понимание

Сколько всего адресов содержит IPv4-префикс /32?

Вопросы к этой главе

Последний адрес /31 обязательно broadcast?

В модели RFC 3021 для точки-точки он является адресом второго конца. Нельзя одновременно применять это соглашение и исключать его как обычный направленный broadcast.

/32 означает отсутствие адресов?

Нет. В блоке один адрес. Для понимания доступности и соседства нужны дополнительные настройки, которые из префикса не следуют.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • IETF RFC 3021: 31-bit prefixes on point-to-point links

    Проверено специальное назначение обоих адресов /31; условие точка-точка сохранено.

  • IETF RFC 4632: CIDR

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

TCP sequence и ACK: подтверждаются байты, а не номера пакетов

Восстанавливаем непрерывный полученный префикс при переставленных сегментах и учитываем место SYN и FIN в последовательности.

Перед началом: Полуоткрытый интервал; Длина сегмента в байтах; Различие потока и сообщения.

Сначала восстановите ожидаемый байт

Пусть SYN имеет sequence 7000. Следующий ожидаемый номер данных равен 7001, потому что SYN занимает одну позицию последовательности. Если сначала придут данные с номером 7501, получатель всё ещё не получил байт 7001. Кумулятивное подтверждение не может перескочить через эту дыру, даже если более поздний участок уже сохранён в буфере.

Sequence обозначает позицию первого байта сегмента в потоке, а ACK — следующий ожидаемый номер после непрерывно полученного префикса. Это не счётчик IP-пакетов. Один и тот же диапазон может передаваться повторно, сегменты могут иметь разную длину, а приложение читает поток порциями, не обязанными совпадать с границами отправок. Протокол верхнего уровня сам определяет границы своих сообщений.

Внеочередные данные не закрывают предыдущую дыру

Если получатель сохраняет внеочередной диапазон, после прибытия недостающего начала подтверждение может сразу пройти через весь собранный непрерывный участок. Без такого сохранения пришлось бы дождаться повторной передачи поздних байтов. В нашем примере буферизация явно разрешена. Это условие нужно объявить, чтобы из одинакового порядка прихода не выводить единственную последовательность подтверждений для любых реализаций.

Повторный ACK показывает, где всё ещё начинается непрерывно неполученный участок. Его появление само по себе не доказывает конкретную причину: возможны потеря, перестановка или дублирование. Механизмы восстановления используют дополнительные правила и измерения. При ручной трассировке полезно вести множество полученных интервалов и отдельно указатель следующего нужного байта, а не прибавлять длину каждого пришедшего сегмента к старому ACK.

Управляющие флаги и предел подтверждения

FIN, как и SYN, занимает одну позицию последовательности, хотя не является байтом пользовательского содержимого. Обычный флаг ACK отдельного места не занимает. Поэтому после тысячи байтов данных и последующего FIN ожидаемый номер сдвинется ещё на единицу. Две независимые стороны соединения ведут собственные последовательности: их численные значения не обязаны совпадать.

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

Нумерация и окно задают разные ограничения

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

Окно получателя ограничивает объём данных, который он готов принять, а управление перегрузкой учитывает состояние сети. Эти механизмы не меняют смысл следующего ожидаемого байта. Реальный стек также может откладывать подтверждения, поэтому шаги задачи показывают значения кумулятивного ACK после событий, а не обещают отправку отдельного пакета подтверждения на каждый приходящий сегмент.

Средний сегмент приходит раньше первого

Условие. SYN seq=7000. Данные: [7001,7501), [7501,7801), [7801,8001). Получатель сохраняет внеочередные байты; сначала приходит второй сегмент, затем первый, затем третий и FIN seq=8001.

  1. После SYN следующий ожидаемый номер 7001. При приходе [7501,7801) он остаётся 7001.
  2. Первый сегмент закрывает дыру; вместе с уже сохранённым вторым получен весь диапазон [7001,7801). ACK становится 7801.
  3. Третий сегмент продолжает префикс до 8001, поэтому ACK=8001.
  4. FIN занимает позицию 8001; после его приёма следующий ожидаемый номер равен 8002.

Ответ. Значения после указанных событий: 7001, 7801, 8001, 8002.

Проверка. Данные имеют длины 500+300+200=1000. От начального 7000 итоговый номер увеличен на SYN, тысячу байтов и FIN: 7000+1+1000+1=8002.

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

Проверьте понимание

Получены байты после дыры, но её начало отсутствует. Куда указывает кумулятивный ACK?

Вопросы к этой главе

Два сегмента по пятьсот байтов дают ACK плюс два?

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

ACK означает, что документ записан на диск?

Нет. Для этого требуется подтверждение приложения с соответствующей гарантией сохранности; транспортный приём сам её не содержит.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • IETF RFC 9293: Transmission Control Protocol

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

DNS-кеш: время жизни записи и время жизни отрицательного ответа

Строим временную шкалу положительного A-ответа и отдельного отрицательного AAAA-ответа без реальных DNS-запросов.

Перед началом: Момент истечения и оставшееся время; Имя и тип DNS-записи; Авторитетный сервер и рекурсивный резолвер.

Изменение зоны не переписывает уже выданный кеш

Если в момент ноль резолвер получил A-запись с TTL девяносто секунд, обычная модель кеша разрешает использовать её до момента девяносто. Изменение записи на авторитетном сервере в момент восемьдесят не отправляет автоматическое обновление каждому прежнему клиенту. В течение оставшегося срока резолвер может продолжать возвращать старый адрес. Это нормальное следствие заранее объявленного времени жизни.

Различайте состояние зоны, состояние рекурсивного кеша и локальное кеширование приложения. Они могут обновляться в разные моменты. Обещание «адрес уже поменяли» обычно относится только к одному из этих уровней. Для точного вывода укажите, откуда получен ответ, когда он был сохранён и какой оставшийся TTL имеет. Один ответ с нового сервера не доказывает обновление всех клиентов.

TTL уменьшается от момента получения

В простой модели запись с начальным TTL τ, полученная в момент t₀, истекает в t₀+τ. При выдаче из кеша в момент t оставшийся срок равен τ−(t−t₀), пока он положителен. Промежуточный запрос не должен каждый раз возвращать исходный срок и продлевать жизнь старого значения бесконечно. На границе истечения нужен новый допустимый источник ответа.

Записи разных типов и разные наборы ресурсов кешируются со своими сроками. Цепочка псевдонимов и конечный адрес также могут иметь разные TTL. Нельзя без проверки приписать всему разрешению имени единственное время одной найденной записи. Здесь рассматриваем обычное использование неистёкшего кеша; специальные политики выдачи устаревших ответов и локальные ограничения реализации в числовую модель не включены.

Отрицательный ответ тоже имеет предмет и срок

NXDOMAIN сообщает об отсутствии имени, а NODATA — об отсутствии запрошенных данных нужного типа при существующем имени. У существующего A-адреса может отсутствовать AAAA, поэтому отрицательный AAAA-ответ не должен автоматически уничтожать положительный A-результат. Для интерпретации важны имя, класс, тип запроса и содержимое отрицательного ответа, а не только отсутствие удобного адреса в показанном списке.

RFC 2308 задаёт срок отрицательного кеширования через меньшее из TTL записи SOA и её поля MINIMUM в соответствующем ответе. Этот срок тоже уменьшается по времени. Поле MINIMUM нельзя во всех ситуациях трактовать как универсальный TTL любых положительных записей зоны. Разделение этих ролей особенно важно, когда только что добавленная запись продолжает казаться отсутствующей старому резолверу.

Проверяйте временную шкалу по отдельным ключам

Для каждого сохранённого ответа выпишите момент получения, начальный срок и момент истечения. Затем обработайте события по времени, не смешивая авторитетное изменение с запросом к кешу. После нового получения срок вычисляется заново от нового момента. Используйте в учебной задаче зарезервированное имя и синтетические ответы; для арифметической проверки обращаться к действующим чужим доменам не требуется.

Кеширование повышает доступность и уменьшает повторную работу, но делает немедленное глобальное переключение неверной исходной моделью. Для прикладной миграции нужны дополнительные правила планирования, проверки и отката. Из вычисленного TTL можно вывести срок конкретной записи в заданной модели, а не гарантию успешного подключения: маршрутизация, доступность сервиса и поведение приложения проверяются отдельно.

Два независимых срока для lab.example

Условие. В t=0 A=192.0.2.23, TTL=90. В t=80 авторитетный A изменён на 192.0.2.51; новый запрос резолвера происходит в t=90. В t=100 получен NODATA для AAAA: SOA TTL=120, MINIMUM=45.

  1. В t=40 старый A имеет оставшийся TTL 50; в t=80 ещё разрешён со сроком 10.
  2. В t=90 старый срок истёк; новый положительный ответ со сроком 90 истечёт в t=180.
  3. Отрицательный AAAA-ответ получает TTL=min(120,45)=45 и истекает в t=145.
  4. В t=130 отрицательный AAAA имеет срок 15, а новый положительный A — срок 50. Эти ответы совместимы.

Ответ. В t=130 A остаётся новым положительным ответом; отсутствие AAAA ещё кешируется отдельно.

Проверка. 180−130=50, 145−130=15. NODATA для AAAA не утверждает отсутствия имени lab.example и его записи A.

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

Проверьте понимание

Отрицательный ответ имеет SOA TTL 80 и MINIMUM 30. Какой начальный срок используется по правилу задачи?

Вопросы к этой главе

Запрос к кешу продлевает старый TTL?

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

Почему новый AAAA может не появиться сразу?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Маршрутизация: самый длинный подходящий префикс

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

Перед началом: CIDR и принадлежность адресу блока; Следующий узел маршрута; Сравнение длины префикса.

Узкое правило может перекрыть большой агрегат

Для адреса 10.44.9.70 могут одновременно подходить маршруты /0, /8, /16 и /21. В одной выбранной таблице из подходящих записей используется самый длинный префикс. Число после косой черты показывает точность совпадения битов, а не задержку и не число переходов. Поэтому даже маршрут с менее привлекательным названием шлюза может победить более общий агрегат.

Сначала должна быть выбрана применимая таблица и набор допустимых записей. Политики по источнику, административные предпочтения и выбор маршрута среди записей одинаковой специфичности относятся к другим частям системы. Здесь они считаются уже разрешёнными. Это ограничение не мешает изучить longest-prefix match, но запрещает объявлять один учебный поиск полной моделью всех решений современного маршрутизатора.

Совпадение проверяется маской, а не строковым префиксом

Адрес принадлежит записи, если после маскирования её длиной получается указанный сетевой префикс. Для 10.44.8.0/21 блок третьего октета охватывает числа от 8 до 15. Адрес с третьим октетом 16 уже вне него, хотя первые десятичные части выглядят похожими. Поэтому проверка «строка начинается на 10.44» не реализует правило диапазона.

Маршрут по умолчанию /0 подходит любому IPv4-адресу, но проигрывает любой более специфичной допустимой записи. Отсутствие отдельного маршрута к каждому узлу компенсируется агрегатами. Это уменьшает размер таблицы, однако агрегирование должно соответствовать возможностям доставки. Объявление широкого блока не создаёт автоматически рабочие пути ко всем адресам внутри него.

Действие выбранного маршрута тоже имеет значение

Запись может задавать следующий узел, локальную доставку или намеренное отбрасывание. Если для 10.44.10.0/24 определён blackhole, адрес 10.44.10.70 выбирает именно эту более точную запись и отбрасывается. Нельзя после этого самовольно вернуться к /21 и переслать пакет «хоть куда-нибудь»: это отменило бы смысл более специфичного запрета в нашей модели таблицы.

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

Сохраняйте все совпавшие записи для проверки

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

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

Три адреса и одно исключение

Условие. Таблица: 0.0.0.0/0→A; 10.0.0.0/8→B; 10.44.0.0/16→C; 10.44.8.0/21→D; 10.44.10.0/24→blackhole.

  1. 10.44.9.70 принадлежит /0,/8,/16,/21, но не запрещающему /24.
  2. Самая длинная запись для него /21, значит выбирается D.
  3. 10.44.10.70 также принадлежит /24; выбирается blackhole без возврата к D.
  4. 10.44.16.1 не входит в диапазон третьего октета 8…15, поэтому выбирается /16→C.

Ответ. 10.44.9.70→D; 10.44.10.70→отбрасывание; 10.44.16.1→C.

Проверка. Перестановка строк таблицы не меняет максимальную длину совпадения. Узкая запись затрагивает только диапазон 10.44.10.0…10.44.10.255.

Где легко ошибиться. Самая длинная маска выбирается только среди действительно совпавших записей. Просто взять максимальную длину во всей таблице неправильно.

Проверьте понимание

Что происходит с адресом из более специфичного blackhole при наличии общего маршрута?

Вопросы к этой главе

Маршрут /21 всегда лучше /16?

Только для адреса, который входит в этот /21. Для остальных адресов он вообще не является кандидатом.

Следующий узел D означает кратчайший путь?

Из одного результата поиска это не следует. Выбор и распространение маршрутов имеют собственные метрики и политики; здесь проверяется только совпадение префикса.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • IETF RFC 4632: CIDR routing

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

Задержка, пропускная способность и BDP: сколько данных держать в полёте

Считаем объём неподтверждённых данных, ограничение окна и время сериализации одного пакета, сохраняя единицы измерения.

Перед началом: Биты и байты; Скорость и время; RTT и подтверждение.

Быстрый канал может простаивать в ожидании подтверждения

Канал способен передавать сорок мегабит в секунду, но разрешённый объём неподтверждённых данных может оказаться слишком мал для длинного RTT. Отправитель исчерпает окно раньше, чем вернутся подтверждения, и не сможет постоянно занимать линию. Поэтому одно объявленное значение скорости интерфейса не определяет скорость длинного TCP-потока. Нужно сопоставить скорость, круговую задержку и допустимые данные в полёте.

Произведение пропускной способности на RTT даёт BDP — объём, необходимый для заполнения пути в такой модели обратной связи. При скорости в битах в секунду результат получается в битах. Перевод в байты требует деления на восемь. Десятичные мегабиты и двоичные мебибайты также нельзя молча смешивать: обозначение единиц входит в само численное условие задачи.

Окно даёт верхнюю границу, но не обещание результата

Если в полёте разрешено не больше W байтов, идеальная установившаяся скорость ограничена W/RTT байтов в секунду. Для TCP действуют и окно получателя, и окно управления перегрузкой; эффективное ограничение может быть меньше одного из них. Увеличение только приёмного буфера не снимает автоматически другое ограничение. Потери, обработка и ограничения приложения тоже способны уменьшить фактическую полезную скорость.

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

Передача пакета и распространение — разные задержки

Сериализация L битов на линии со скоростью R занимает L/R секунд. Распространение зависит от длины пути и среды. Очередь добавляет изменяющееся ожидание, а обработка — собственную стоимость. Удвоение скорости линии уменьшает сериализацию, но само по себе не вдвое сокращает время движения сигнала по длинному кабелю. Нельзя все эти компоненты заменить одним размером пакета.

RTT включает путь туда и обратно в условиях измерения. Для BDP используется именно круговая задержка обратной связи; для прибытия последнего бита одного пакета нужна соответствующая односторонняя модель. Если RTT меняется из-за очередей, меняется и требуемый бюджет. В числовой задаче значения фиксированы специально, чтобы отделить арифметику от оценки реального изменчивого пути.

Уточняйте, что именно измеряется

Скорость линии, транспортная скорость и полезная скорость приложения могут различаться из-за заголовков, повторов и протокольных действий. При сравнении укажите размер передачи, интервал измерения, единицы и включённые расходы. Время соединения и время выполнения запроса приложением также не являются одной величиной. Быстрый канал не устраняет медленное чтение диска или обработку сервером.

Для самостоятельной проверки сначала переведите все исходные числа в секунды, биты и байты. Затем проверьте размерность каждого выражения: скорость на время даёт объём, объём на время — скорость. Наконец, перечислите опущенные условия. Учебный калькулятор или ручной расчёт не должен объявлять отсутствие этих условий в действующей сети, если сетевой эксперимент вообще не проводился.

Бюджет для шестидесяти миллисекунд

Условие. Идеальная установившаяся модель: R=40 Мбит/с, RTT=60 мс, разрешённые неподтверждённые данные W=120000 байтов. Отдельно найти сериализацию пакета 1500 байтов без служебных расходов.

  1. RTT=0,06 с. BDP=40000000×0,06=2400000 бит.
  2. Делим на восемь: для бюджета BDP нужно 300000 байтов.
  3. Текущее окно даёт предел 120000/0,06=2000000 байт/с, то есть 16 Мбит/с.
  4. Пакет имеет 12000 бит; время сериализации 12000/40000000=0,0003 с=0,3 мс.

Ответ. BDP=300000 байтов; ограничение окна — 16 Мбит/с; сериализация пакета — 0,3 мс.

Проверка. 300000/0,06×8=40000000 бит/с. Сериализация не включает распространение, очередь, заголовки и повторную передачу.

Где легко ошибиться. Окно в байтах нельзя делить на RTT в миллисекундах и называть результат битами в секунду без обоих преобразований единиц.

Проверьте понимание

При том же окне RTT удвоился. Как меняется идеальная граница W/RTT?

Вопросы к этой главе

Если окно стало равно BDP, скорость гарантированно равна линии?

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

Почему для BDP взят RTT, а не одна сторона пути?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • IETF RFC 6349: Framework for TCP Throughput Testing

    Проверены BDP по RTT и перевод требуемого окна в байты. Скорость, окно и пакет примера рассчитаны отдельно; сетевых испытаний не проводилось.

Темы направления

Алгоритмы на графах: представление, пути и зависимости

Обзор модуля

Выбор представления графа, условия алгоритма Дейкстры, топологический порядок и длиннейший путь в DAG: сравнение задач и гарантий алгоритмов.

Алгоритмы строк: подпоследовательность, правки и границы совпадений

Обзор модуля

Выберите задачу сравнения строк: общая подпоследовательность, расстояние правок, префикс- или Z-функция. Разведите стоимость преобразования и точное совпадение фрагментов.

Графовые задачи: существование, построение и точный подсчёт

Обзор модуля

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

Двоичные представления: коды, рекурсии и эскизы

Обзор модуля

Как компактная запись хранит информацию: интервалы арифметического кода, GF(2), линейная рекурсия и слияние регистров.

Автоматы и границы алгоритмического доказательства

Обзор модуля

Детерминизация, различимость префиксов, накачка и неразрешимость семантических свойств программ.

Разобранный пример

Кратчайший путь по слоям

В неориентированном невзвешенном графе рёбра AB, AC, BD, CD, DE. Найдите расстояние от A до E и один кратчайший путь.

  1. Слой 0 содержит A. После его обработки слой 1 содержит B и C.
  2. Из B и C впервые обнаруживается D: его расстояние 2. Повторное ребро к D не создаёт новую вершину очереди.
  3. Из D обнаруживается E на расстоянии 3. По запомненным предкам получаем A–B–D–E, если B обработана первой.

Ответ: Расстояние 3; один путь A–B–D–E.

Проверка: Все рёбра пути присутствуют. До слоя 3 E не обнаружена: её единственный сосед D имеет минимальное расстояние 2, поэтому пути длины 1 или 2 к E нет.

Проверьте понимание

Когда обычный BFS даёт кратчайший путь по числу рёбер?

Вопросы по направлению

Почему тесты не заменяют доказательство алгоритма?

Конечный набор тестов обычно не покрывает все входы. Тесты ищут конкретные сбои, а инвариант и доказательство завершения объясняют поведение всей заявленной области.

O(n+m) означает точное число операций?

Это оценка порядка роста при принятой модели стоимости. Константы, хранение и характер входа остаются важны. Для сравнения сначала уточняют, что считается n и m.

Достаточно ли совпадения хеша для равенства строк?

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