Логика, графы, пути и поисковые запросы

В этих задачах один и тот же объект удобно видеть по-разному: условие — как логическое выражение, дороги — как граф, запросы — как множества страниц. Сначала переведите текст в модель, затем считайте.

Пусть $A$ и $B$ — высказывания.

Приоритет: отрицание, затем «и», затем «или». Скобки меняют порядок.

Полная таблица для «и» и «или»:

Пример. Для $A=1$, $B=0$:

а

Результат совпал, но это не общее тождество. Проверьте остальные строки таблицы истинности.

Отрицание выражения раскрывают так:

Пример. Отрицание условия «целое число положительное и чётное» означает «целое число неположительное или нечётное». Союз меняется, отрицание применяется к каждой части.

Текст «$x$ не меньше 7» означает $x\ge7$, «не больше 12» — $x\le12$, «вне отрезка от 7 до 12» — $x<7\lor x>12$.

Пример. Найдём целые $x$, для которых истинно $x\ge4\land x<8$. Пересечение условий даёт $4,5,6,7$: всего 4 значения.

Запрос с «И» соответствует пересечению множеств страниц, запрос с «ИЛИ» — объединению. Для двух запросов:

Пример. Запрос робот нашёл 620 страниц, алгоритм — 480, а робот И алгоритм — 170. Тогда

Пересечение вычитают один раз, потому что в сумме $620+480$ общие страницы посчитаны дважды.

Для трёх множеств:

Пример. Три запроса дали 100, 80 и 60 страниц; попарные пересечения — 30, 20 и 10, общее пересечение — 5:

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

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

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

Пример. Степени четырёх вершин равны 2, 3, 2 и 1. Сумма равна 8, значит, рёбер $E=8:2=4$.

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

1. Начальной вершине присвойте расстояние 0, остальным — бесконечность.
2. Выберите непосещённую вершину с наименьшим расстоянием.
3. Попробуйте улучшить расстояния до её соседей.
4. Пометьте вершину посещённой и повторяйте.

Пример. Есть дороги $A-B=4$, $A-C=2$, $C-B=1$, $B-D=5$, $C-D=8$. Сначала из $A$ получаем $B=4$, $C=2$. Через $C$ улучшаем $B$: $2+1=3$. Через $B$ получаем $D=3+5=8$. Путь $A-C-B-D$ короче прямого варианта $A-C-D=10$.

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

Пример. Из $A$ идут рёбра в $B$ и $C$, из $B$ и $C$ — в $D$, из $C$ — ещё в $E$, из $D$ — в $E$.

Ответ: из $A$ в $E$ ведут 3 пути. При наличии циклов сначала уточните, разрешено ли посещать вершины повторно: без ограничения число маршрутов может стать бесконечным.

URL обычно содержит схему, имя узла, путь и иногда параметры, например https://example.org/tasks/list?page=2. IP-адрес идентифицирует узел в сети, доменное имя даёт человеку удобное имя, DNS сопоставляет доменное имя с сетевым адресом.

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

• Союзы «и», «или», «не» переведены без перестановки смысла?
• В запросах «И» стало пересечением, а «ИЛИ» — объединением?
• Общая часть множеств не посчитана дважды?
• У графа учтены направления и веса?
• Кратчайший маршрут проверен сравнением сумм?
• При подсчёте путей сложены все входящие варианты?

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

Охват тем и экзаменационных действий сверён с проектом кодификатора ОГЭ-2027 ФИПИ. Схемы решения и числа в примерах созданы FastLearn.