Автор: Львович
Решил вынести на отдельно обсуждение понятие "Сложность". Пока отдельные мысли на эту тему: 0) Понятие сложности нужно для сравнения разных задач и оценки ресурсов на их решение. 1) Сложность это интегральное свойство любого объекта в рамках некоторого контекста. 2) Контекст в данном случае - априорно известная информация об объекте. 3) Сложность это минимальное среднестатистическое количество вопросов с ответами ДА/НЕТ после которых становится известна вся информация об объекте. Пример: Контекст - "равновероятное целое число от 0 до 15" Количество необходимых вопросов - 4 Сложность - 4 4) Контекстом также является распределение вероятности любых параметров объекта. Если распределение вероятности не задается, то для конечного количества значений принимается равновероятное рапределение. 5) Контекст может предполагать конечное или бесконечное количество объектов или значений для свойств объекта. 6) Для бесконечного количества значений (объектов) должно обязательно задаваться распределение вероятности так, чтобы . Одним из простейших распределений является
Пример: Контекст - "целое неотрицательное число с вероятностью распределения (1)" Объект - число 8. Вопросы (по методу половинного деления с учетом вероятности): это число 1? это число 2? ... Количество необходимых вопросов -8. Сложность - 8.
Пример: Контекст - "граф переходов с n вершинами и m переходами из каждой вершины" Количество вопросов (сложность):
Теорема. Сложность системы, состоящей из нескольких невзаимодействующих подсистем, равна сумме сложностей этих систем. Строгого доказательства пока нет. Для числовых объектов вроде бы выполняется.
7) Сложность может быть введена и определена и для непрерывных свойств. Но тогда в контексте должна быть определена погрешность определения этого свойства. И конечно же плотность распределения вероятности особенно для бесконечных значений.
Напомню, что это только мысли... Может быть я изобретаю велосипед. Любая конструктивная информация приветствуется. |
|
да да да... рехнувщийся тролль и шизофреник, с лодкой в жопе Игнат Игнатов говорил про Вас, пытался пропиарить, но сложность это не математика а ЛЮДИ, сложность меряется в ЛЮДСКОМ ТРУДЕ, это экономика а не кибернетика.