Алгоритмы все таки предполагают, что они будут реализованы на подходящей для размера задачи машине, а не на первой попавшейся. Может быть, когда машина выбрана, размер оперативной памяти уже внешняя константа, однако я предполагаю, что вам будет удобно решать большие задачи на машинах с большим размером памяти, а маленькие, из моих слов, — будут быстрее считаться на маленьких ЭВМ. Именно в момент выбора подходящей плохой машины логарифм и выстрелит.
Принципиально можно так сконструировать шину, чтобы (упрощенно) адрес распадался на длинный адрес сегмента и короткий адрес ячейки в сегменте, при этом на машинном уровне шине сообщалось, будут ли ближайшие запросы попадать в один и тот же сегмент. В этой ситуации программы можно так писать, чтобы N было размером структуры данных, размещаемой внутри оперативной памяти. В плохо сделанных компьютерах N будет размером оперативной памяти.
Я настаиваю на несколько другой идеи:
Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
Если не для тех, кто пишет программы, то для кого проводились исследования и строилась теория вычислительной сложности? «Глас народа — ...». Оценки сложности всегда даются по отношению к некоторой конкретной вычислительной модели, и тот факт, что народ негодует по поводу применяемой RAM модели с доступом к памяти за ограниченное константой количество ходов машины имеет на самом деле не только расхождение с реальными машинами но и некоторые противоречия с теорией передачи информации. Вот вам задачка:
Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?
Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.
По всей видимости, с бутылочными горлышками в последнее время борются расширяя тротуары и убирая при этом лишние полосы. Метод действенный, но не самый эффективный: возможно большое количество водителей использовали исключительно широкий участок некоторой дороги, сворачивая с нее задолго до горлышка. Теперь выходит, что этот участок стал перегруженным, даже если никакого горлышка уже нет. Один из способов бороться с горлышком, не сужая дороги перед ним — система раздельных светофоров на каждую полосу перед сужением и физическое разграничение этих полос. Светофоры должны открываться поочередно, пропуская движение по стольким полосам, сколько их (полос) в узком месте.
Пропускная способность дороги тоже не самоцель: можно построить очень широкую дорогу с достаточно медленным движением: в итоге у комиссии в отчетах большая пропускная способность, а водители теряют попусту значительное время. Нужен некоторый компромисс между количеством проезжающих машин и потраченным каждой из них временем. Я немного исследовал вопрос оптимальной транспортной сети в городе и, как тогда мне показалось, неплохой критерий есть экономическая мощность дороги: миграция — это торговые связи, они приносят деньги, а само время прохождения дороги каждой машиной их тратит (заработная плата+амортизация). Если вы градоначальник или хотите жить в экономически развитой стране, то будете (не перед выборами, конечно) оптимизировать именно экономическую мощность дороги, а не скорость или поток в отдельности.
Интересным образом задача поиска оптимальной дорожной сети города оказывается переформулировкой задачи коммутации N источников и N стоков. Когда-то я искал схему оптимальной коммутации, результаты публиковались на хабре в статье «Задача телефонисток», может быть дойдут руки написать и про дороги.
Еще хотелось бы уточнить у авторов вид графика поток-скорость: все-таки наверное сначала рост концентрации хоть и приводит к снижению скорости, но поток при этом должен расти, только при значительном уплотнении поток стремительно падает. Если же график монотонный, как на рисунке, то движение просто не устойчивое и пробки должны образовываться всегда, везде, от каждого чиха любого водителя, а не только в проблемных местах дороги.
Энтропийная мощность марковского передатчика (энтропия Шеннона) — абсолютная не зависящая не от чего величина, применимая всюду, где по крайней мере можно утверждать вероятностный либо статистически устойчивый характер процесса.
К примеру взяв 20 типографских оттисков буквы «а» 15 — буквы «б» и 65 — буквы «в» с помощью энтропийной мощности в отсутствие всякой вероятности Вы можете подсчитать количество различных слов длины 100, составленных из этих оттисков.
Если следовать примеру выше и разбить область значений синусоиды на небольшие участки, то получится, что принимая любое значение кроме крайних, почти равновероятен как переход в состояние с большим значением, так и переход в состояние с меньшим. Выходит, что синусоидальный сигнал, будучи полностью предсказуемым, имеет ненулевую энтропийную мощность в качестве марковского передатчика?
Что касается бинарных последовательностей, до сих еще никто не справились с задачей дать удовлетворительную меру сложности единичного конструктивного объекта в себе, колмогоровская сложность безотносительно машины или языка определена лишь для неограниченно усложняющихся последовательностей таких объектов. Иными словами, если наперед задан объект, то можно предъявить машину, относительно которой его сложность равна нулю, как бы он интуитивно сложен не был, и машину, относительно которой сложность этого объекта будет невероятно большой, даже если он интуитивно прост.
Простите, а какая главная мысль статьи? Второй вопрос — как все-таки строится модель энтропийного передатчика для конкретного процесса, например если процесс на осциллографе — правильная синусоида?
Большое спасибо. Только в этой книге говорится немного о другом. Моя идея была описать вещь, не привлекая никаких заранее сформированных структур вроде фреймов или графовых схем на бумаге — я показал на примере, как сформировать представление о предмете как принципиально новое понятие непосредственно в терминах символьной последовательности.
К тому же, вот мнение автора книги, прямо противоположное моим выводам:
«Строятся ли такие системы фреймов для каждого знакомого нам объекта? Это выглядело бы слишком экстравагантно. Представляется более вероятным, что у человека имеются специальные системы для представления наиболее важных объектов, а, кроме того, множество фреймов для обычно используемых „основных форм“; их сочетания образуют фреймы для новых применений.»
Да, в моей статье и в приведенной вами книге, говорится об одной и той же задаче и о совершенно различных способах ее решения.
Как же вы собираетесь определить формально для машины «уметь» и «личное действие»? Я, в свою очередь, пока имею только догадки на этот счет. Считается, к тому же, правилом хорошего тона производить логические построения при минимальных требованиях: абстракции предмета, места и формы доступны и восприятию машин, напрочь лишенных какой-либо возможности действовать, не то что форм самосознания.
Решив простую задачу, часто удается найти ключ и к задаче посложнее. Даже в том виде, который есть, изложенные методы позволяют справится с вещами вроде револьвера и автомобиля. В законах Максвелла тоже нет соринок и скрытых параметров веселости электрика: именно простота академической базы знаний позволяет быть сложными их практическим приложениям. Цель статьи — как раз раскрыть принципы того, как в условиях отсутствия объективной реальности строится субъективное представление о различных понятиях. «Поваренной книгой» она конечно же не является.
Друзья! давайте во избежания конфликтов и введения читателей в заблуждение, всякий раз, говоря, что что-то есть пересказ, переписка или перепечатка, не ленится и давать ссылку на конкретную публикацию или главу книги. В свою очередь, я снова заявляю, что центральная и идея и все примеры — мои собственные и вряд ли встречались где-то до настоящего момента. Если же Вы предъявите конкретную статью, с ровно такими же мыслями, я буду только рад своему неодиночеству в мире.
Не читайте на завтрак советских газет, и книги советских авторов тоже раньше ужина не стоит, иначе действительно развивается как у Вас впечатление, будто они все открыли, а остальные у них списывают. Кому, по вашему, мир обязан открытию теории информации (пропускная способность каналов с шумом и без)?
Шеннон — не только автор теорий, он еще и автор элегантно написанных, в доступной форме преподносящих даже самые сложные идеи книг. Многие слышали об энтропии: какая-то взявшаяся с неба мера беспорядка из учебников по статистике, так думал и я, пока в его трудах по теории информации мне не попалась глава, раскрывающая всю естественность и изящность этого понятия. Странная история, когда полки магазинов прогибаются под не лучшими пересказами научных идей, первооткрыватели которых со временем становятся рекламной вывеской этого сомнительного товара.
Давайте отметим юбилей, размышляя над какой-нибудь статьей именинника!
Шеннон — ученый, гуманист, популяризатор науки.
Правда, могут возникнуть расхождения, если зонд двигается внутри большого одноцветного пятна и в ряде схожих ситуаций. Я вспомнил, что тоже сначала пытался без лампочек движения
Если среди простых движений нет дальних скачков, то Ваше замечание абсолютно справедливо, когда слово паттерн (устойчивая закономерность) понимается в смысле «цветовая конфигурация части индикаторов цвета».
Простите, что не ответил сразу — счел статью интересно и хотел для начала прочитать. В ней тоже не все утверждения обоснованы: например о длительности вычисления параллельными машинами. Я много занимался этой проблемой и смог привести вычислительную модель, которая логарифмировала время (количество шагов) вычисления стандартных алгоритмов: сортировки, поиска по свойству и обращению к памяти. Эта статья тоже присутствовала на хабре — ее любезно согласилчя разместить из под своего юзернейма, но с моей подписью мой приятель. Редакторы хабра даже помогли по-человечески отверстать текст, но при этом потерялось мое имя. В любом случае, гугл еще ищет «Компьютер из маленьких фей». В другой работе «Задача телефонисток» Вы сможете найти обоснование возможности физической реализации вычислительной машины с такой архитектурой.
В любом случае, большое спасибо, подчерпнул для себя много интересного.
Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?
Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.
Пропускная способность дороги тоже не самоцель: можно построить очень широкую дорогу с достаточно медленным движением: в итоге у комиссии в отчетах большая пропускная способность, а водители теряют попусту значительное время. Нужен некоторый компромисс между количеством проезжающих машин и потраченным каждой из них временем. Я немного исследовал вопрос оптимальной транспортной сети в городе и, как тогда мне показалось, неплохой критерий есть экономическая мощность дороги: миграция — это торговые связи, они приносят деньги, а само время прохождения дороги каждой машиной их тратит (заработная плата+амортизация). Если вы градоначальник или хотите жить в экономически развитой стране, то будете (не перед выборами, конечно) оптимизировать именно экономическую мощность дороги, а не скорость или поток в отдельности.
Интересным образом задача поиска оптимальной дорожной сети города оказывается переформулировкой задачи коммутации N источников и N стоков. Когда-то я искал схему оптимальной коммутации, результаты публиковались на хабре в статье «Задача телефонисток», может быть дойдут руки написать и про дороги.
Еще хотелось бы уточнить у авторов вид графика поток-скорость: все-таки наверное сначала рост концентрации хоть и приводит к снижению скорости, но поток при этом должен расти, только при значительном уплотнении поток стремительно падает. Если же график монотонный, как на рисунке, то движение просто не устойчивое и пробки должны образовываться всегда, везде, от каждого чиха любого водителя, а не только в проблемных местах дороги.
К примеру взяв 20 типографских оттисков буквы «а» 15 — буквы «б» и 65 — буквы «в» с помощью энтропийной мощности в отсутствие всякой вероятности Вы можете подсчитать количество различных слов длины 100, составленных из этих оттисков.
Простите, а какая главная мысль статьи? Второй вопрос — как все-таки строится модель энтропийного передатчика для конкретного процесса, например если процесс на осциллографе — правильная синусоида?
К тому же, вот мнение автора книги, прямо противоположное моим выводам:
«Строятся ли такие системы фреймов для каждого знакомого нам объекта? Это выглядело бы слишком экстравагантно. Представляется более вероятным, что у человека имеются специальные системы для представления наиболее важных объектов, а, кроме того, множество фреймов для обычно используемых „основных форм“; их сочетания образуют фреймы для новых применений.»
Да, в моей статье и в приведенной вами книге, говорится об одной и той же задаче и о совершенно различных способах ее решения.
Давайте отметим юбилей, размышляя над какой-нибудь статьей именинника!
Шеннон — ученый, гуманист, популяризатор науки.
Задача телефонисток
В любом случае, большое спасибо, подчерпнул для себя много интересного.