Хочется разобрать решение контрольной работы по дискретной математике для студентов 1 курса. Контрольная разработана для будущих программистов, потому и ориентирована на пошаговое изложение алгоритмов. Я всегда считала эту контрольную примитивной и какой-то "бонусной", где студенты набирают много баллов. Но с приходом больших языковых моделей данное задание стало для студентов непосильной ношей.
Задача 1. Построить бинарное дерево поиска
Заданы слова: Марина, Наталья, Василиса, Полина, Зинаида, Екатерина, Клавдия, Евгения, Серафима, Ярослава. Построить бинарное дерево поиска, подробно описать процесс построения. Привести рисунок, на котором изображено результирующее дерево.
Решение от человека. Расписывать не буду, жаль, но платформа Дзена не обладает достаточным инструментарием для записи таблиц и формул. Суть в том, что построение бинарного дерева начинается с корня. Вставка каждого нового узла также идет от корня исходного дерева. И данная структура в дальнейшем используется при организации сортировки. Данные поступают последовательно, начиная с первого слова, заканчивая десятым. Обратите внимание на структуру дерева! В левом поддереве каждой вершины содержатся только строки, которые по алфавиту идут раньше.
А теперь я взяла постановку, сделала скриншот и попросила хваленый и разрекламированный всезнающий GigaChat написать мне подробное решение задачи.
Решение от GigaChat
Уже на первом шаге нейронная сеть делает грубейшую ошибку: сортирует предложенный массив. Для чего - не ясно.
Шаг 1: Определение порядка вставки элементов
Сначала упорядочим имена по алфавиту:Евгения
Екатерина
Зинаида
Клавдия
Марина
Наталия
Полина
Серафима Ярослава
Василиса
Теперь будем строить дерево, начиная с первого элемента списка.
Далее нейронная сеть выдает правильный алгоритм вставки:
Шаг 2: Процесс построения бинарного дерева поиска
Определение структуры узла: Каждый узел дерева имеет три компонента:Значение (имя)
Левый потомок
Правый потомок
Алгоритм вставки нового элемента: Начинаем с корня дерева.
Если дерево пустое, новый элемент становится корнем.
Иначе сравниваем новое значение с текущим узлом:Если новое значение меньше текущего, идём влево.
Если больше, идём вправо.
Повторяем шаги 2 и 3, пока не найдём свободное место для вставки.
И в результате бурной интеллектуальной деятельности выдается вот такой ответ:
Перед этим описываются все этапы вставки. Но... Узел "Екатерина" никак не может быть левым поддеревом "Евгении". А что случилось с Серафимой и Ярославой я совсем не пойму. Превратились в сиамских близнецов на этапе сортировке. А Василису затолкнули на самое последнее место в алфавите. Буду знать, что "В" - последняя буква в русском алфавите, а то до появления ГигаЧата это было для меня тайной.
Qwen 3.5 Plus
Cправился с задачей не настолько дико, но все равно отличником его назвать сложно.
Нейронная сеть построила таблицу, в которой определила место каждой вершины...
1 Марина — (первый элемент) Корень
2 Наталья
Наталья > Марина
Правый сын (Марина)
3 Василиса
Василиса < Марина
Левый сын (Марина)
4 Полина
Полина > Марина, Полина > Наталья
Правый сын (Наталья)
5 Зинаида
Зинаида < Марина, Зинаида > Василиса
Правый сын (Василиса)
6 Екатерина
Екатерина < Марина, Екатерина > Василиса, Екатерина < Зинаида
Левый сын (Зинаида)
7 Клавдия
Клавдия < Марина, Клавдия > Василиса, Клавдия > Зинаида
Правый сын (Зинаида)
8 Евгения
Евгения < Марина, Евгения > Василиса, Евгения < Зинаида, Евгения < Екатерина
Левый сын (Екатерина)
9 Серафима
Серафима > Марина, Серафима > Наталья, Серафима < Полина
Левый сын (Полина)
10 Ярослава
Ярослава > Марина, Ярослава > Наталья, Ярослава > Полина
Правый сын (Полина)
Получилось вот такое деревце...
Но как считаете, знает ли Qwen русский алфавит? С дискретной математикой у него значительно лучше, чем у GigaChat, но проблемы все равно есть... Подсказка - правильный ответ в решении от человека!!!
Задача 2. Алгоритмы вставки, поиска и удаления в бинарном дереве поиска
Задача и ее ручное решение приведены на рисунке.
Здесь вставляемая вершина J является правым сыном вершины i (для этого нужно пройти от корня по синей траектории), для определения отсутствия T необходимо 4 сравнения в узлах, помеченных красным, а при удалении E ее следует заменить вершиной G. Все делается в соответствии с алгоритмами.
Решение от GigaChat
Вроде бы, все начинается безобидно...
Чтобы вставить букву J, начнем с корня дерева N и будем двигаться вниз, сравнивая значения узлов:
- Сравниваем J с N: J < N → идем влево
- Сравниваем J с E: J > E → идем вправо
- Сравниваем J с H: J > H → идем вправо
- Сравниваем J с I: J > I → идем вправо
- Узел M является листом, значит J вставляется как правый ребенок M
Но... внезапно нейронную сеть подвидит распознавание, и она путает L и i. Результат очевиден. Ошибка.
Поиск буквы T
Для проверки наличия буквы T в дереве выполним следующий процесс:
- Сравниваем T с N: T > N → идем вправо
- Сравниваем T с U: T > U → идем вправо (у российской нейросети плохо с латинским алфавитом... PQRSTUVW...)
- Сравниваем T с W: T < W → идем влево
- Сравниваем T с V: T > V → идем вправо
- Достигли листа Z, T ≠ Z → буква отсутствует
Всего потребовалось 5 сравнений, чтобы установить отсутствие буквы T в дереве. И снова ошибка.
Удаление узла E
Удаление узла E требует особого внимания, поскольку этот узел имеет двух детей (B и H). Отлично, понимает, что задача дана непростая...
- Для удаления узла с двумя детьми в бинарном дереве поиска обычно используют следующую стратегию:
- Найти преемника узла E - минимальный элемент в правом поддереве (H) ("преемника" обычно называют в учебной литературе "сыном", потому использование слова "преемник" - сразу намек на автора решения).
- Скопировать значение преемника (H) в удаляемый узел (E)
- Удалить прежнее местоположение преемника (H)
- Процесс удаления:Копируем значение H в узел E
- Теперь нужно удалить старый узел H
- У старого узла H есть два ребенка (I и P)
- Преемником H будет I (минимальный элемент в правом поддереве)
- Копируем I в старое положение H
- Удаляем старый узел I (лист)
И снова имеем решение невпопад. Алгоритм удаления узла с двумя указателями таков: переход к правому сыну, а далее осуществляется переход по левым сыновьям до тех пор, пока возможно. Замена осуществляется на узел, не имеющий левого сына. Есть еще нюансы, но для решения данной задачи информации достаточно. Очевидно, что переход направо, а затем налево в данном дереве - E->H->G. И поскольку G - лист, то значение E заменяется на G, а старый G удаляется. Итог - опять провал.
Решение от Qwen 3.6
1. Вставка буквы J
Процесс вставки:
- J < N → идём влево к E
- J > E → идём вправо к H
- J > H → идём вправо к L
- J < L → идём влево к I
- J > I → I не имеет правого потомка, J становится правым потомком I
Ура! Победа! Решил верно!
2. Поиск буквы T (сколько сравнений)
Процесс поиска:
- T > N (1-е сравнение) → идём к U
- T < U (2-е сравнение) → идём к R
- T > R (3-е сравнение) → идём к S
- T < S (4-е сравнение) → у S нет левого потомка
Ответ: требуется 4 сравнения, чтобы понять, что буква T отсутствует. И снова вссе отлично!
3. Удаление узла E
Узел E имеет двух потомков (B и H). Согласно стандартному алгоритму удаления из BST, нужно заменить удаляемый узел на его ин-ордер предшественника (наибольший в левом поддереве) или преемника (наименьший в правом поддереве). Нейронка нашла алгоритм. Записала его своими словами, слишком мудрено, но верно. А далее использовала одну из стратегий. Она китаянка, ей простительно работать справа налево, а не слева направо.
Используем ин-ордер предшественника:
- В левом поддереве E наибольший элемент — D
- Заменяем E на D
- Левый потомок D (буква C) становится правым потомком B
В данном случае Qwen справился отлично. Но, помня о первом решении, его нужно проверять. Вдруг в этот раз просто повезло?
Задача 3. Матричная формула Кирхгофа для подсчета числа остовных деревьев
Решение от GigaChat
Уже после первого шага рассматривать решение от этой нейронки отпадает всякое желание.
Начнем с того, что GigaChat где-то разглядел шестую вершину в графе и не доглядел одно ребро. Для чего он строит матрицу инцидентности, да еще и с ориентацией - совсем не ясно. В формуле требуется матрица смежности.
Далее еще загадочнее.
На лекциях мы это называли матрицей Кирхгофа (кстати, это одно и то же) и использовали при ее составлении матрицу степеней и матрицу смежности. Мне очень интересно, где GigaChat разглядел вершину степени 2. Или он решает на опыте вариантов, загруженных моими студентами?
Далее вычисляется алгебраическое дополнение, в правильность данного процесса я углубляться уже не хочу, поскольку на вход уже подана неверная матрица. И, как следствие, получается совершенно не верный ответ, отдаленно похожий на правду.
Далее я еще в донейронную эпоху затроллила все нейронки вместе взятые, потребовав нарисовать примеры остовных деревьев. Для человека это не составляет труда. Перерисовал 5 вершин на своих местах (а рисовать точки в том же месте, где они располагаются на образце, учат в старшей группе детского сада и в подготовишке к школе), и добавляй произвольные 4 ребра, лишь бы цикл не образовали. А для нейронки это задача неподъемная... Иллюстрацию к сказке нарисует, а вот остовное дерево - это очень большая для нее проблема!
Qwen 3.6 Plus
Посмотрим на результаты от китаянки. Мозг китаянки от этой задачи настолько вскипел, что по-русски она общаться отказалась...
Looking at this problem, I need to solve it using Kirchhoff's Matrix Tree Theorem. Let me analyze the graph structure first.
The graph shown is a wheel graph W₅ with:
- 1 center vertex connected to 4 outer vertices
- 4 outer vertices forming a cycle
Let me label the vertices: 1 (center), 2 (top), 3 (right), 4 (bottom), 5 (left)
Но матрицы степеней и матрицу смежности (именно смежности) она построила верно. И полученная матрица Кирхгофа тоже верная. Да, вершины пронумерованы не так, как в моем ручном решении, но это не ошибка.
И даже алгебраическое дополнение было записано верно, но вот с расчетом определителя вышел конфуз...
Но это не смущает нейронку, и она выдает ответ:
Number of spanning trees = 9
Since 9 ≤ 10, all spanning trees can be drawn. The spanning trees are:
- 4 spokes + 0 outer edges: All 4 spokes (only 1 way)
- 3 spokes + 1 outer edge: 8 treesRemove each spoke (4 choices) × valid outer edges (2 choices each)
- 2 spokes + 2 outer edges: Not possible without creating cycles
Answer: The graph has exactly 9 spanning trees.
Граф имеет ровно 9 остовов, и она даже рассказывает, как их рисовать, но рисовать все равно не умеет!
Задача 4. Остовное дерево оптимального веса
Ручное решение. Конечно, немного короче, чем на контрольной.
Решение от GigaChat
Догадайтесь с первого раза, правильно ли решена задача? Конечно же, нет.
И ошибки начинаются с самого первого действия - выписывания весов ребер. Если посчитать, то можно увидеть, что ребро v3v6, вообще, оказалось потеряно. Оно, правда, не попадает в ответ. Но где гарантия, что для другой задачи нейронка не выкинет ребра из решения?
Работа с алгоритмом Прима идет аккуратно, ребра добавляются...
Но... в результате получаем вот какой ответ...
Для начала, дерево вдруг стало "основным", а не остовным. Ладно, дискретной математики нейронка не знает. Тот поток сознания, который приводится после - на да, можно перерисовать в свой листок. Но что это значит? Вершины, соединенные ребрами определенного веса. А не проще ли взять цветную ручку и нарисовать решение на графе из условия? Ведь красить необходимые нам объекты нас учили в старшей группе детского сада. Почему-то на первом курсе доверие к ответу от нейронной сети настолько велико, что люди готовы пожертвовать своими базовыми навыками.
А найденное решение, конечно же, с ошибкой. С какой? Нейронка пропустила ребро v2v6 с весом 6.
Qwen 3.6 Plus
При решении данной задачи нужно признать, что Qwen 3.6 Plus победил. Он правильно считал со скриншота с условием все данные и аккуратно применил алгоритм Прима. Итерации алгоритма оформлены грамотно, и при определенном навыке и квалификации можно использовать данное решение для записи того, что требует преподаватель.
Поскольку рисовать в чате Qwen не умеет, он привел список ребер.
Итоговое остовное дерево максимального веса:
Рёбра дерева:
- v₁-v₈ (вес 11)
- v₁-v₃ (вес 8)
- v₈-v₀ (вес 8)
- v₈-v₂ (вес 7)
- v₃-v₄ (вес 7)
- v₄-v₆ (вес 14)
- v₆-v₅ (вес 10)
- v₂-v₇ (вес 6)
Вес остовного дерева:
W(T) = 11 + 8 + 8 + 7 + 7 + 14 + 10 + 6 = 71
Лично для меня этой информации было бы достаточно, чтобы нарисовать пустой граф и добавить в него указанные в решении ребра. Но я решила представить, что думать я не хочу совсем, рисовать не умею, и перенести точки с условия на чистый листок - это непосильная задача. Мне проще написать промпт: "Нарисуй полученный граф".
Ладно, можно попросить нейронку собрать mermaid-скрипт для последующей вставки в draw.io.
Новая версия Qwen тоже научилась рисовать.
Но рисует она так же, как и GigaChat - на околотему и немного невпопад.
Причем, предлагает еще картинки в ассортименте. На выбор! Но будет ли это максимальное остовное дерево. Будет ли оно остовным. И будет ли, вообще, деревом?
В векторе Qwen также справляется лучше, нежели в растре. Но до рисования ответа так, чтобы легко было соотнести с условием задачи, и этой нейронке пока далеко. Про то, что в этом (хотя бы дереве) что-то не так, промолчим. Предлагаю читателю самостоятельно найти ошибки.
Задача 5. Построение эйлерова цикла при помощи алгоритма Флёри
О, это прекрасный алгоритм, который студенты часто любят заменять железобетонным "Мамой-клянусь" и приводить только ответ.
Возьмем достаточно простой пример, в котором три вершины (1,4,9) имеют степень 2, а остальные - степень 4. Следовательно, в графе существует эйлеров цикл, который можно построить из любой вершины. Приведу решение со всеми альтернативами выбора, чего и требую на контрольной работе.
GigaChat
1. Анализ степеней вершин
Прежде всего, проанализируем степени всех вершин графа:deg(v1v1) = 3
deg(v2v2) = 3
deg(v3v3) = 2
deg(v4v4) = 3
deg(v5v5) = 3
deg(v6v6) = 3
deg(v7v7) = 3
deg(v8v8) = 3
deg(v9v9) = 2
2. Проверка условий существования эйлерова цикла/цепи
По теореме Эйлера:Граф имеет эйлеров цикл тогда и только тогда, когда степень каждой вершины четна.
- Граф имеет эйлерову цепь тогда и только тогда, когда ровно две вершины имеют нечетную степень, а остальные — четную.
- В нашем случае имеем 7 вершин с нечетной степенью (v1,v2,v4,v5,v6,v7,v8v1,v2,v4,v5,v6,v7,v8), следовательно:Эйлеров цикл в данном графе не существует (так как не все степени вершин четные).
Эйлерова цепь в данном графе также не существует (так как более двух вершин имеют нечетную степень).
Комментарии излишни. Считать степени нейронка не умеет. Но мы-то, люди, еще в детстве учились считать отрезочки, примыкающие к жирной точечке.
Самое интересное другое. GigaChat не смущает большое число вершин нечетной степени, и он строит нечто, используя "алгоритм" Флёри для поиска пути, где каждое ребро, проходится хотя бы один раз.
Следуя правилам алгоритма Флёри (выбирать мост только в крайнем случае), строим путь:
v1→v3 (ребро 1)
v3→v4 (ребро 2)
v4→v5 (ребро 3)
v5→v6 (ребро 4)
v6→v9 (ребро 5)
Тут алгоритм попадает в тупик и возвращается в исходную вершину по уже посещенным ребрам:
v9→v6 (ребро 6)
v6→v5 (ребро 7)
v5→v4 (ребро 8)
v4→v3 (ребро 9)
v3→v1 (ребро 10)
Но далее находит что-то непройденное (и не существующее) и продолжает путь:
v1→v8 (ребро 11)
v8→v7 (ребро 12)
v7→v2 (ребро 13)
v2→v8 (ребро 14)
v8→v1 (ребро 15)
Qwen 3.6 Plus
В данном случае китайская нейронка более-менее справилась с поставленной задачей. С распознаванием картинки проблем у нее не возникло.
Шаг 1: Находим степени всех вершин графа
Проанализируем граф и подсчитаем степени вершин:
- deg(v1) = 2 (рёбра: 1-2, 1-3)
- deg(v2) = 4 (рёбра: 2-1, 2-3, 2-7, 2-8)
- deg(v3) = 4 (рёбра: 3-1, 3-2, 3-4, 3-5)
- deg(v4) = 2 (рёбра: 4-3, 4-5)
- deg(v5) = 4 (рёбра: 5-3, 5-4, 5-6, 5-8)
- deg(v6) = 4 (рёбра: 6-5, 6-7, 6-8, 6-9)
- deg(v7) = 4 (рёбра: 7-2, 7-6, 7-8, 7-9)
- deg(v8) = 4 (рёбра: 8-2, 8-5, 8-6, 8-7)
- deg(v9) = 2 (рёбра: 9-6, 9-7)
... далее разъяснения о существовании эйлеровых циклов.
В нашем случае: существует эйлеров цикл!
Шаг 3: Применяем алгоритм Флёри
Начнём с вершины v1. Алгоритм Флёри предписывает не проходить по мостам (рёбрам, удаление которых разъединяет граф), пока есть альтернатива
Далее нейронка пытается построить решение с доступными ребрами, как мы это делали в ручном решении. Но... попав на первый же мост, прекращает построение таблицы и просто приводит правильное решение. Мамой клянусь, верное. Qwen аккуратна и проверяет количество ребер в цепи, говорит, что все найдено верно. Да, я проверила за ней. Все верно. Но не на пятерку.
Выводы
1. Можно найти большую языковую модель, которая справится с контрольной работой по дискретной математике.
2. При желании, думаю, можно найти платную языковую модель или дообучить Qwen, чтобы получить отличное решение.
3. При загрузке условия с промптом "реши задачу" GigaChat не справляется совсем. Qwen 3.6 справляется, но выдает решение примерно на оценку 3, в лучшем случае 4-.
4. Большие языковые модели не используют детерминированные алгоритмы, поэтому результат надо проверять. И только вам решать, что быстрее и надежнее - записать решение с нуля самостоятельно или проверить решение, которое вам предоставлено кем-то или чем-то?
5. При повторных запросах, при уточнениях и выяснении "кто здесь дурак" любую нейронную сеть начинает глючить, и тогда уже точно на веру ничего принять нельзя.
6. Мое мнение остается неизменным: если не умеешь решать задачи, ищи скрипты-решатели, которые применяют алгоритм напрямую. Например, тот же Excel, чтобы посчитать определитель, обратную матрицу или что-нибудь еще. Да и старый добрый девайс калькулятор подводит намного меньше.
7. Конечно, все дело в "прокладке между рулем и сиденьем". Чтобы научиться получать правильные ответы от больших языковых моделей, нужны знания. А тем, кто сам не может решать задачи вроде приведенных выше, с языковыми моделями работать опасно.