Возможности алгоритма и физической системы.

Помните, что общение на форуме не заменяет образования!

Возможно ли в принципе алгоритмическое решение задач распознавания образов?

Да, достаточно уровня алгоритмической, математической обработки сигнала.
6
55%
Нет, необходимо нужна физическая система, дающая принципиальную возможность распознавания.
5
45%
 
Total votes: 11

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Fri May 23, 2008 9:38 am

Хмур wrote: Ээ.. Многоуровневый параллельный алгоритм, когда события одного
уровня выступают как данные для другого, особенно в асинхронном
режиме, вряд ли можно адекватно представить в последовательном виде..
у тебя тут некоторая путаница: асинхронный режим подразумевает некую физическую реализацию, а это уже не алгоритм, а прибор... если же ты эту асинхронность описываешь математически, то ты должен ввести источник случайности, то есть постулировать, что твой алгоритм постоянно получает новую информацию... это не совсем честно по отношению к обычным алгоритмам, не находишь? ) конечно, введение мистического источника информации неалгоритмизуемо )
а в остальном, алгоритмически неразрешимые проблемы в равной степени неразрешимы с помощью параллельных алгоритмов
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

stilda
Posts: 110
Joined: Tue Mar 11, 2008 11:30 am
Location: Киев

Post by stilda » Tue May 27, 2008 8:07 pm

Хмур wrote:Что параллельность в общем случае не сводима к последовательности.
Я согласен, но интересно слышать ваши пояснения этого...
Хмур wrote:Замечания о связи с алгебраическими расширениями не понял..
Поверхностно представляю себе так: места сети отвечают за мнимые единицы, переходы между местами задают законы "сложения" мнимых единиц. Количество фишек в месте - количество данной мнимой единицы.
Например, можно получить систему переходов
1*место1 + 1*место2 -> 1*место3 + 1*место4 + 1*место5
1*место5 + 1*место2 -> 1*место3 + 1*место1
Что-то, типа этого. Детально не разбирался. Можно попробовать под конкретную алгебру построить сеть.
Глупая правдивость полезна

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Wed May 28, 2008 9:38 am

Хмур wrote:.
параллельность в общем случае не сводима к последовательности.
Все-таки мне бы хотелось отметить следующее: если есть конечный набор параллельно работающих элементов, срабатывающих в дискретные (и предсказуемые) моменты времени, то можно построить эквивалентную последовательную систему, если ее элементы работают быстрее. Это факт.
Конечно, если времена срабатывания априорно неизвестны (случай истинной асинхронности), то промоделировать действие такой системы нельзя (поскольку о ней имеется не вся информация). Но добавление такой асинхронности можно заменить эквивалентным источником хаоса и для последовательных систем. ИМХО, это уже вопрос не последовательности и параллельности, а случайности и детерминированности.

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

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

Таким образом, если вернуться к исходному вопросу (с которого началась дискуссия про последовательность-параллельность), то параллельность никаких принципиально новых свойств не дает. Вопрос о случайности-детерминированности и континуальности-дискретности нужно рассматривать отдельно (хотя эти вопросы также относятся к данной теме).
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Wed May 28, 2008 10:05 am

Inex wrote:Все-таки мне бы хотелось отметить следующее: если есть конечный набор параллельно работающих элементов, срабатывающих в дискретные (и предсказуемые) моменты времени, то можно построить эквивалентную последовательную систему, если ее элементы работают быстрее. Это факт.
И да и нет. Естественно все что алгоритммизуется может быть выраженно на машине Тьюринга. Однако задача переключения между процессами (задача планировщика) сама по себе является NP полной. Соответсвенно такое моделирование не всегда возможно по комбинаторным причинам.
Таким образом, если вернуться к исходному вопросу (с которого началась дискуссия про последовательность-параллельность), то параллельность никаких принципиально новых свойств не дает. Вопрос о случайности-детерминированности и континуальности-дискретности нужно рассматривать отдельно (хотя эти вопросы также относятся к данной теме).
Дает, она подавляет задачу планировщика. В случае с квантовым регистром эффект вообще огромный.
весь мир, бензин и спички ;)

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Wed May 28, 2008 10:44 am

2 Lex
не совсем понимаю, о чем ты... эмуляция многозадачности приводит только к кратной потере скорости
если же речь идет о дизайне системы, то распараллеливание - задача существенно более сложная, чем создание последовательного алгоритма (если есть независимые потоки, то планировщик не нужен, достаточно тупого переключения между задачами; если же система такова, что нужен планировщик, то дизайн параллельного решения не менее сложен)
про квантовые же компьютеры и NP-полноту речь здесь не шла (вернее, косвенно шла, но чуть раньше)

я говорю не то, что параллельность (в классическом смысле) не нужна, а то, что она дает те же алгоритмические решения
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Lex
Posts: 1862
Joined: Thu Aug 26, 2004 8:12 pm

Post by Lex » Thu May 29, 2008 10:49 am

Если между потоками есть взаимное влияние, то задача планирования совсем не тривиальна. Нужны объекты синхронизации и вся обвязка над ними. В общем случае это неразрешимо.

Многопоточность действительно не дает никакого выйгаша над стандартными алгоритмами. Даже квантовый регистр пока не дает ( кроме скорости). Хотя возможно тут не все нарыли. Вообще машина Тьюринга пока себя не исчерпала. Кроме проблемы останова других серьезных недостатков у нее пока нет.

Я думаю что никакая физическая система не может дать алгоритмических преимуществ над машиной Тьюринга. На сегодняшнем уровне знаний конечно.
весь мир, бензин и спички ;)

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Thu May 29, 2008 11:38 am

2 Lex
Ну, по главному пункту наши мнения, значит, сходятся.
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

stilda
Posts: 110
Joined: Tue Mar 11, 2008 11:30 am
Location: Киев

Post by stilda » Thu May 29, 2008 3:17 pm

Lex wrote:Я думаю что никакая физическая система не может дать алгоритмических преимуществ над машиной Тьюринга.
Слово "алгоритмических" существенно или можно выбросить?
Inex, я задавал вам вопрос, если хотите, можно ответить ).

В чем отличие последовательности и паралельности?

Ведь для машины Тьюринга не существует понятий "круг", "квадрат", "лицо" и так далее. Эти понятия могут родится только в паралельно воспринимающей системе.

Что скажете?
Глупая правдивость полезна

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Thu May 29, 2008 8:35 pm

stilda wrote:
сделаю прибор, сканирующий картину с частотой 24 Гц )
вроде мы уже обсуждали развертку на ЭЛТ мониторе
а зачем?
Этот вопрос? Я подумал, что он риторический.
Повторюсь: вроде мы уже обсуждали развертку на ЭЛТ мониторе.
Человеческое восприятие работает в определенном масштабе времени. Развертка (последовательная) воспринимаемой информации должна соответствовать этому масштабу, не более того.

Тогда я встречный вопрос задам: ты смотришь фильм, замедленный в 10^12 раз. Каковы твои действия, чтобы понять его содержание? Замечу, все воспринимается непрерывно и параллельно.
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Thu May 29, 2008 8:37 pm

stilda wrote: Ведь для машины Тьюринга не существует понятий "круг", "квадрат", "лицо" и так далее. Эти понятия могут родится только в паралельно воспринимающей системе.

Что скажете?
скажу, что это глупость; есть алгоритмы, которые способны распознавать круги и квадраты и даже строить такого рода обобщения без априорного знания о их существовании
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

stilda
Posts: 110
Joined: Tue Mar 11, 2008 11:30 am
Location: Киев

Post by stilda » Fri May 30, 2008 1:34 pm

Inex wrote:Человеческое восприятие работает в определенном масштабе времени. Развертка (последовательная) воспринимаемой информации должна соответствовать этому масштабу, не более того.
Основное то, что вам понадобилось увидеть все изображение сразу (а не последовательно во времени). Есть временные сигналы и есть пространственные (связанные с паралельностью).
Inex wrote:есть алгоритмы, которые способны распознавать круги и квадраты и даже строить такого рода обобщения без априорного знания о их существовании
Не путайте объект и развертку объекта. Никакая машина тьюринга не работает с пространственными объектами и не имеет про них ни малейшего понятия. Все работает только с их развертками. Это основной пункт из-за которого возник вопрос и сомнения в возможностях алгоритмов по сравнению с физической системой.
Тогда я встречный вопрос задам: ты смотришь фильм, замедленный в 10^12 раз. Каковы твои действия, чтобы понять его содержание? Замечу, все воспринимается непрерывно и параллельно.
Ускорю фильм либо за счет своей памяти либо за счет скорости воспроизведения.
Глупая правдивость полезна

DS
Posts: 949
Joined: Tue Jan 06, 2004 6:17 am

Post by DS » Fri May 30, 2008 2:24 pm

-"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите".
-"Глупая правдивость полезна".

Inex
Posts: 2331
Joined: Mon Jan 05, 2004 10:33 am
Location: Санкт-Петербург

Post by Inex » Fri May 30, 2008 4:43 pm

stilda wrote:Основное то, что вам понадобилось увидеть все изображение сразу (а не последовательно во времени). Есть временные сигналы и есть пространственные (связанные с паралельностью).
да не надо сразу! сколько раз говорить!!! достаточно увидеть все точки поочереди в течение, хотя бы, 1 секунды... можно, конечно, говорить, что в мозгу накапливается информация, которую мозг затем обрабатывает одновременно, но это не имеет отношения к твоему примеру...
еще раз, при наличии самостоятельных элементов (типа нейронов) не имеет абсолютно никакого значения, работают ли они одновременно! нейроны разряжаются несинхронизовано и в ____разные_____ моменты времени; моменты разрядки нейронов не могут в точности совпадать; более того (см. теорию относительности), каждый из них работает в своем времени. Все моменты возникновения спайков всех нейронов при большом желании можно выстроить в последовательность и построить эквивалентный последовательный процессор, который быстро по ним пробегает и разряжает нейроны в соответствующие моменты времени
понятие одновременности пространственно-относительно!!!
stilda wrote: Ускорю фильм либо за счет своей памяти либо за счет скорости воспроизведения.
по поводу памяти жжош! а про скорость воспроизведения та же фигня, что и с быстрым последовательным просмотром картинки, так что твой ответ гипотенуза (в смысле, не катит).
stilda wrote:Не путайте объект и развертку объекта. Никакая машина тьюринга не работает с пространственными объектами и не имеет про них ни малейшего понятия. Все работает только с их развертками. Это основной пункт из-за которого возник вопрос и сомнения в возможностях алгоритмов по сравнению с физической системой.
Иди учи физику, в частности, теорию относительности о пространственно-временном континууме, а таже математику в области теории множеств о кардинальных числах. Я - пас...
"Когда Вы говорите, Иван Васильевич, у меня такое чувство, что Вы бредите"

Egg
Posts: 2693
Joined: Fri Jan 02, 2004 9:13 pm
Location: Boulder, CO
Contact:

Post by Egg » Fri May 30, 2008 4:48 pm

Цой (С): Тот, кто в пятнадцать лет убежал из дома, вряд ли поймёт того, кто учился в спецшколе... / конец цитаты... :)
Давайте уже отделять котят от котлет!

Солеваров
Posts: 5301
Joined: Wed Jan 07, 2004 5:46 am
Location: все из *****
Contact:

Post by Солеваров » Sat May 31, 2008 6:05 am

Inex wrote: ... моменты разрядки нейронов не могут в точности совпадать; более того (см. теорию относительности), каждый из них работает в своем времени. Все моменты возникновения спайков всех нейронов при большом желании можно выстроить в последовательность и построить эквивалентный последовательный процессор, который быстро по ним пробегает и разряжает нейроны в соответствующие моменты времени
понятие одновременности пространственно-относительно!!!...
- эээ ... с относительностью это сложно к пониманию :) можно проще объяснить, мозг не машина, поэтому пока одни нейроны работают разряжаясь, другие релаксируют и есть некоторое число нейронов занятых в многосложных реакциях переходов между работой и релаксацией как в ту так и в другую сторону. поэтому и возникает групповая асинхрония в следствии которой можно допустить что из всех нейронов возможно построить огроменную последовательность.
Usus est optimus magister

Locked

Who is online

Users browsing this forum: No registered users and 1 guest