sizeof (sizeof) wrote,
sizeof
sizeof

Categories:

Технотрек: Занятия 07, 08: Построить проект, вырастить дерево, родить левого или правого сына


(Копия блога на Технотреке)

Summary

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

Деревьев разного назначения и вида великое множество. В алгоритмических курсах часто рассматривают деревья поиска, хранящие данные и выдающие их как можно быстрее - то есть такие деревья представляют множества в их математическом смысле. Для этого им важно не содержать длинных путей от корня к листьям, и, если такой путь возникает, дерево перестраивается (балансируется) согласно различным алгоритмам. Структура связей такого дерева постоянно меняется, так как ее сохранение - не задача таких деревьев, главное, чтобы элементы искались максимально быстро.

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

Для деревьев у нас будут три задачи, полторы из них рассматривались на прошедшей лекции: это экспертная система ("Акинатор") и убийца лаб по общефизу символьное дифференцирование.

Домашнее задание

1. Реализуйте проект "Акинатор" с возможностями:
  • сохранения и загрузки базы данных,
  • угадывания объекта,
  • добавления нового объекта с указанием разделяющего свойства,
  • выдачи определения указанного объекта,
  • сравнения указанных объектов.
  • Не забудьте захватить мир; TXSiri (см. ниже) уже делает это.

В качестве примера можно посмотреть проект "TxSiri" Артема Переведенцева, см. здесь. Видеопрезентация см. в разделе "Экспертная система TxSiri", исходный текст и исполняемые модули для Windows - в архиве по ссылке "Материалы". Если что там вдруг не идеально, не судите строго - автор учился в 8 классе :)

2. Реализуйте символьное дифференцирование с помощью деревьев:
  • выражений "школьного" уровня (частные производные констант, переменных, сложения, вычитания, умножения, деления; степенной функции, синуса, косинуса как сложных функций);
  • некоторых (или всех, по желанию) других элементарных функций;
  • полной производной (THIS IS СПОГРЕШНОСТЬ! привет лабам по общефизу);
  • с дампом в дерево через DotWiz;
  • с дампом в TEX;
  • с генерацией в TEX эпической псевдонаучной статьи о взятии полной производной во имя неразделенной любви к лабам по общефизу или матанализу. Можно ее прямо из программы отсылать преподу на электронную почту через вызов утилит командной строки для отсылки почты.

Некоторые примеры последнего задания, спешно сделанные в 3 часа ночи перед зачетом: Никита Остроухов, Булат Ниатшин, Артем Яшухин, Рома Глаз.

Часть этой работы - упрощение (оптимизация) дерева. Это будет разбираться на следующей лекции, поэтому второе задание - это "половина" полного задания.

***

Удачи, и May the Source be with you! :)
Tags: Технотрек
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments