Вот вы можете отличить программу которую писала большая корпорация 10 лет от программы которую слабал Петя за 15 минут с кофе? Как правило, первая большая, с большим количеством осмысленных инструкций, хорошо структурирована и пр. А Петя начеркал 100 кривых строчек на скорую руку.
Можно ли сказать что одна программа сложнее другой? Или же это все не объективно и нельзя точно сказать?
Что если Петя создал 100 строк, которые сгенерили 10 млн. строк программного кода. Ведь мы можем сказать что хоть их и 10 млн., они проще чем 1 млн. строк, которые создавала корпорация 5 лет?
Есть ли в информатике понятие сложности программы?
Есть вычислительная сложность алгоритма, но это совсем другое.
Здравствуйте, Shmj, Вы писали:
S>Есть ли в информатике понятие сложности программы?
Сложность это мера неоднородности. Для ее численного выражения существует мера цикломатической сложности
S>Есть вычислительная сложность алгоритма, но это совсем другое.
То что тебе нужно рассматривается не в информатике, а в теории сложных систем.
Здравствуйте, LaptevVV, Вы писали:
S>>Есть ли в информатике понятие сложности программы? S>>Есть вычислительная сложность алгоритма, но это совсем другое. LVV>Колмогоровская сложность
как мне кажется есть две категории "сложности".
есть сложность обьективная: насколько сама задача обьективно сложная. колмогоровская сложность здесь в тему.
есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
S>>>Есть ли в информатике понятие сложности программы? S>>>Есть вычислительная сложность алгоритма, но это совсем другое. LVV>>Колмогоровская сложность DM>как мне кажется есть две категории "сложности". DM>есть сложность обьективная: насколько сама задача обьективно сложная. колмогоровская сложность здесь в тему. DM>есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
Ну, ТС спрашивал об объективной сложности.
Восприятие сложности текста (в том числе и текста программы) субъективно, но тоже основано не на пустом месте.
Зависит от построения текста. Например, длинные предложения воспринимаются хуже (более сложные), чем короткие.
Есть исследования по оцениванию сложности текстов.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, pestis, Вы писали:
P>Сложность это мера неоднородности. Для ее численного выражения существует мера цикломатической сложности
Ну смотрите. Вася сбацал за 15 мин прогу, которая на основе ГСЧ дает миллионы циклов и условий. А корпорация делала осмысленно прогу с таким же кол-вом циклов и условий несколько лет.
Здравствуйте, LaptevVV, Вы писали:
LVV>Колмогоровская сложность
Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? Но ведь будет понятно что это всего лишь кодогенеренная прога и трудовые затраты на ее создание не велики.
Здравствуйте, DreamMaker, Вы писали:
DM>есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
Вот это уже ближе. Ведь можно сгенерить прогу с произвольным количеством условий и циклов, но спецу будет видно что это фуфло ничего полезного не делает.
Здравствуйте, LaptevVV, Вы писали:
LVV>Зависит от построения текста. Например, длинные предложения воспринимаются хуже (более сложные), чем короткие. LVV>Есть исследования по оцениванию сложности текстов.
Смотрите. Мой вопрос в корне имеет эволюцию. Вот всем нам понятно что ДНК человека совершеннее ДНК козы. Совершеннее. И больше по размеру. И дает качественно иной результат. Но как это выразить математически?
Вот я хочу сделать эволюцию программ. А как мне сделать сравнение на уровне системы какая программа более совершенная (такие должны "выживать") а какая программа менее совершенная (такие должны "погибать")?
Здравствуйте, Sinix, Вы писали:
S>>Смотрите. Мой вопрос в корне имеет эволюцию. Вот всем нам понятно что ДНК человека совершеннее ДНК козы. Совершеннее. S>Дафния смотрит на вас с недоумением.
Она больше по размеру -- но кто сказал что сложнее?
Я вам могу дать проект, в котором миллион классов, 10 млн. функций, некие циклы и условия. Причем все совсем разное, архиватором не сильно ужимается. Но потрачено времени на его разработку всего лишь пара часов -- все автогенеренное на основе ГСЧ.
Понятна идея?
Размер != сложность.
S>Если коротко, то в итоге получится как-то так
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Колмогоровская сложность
S>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)?
Нет, не получится. У всех этих сгенеренных программ сложность будет не выше, чем размер самого генератора. См. определение.
Более того, эта сложность вообще невычислима, насколько я помню.
Здравствуйте, D. Mon, Вы писали:
DM>Более того, эта сложность вообще невычислима, насколько я помню.
Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. wiki
Получается для очень систем эта оценка сложности не применима.
S>Она больше по размеру -- но кто сказал что сложнее? S>Размер != сложность.
Это зависит от исходных постулатов.
Вполне можно строить некую теорию на основе вот такой простой меры — длина строки.
Другое дело, что эта теория не совсем нас устраивает чисто субъективно.
Ибо:
abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
Две строки — одного размера, но первая строка выглядит проще второй. Или вторая — сложнее первой.
Колмогоровская сложность — как раз и есть некоторая формализация вот такого интуитивного представления.
Неформально можно сказать, что сложность — мера разнообразия.
Первая строка — однообразна, вторая — намного разнообразнее.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
LVV>>Есть исследования по оцениванию сложности текстов. S>Чтобы его оценить -- его нужно понять. А математика такими терминами пока не оперирует. Видимо в этом проблема.
Не обязательно. Смысл — это субъективная интерпретация.
Так же как теория формальных грамматик не оперирует смыслом, а только формой — можно строить понятие сложности текста на основе сложности формы.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Колмогоровская сложность
S>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? Но ведь будет понятно что это всего лишь кодогенеренная прога и трудовые затраты на ее создание не велики.
Не все так просто.
Слово "произвольный" — тут не подходит.
На практике невозможно создать программу генерирующую строку бесконечной сложности.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
DM>>Более того, эта сложность вообще невычислима, насколько я помню. S>Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. wiki S>Получается для очень систем эта оценка сложности не применима.
Ну дык есть алгоритмически неразрешимые проблемы. И что?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
