Современные подходы к представлению знаний

Формальная система (начальный, во многом дезавуированный в 80 годы, этап):

- знание представляется в виде формальной системы – основных предикатов, аксиом накладываемых на них, и правил вывода. В последнее время сюда включаются характеристики пространства, времени, а также модальности (долженствования) и этики.

Экспертная система:

Когда элементы знания сообщаются, хотя бы частично, человеком;

Онтология (современный этап):

- знание представляется в виде:

     (а) иерархии основных понятий,

     (б) системы отношений, в которых они участвуют (сюда могут включаться предикаты и правила вывода), и

     (в) индивидуальных фактов, соответствующих тем или иным отношениям.

Дискретная математика и графы

Сложность задач: алгоритмическая и полиномиальная невозможность.

              7.2 Графы и модели их порождения.

              7.3 Визуализация графов.

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

       7.1 Сложность задач: алгоритмическая и полиномиальная невозможность.

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

(а) сужение класса – обычно трудно, надо понимать специфику задач и ввести соответствующие ограничения;

(б) аппроксимационное или эвристическое решение;

(в) новые подходы на основе случайных элементов и агрегирования решений.