Технотрек: Занятия 07, 08: Построить проект, вырастить дерево, родить левого или правого сына
(Копия блога на Технотреке)
Summary
Деревья - структуры данных, где мы совсем отказываемся от линейности, даже в логическом смысле. Для родительского узла дерева существует более одного "следующего" узла - например, левый и правый, называемых сыновними или дочерними узлами. Связь с родительским узлом у дочерних узлов может как быть, так и не быть; но с ней гораздо удобнее продвигаться от листьев дерева к его корню. Мы рассмотрели разные виды организации узлов деревьев и реализации связей между узлами.
Деревьев разного назначения и вида великое множество. В алгоритмических курсах часто рассматривают деревья поиска, хранящие данные и выдающие их как можно быстрее - то есть такие деревья представляют множества в их математическом смысле. Для этого им важно не содержать длинных путей от корня к листьям, и, если такой путь возникает, дерево перестраивается (балансируется) согласно различным алгоритмам. Структура связей такого дерева постоянно меняется, так как ее сохранение - не задача таких деревьев, главное, чтобы элементы искались максимально быстро.
Мы будем рассматривать такие деревья, в которых структура связей - важна. Роль таких деревьев - представлять взаимоотношения между объектами. Если у такого дерева меняются связи, то это должно быть следствием изменения таких отношений, и никак иначе. Поэтому понятие балансировки в таких деревьях бессмысленно, и если в них вдруг обнаружились длинные несбалансированные пути от корня - что ж, значит так построены взаимоотношения между объектами, которые это дерево отражает.
Для деревьев у нас будут три задачи, полторы из них рассматривались на прошедшей лекции: это экспертная система ("Акинатор") и убийца лаб по общефизу символьное дифференцирование.
Домашнее задание
1. Реализуйте проект "Акинатор" с возможностями:
- сохранения и загрузки базы данных,
- угадывания объекта,
- добавления нового объекта с указанием разделяющего свойства,
- выдачи определения указанного объекта,
- сравнения указанных объектов.
- Не забудьте захватить мир; TXSiri (см. ниже) уже делает это.
В качестве примера можно посмотреть проект "TxSiri" Артема Переведенцева, см. здесь. Видеопрезентация см. в разделе "Экспертная система TxSiri", исходный текст и исполняемые модули для Windows - в архиве по ссылке "Материалы". Если что там вдруг не идеально, не судите строго - автор учился в 8 классе :)
2. Реализуйте символьное дифференцирование с помощью деревьев:
- выражений "школьного" уровня (частные производные констант, переменных, сложения, вычитания, умножения, деления; степенной функции, синуса, косинуса как сложных функций);
- некоторых (или всех, по желанию) других элементарных функций;
- полной производной (THIS IS СПОГРЕШНОСТЬ! привет лабам по общефизу);
- с дампом в дерево через DotWiz;
- с дампом в TEX;
- с генерацией в TEX эпической псевдонаучной статьи о взятии полной производной во имя неразделенной любви к лабам по общефизу или матанализу. Можно ее прямо из программы отсылать преподу на электронную почту через вызов утилит командной строки для отсылки почты.
Некоторые примеры последнего задания, спешно сделанные в 3 часа ночи перед зачетом: Никита Остроухов, Булат Ниатшин, Артем Яшухин, Рома Глаз.
Часть этой работы - упрощение (оптимизация) дерева. Это будет разбираться на следующей лекции, поэтому второе задание - это "половина" полного задания.
***
Удачи, и May the Source be with you! :)