|
Автор
|
Тема: Искусственный Интеллект и Сознание
|
|
AesirLoki
|
написано:09-04-2004 15:08:46
|
106
|
малюк
Размер сортируемых елементов влияет следующим образом : t(n, m) = O(n*m) где m - кол-во разрядов
Дык, я и говорю: почувствуйте разницу между O(n) и O(n * m). Это уже сродни разнице между псевдополиномиальными и полиномиальными задачами.
В случае сортировок со сравнением будет необходим тот же множетель что и здесь. Просто обычно предполагается, что сравнение - операция выполняемая за конст. времени.
Тут ты на ходу аксиоматику правишь, то есть, подменяшь предмет обсуждения. Теория сложности работает с некими абстрактными "элементарными операциями" (в данном случае - сравнения) и считает именно их. Впрочем, если вернуться к совсем классической постановке вопроса, с машиной им. тов. Тьюринга и длиной записи условия, то у твоей сортировки O(n) может уже и не получиться - придется долго и упорно бегать по записям длиннющих чисел. А может, и получится... думать над этим лень.
это значит, что существует такие m и p, что для любого n>m верно t(n)Именно так!
А что такое здесь p и зачем оно?
ц и т а т а
|
|
малюк
|
написано:09-04-2004 15:42:33
|
107
|
AesirLoki
почувствуйте разницу
Так заметь! Теорема тогда тоже превращается в O(n*ln(n)*m)
Это уже сродни разнице между псевдополиномиальными и полиномиальными задачами.
нифига.
А что такое здесь p и зачем оно?
Это лишь определение f(x)=O(g(x)) - смотри учебники зачем. Без нотации очень неудобно пояснять.
Впрочем, если вернуться к совсем классической постановке вопроса, с машиной им. тов. Тьюринга и длиной записи условия
Ну-ну. Там вообще алфавит есть. Сортировка на МТ это для особо одаренных. Я опять говорю о реальности, зачем тебе заморочки. То, что оценка поразрядной сортировки не O(n) будешь Кнуту доказывать, чего уперся, а?
ц и т а т а
|
|
AesirLoki
|
написано:09-04-2004 15:54:53
|
108
|
малюк
То, что оценка поразрядной сортировки не O(n)
Именно. И ты сам признал, что там есть еще один множитель. А если этот множитель зафиксировать, то получаем ограничение на размер задачи.
будешь Кнуту доказывать
Авторитет кнута, а уж тем более пистолета непререкаем, супротив них я спорить не буду :) С пряником - еще поспорил бы, может, и то если только не голоден :)
А если серьезно, то ссылки на авторитеты не канают. Я еще в школе вредный был (а сейчас я полезный), с учителями спорил, иногда даже успешно :) Есть некая аксиоматика, и если есть некие утверждения в ней, с которыми я несогласен - буду спорить, если не надоест раньше; а кто конкретно высказал мнение, с которым (после передачи его через испорченный телефон) я несогласен - плевать. От гипноза авторитетов надо избавляться.
ц и т а т а
|
|
малюк
|
написано:09-04-2004 16:07:00
|
109
|
AesirLoki
А если этот множитель зафиксировать, то получаем ограничение на размер задачи.
Каким же образом?
Да, Кнут сакс, я просто надеялся что ты на определение глянешь, а куда тебя послать сходу лучше не придумал (за опредлением ессно).
Ты говоришь, что верхняя оценка зависимости времени сортировки от количества елементов не является линейной функцией - продемонстрируй это и заодно скажи-ка, каким образом это влияет на то, что абсолютное большинство программеров считают такую сортировку именно НЕВОЗМОЖНОЙ.
ц и т а т а
|
|
малюк
|
написано:09-04-2004 16:11:44
|
110
|
AesirLoki
А ты такую сортировку видел - чтобы без сравнений?
Вот об этом, на самом деле, речь, упертый Локи.
Вот о таких ловушках понимания речь шла в теме.
Если сказать человеку, что есть шняга под названием ТС, позволяет собирать разные миры, а он - хопа! - бритву Оккама из кармана и - чик! - а других миров нету, значит и ТС ненужное усложнение представлений о мире.
малюк
мы, как правило, других сортировок не знаем мы сокращаем память о ней до первого варианта (как и почему это происходит я в этой теме уже писал) и потом, на сортировку за линейное время O(n) нормальной реакцией является "это невозможно"
ц и т а т а
|
|
AesirLoki
|
написано:09-04-2004 16:31:13
|
111
|
малюк
Нежелание признавать сходу и без споров тех же авторитетов, что и ты, ты называешь "упертостью"? Сочувствую, но не присоединяюсь.
Ты говоришь, что верхняя оценка зависимости времени сортировки от количества елементов не является линейной функцией - продемонстрируй это
Подсунь этому алгоритму сортировки 2 одинаковых (ладно, разрешаю им различаться в младшем разряде) вектора длины M - и ты увидишь, что пыхтеть он будет O(M) операций, притом что n (количество сортируемых элементов) вообще фиксировано и равно 2.
А если этот множитель зафиксировать, то получаем ограничение на размер задачи.
Каким же образом?
Читай внимательнее сообщение 104.
ц и т а т а
|
|
малюк
|
написано:09-04-2004 16:42:27
|
112
|
Подсунь этому алгоритму сортировки 2 одинаковых (ладно, разрешаю им различаться в младшем разряде) вектора длины M - и ты увидишь, что пыхтеть он будет O(M) операций, притом что n (количество сортируемых элементов) вообще фиксировано и равно 2.
Оценка от количества сортируемых елементов по прежнему линейная это раз. Любой алгоритм будет сравнивать два числа O(M) операций, это два.
С чем же ты не согласен?
сообщение №104
а значит, чтобы применить этот алгоритм, мы должны заранее ограничить количество сортируемых объектов
полная херня. неверно.
ц и т а т а
|
|
Сяо Лао
|
написано:10-04-2004 10:37:29
|
113
|
Ну пацаны. Ну сцепились! Ай молодцы! Сортировка от слова сортир? И при чем здесь ИИ? Если уж такая базовая операция программирования как сортировка вызвала столько споров, то про ИИ (про одно только опреление его) можно биться до зеленого посинения. Вы бы оглянулись на самих себя, о чем базар то?
ц и т а т а
|
|
temp
|
написано:11-04-2004 03:36:28
|
114
|
Практически каждое слово имеет несколько вариантов морфологического значения, что как правило порождает несколько разных вариантов верных синтаксических структур описывающих это предложение и что совсем портит картину так это то, что и семантически верными оказываются несколько вариантов.
Извини, вернусь к твоему первому сообщению.
Проблема выбора алтернатив сем. описания слова решается однозначно при сборке предложения. Если имеет дело неоднозначность, то предложение неоднозначно и для человека. Так что в теории (и по большому счету на практике) эта проблема решена.
ц и т а т а
|
|
Сяо Лао
|
написано:11-04-2004 06:43:21
|
115
|
temp в теории (и по большому счету на практике) эта проблема решена.
Где ж она решена? На практике (человеческой) да, в основном решена, через привлечение вневербального контекста, хотя судя по тому, сколько между людьми возникает "непоняток", то и здесь нельзя говорить о стопроцентном решении. Что касаемо неоднозначностей "компьютерного понимания", т.е. однозначного выбора семантической интерпретации, то в самом лучшем случае комбинируется более-менее полный набор альтернатив, а выбор оставляется "на потом", на другой алгоритм или человека.
ц и т а т а
|
|
temp
|
написано:11-04-2004 11:05:13
|
116
|
Где ж она решена? На практике (человеческой) да, в основном решена, через привлечение вневербального контекста, хотя судя по тому, сколько между людьми возникает "непоняток", то и здесь нельзя говорить о стопроцентном решении. Что касаемо неоднозначностей "компьютерного понимания", т.е. однозначного выбора семантической интерпретации, то в самом лучшем случае комбинируется более-менее полный набор альтернатив, а выбор оставляется "на потом", на другой алгоритм или человека.
Решена она явно не в ПРОМТе :) -- их переводы можно как анекдоты читать. Кого интересует, могут почитать труды проф. Тузова В.А. И решена она не через привлечение вневербального контекста, а через семантический словарь, описываюший каждое слово как аргумент функции предложения. Если проблемы и возникают, то это из-за неполноты или неточности словаря, что поправимо.
ц и т а т а
|
|
sergejh
|
написано:13-04-2004 12:16:37
|
117
|
ЗДЕСЬ объявляется конкурс, связанный с интеллектуальными технологиями (в частности, из области ИИ). Есть возможность заработать бабки. :)
ц и т а т а
|
|
Игорёк
|
написано:04-05-2004 22:29:13
|
118
|
малюк
Я когда брался за комп. анализ ест. языка мне это казалось чистой магией, я представления не имел как это возможно, а через пол года был готов замечательный анализатор англ. языка по оригинальному алгоритму. Нужно взяться и начнут получаться невероятные вещи.
...
Поясняю. Когда я взялся за ИИ, чтение книг на тему казалось мне самым правильным, что можно сделать, читал я их много и старательно, месяца два. Но уродство всех построений которые приводились, их очевидная (скажем так) нееффективность и несостоятельность мне надоели и я взялся придумывать свой способ построить анализатор чел. языка (задча стояла именно так). Еще месяц потребовался чтобы поотбрасывать весь хлам который эти книги привнесли в мое понимание проблемы, а потом, выбросив свои предыдущие наработки, за 1,5-2 недели я написал анализатор круче всех тех что были мне известны и известны сейчас.
...
Среди интересных возможностей - понимание синтаксически неверных предложений (нигерский спик, речь иностранца) довольно неплохо работало, строит не одну структуру а несколько для дальнейшей обработки на уровне семантики. Понимание "недоговоренных" предложений. То есть, потенциально, он мог даже перебивать собеседника, для уяснения аспектов. Оригинальная модель структур после синт. разбора - связи разнородные и уже несут большой шмат семантики, то есть многие неверные смылы отваливаются уже из-за этого. В общем, насколько я представляю, он переводил предложения в компьютерно перевариваемый вид с минимальными потерями.
...
Что было недоделано. Был разбор не всех типов вопросительных предложений. Забиты правила лишь на самые употребимые собюзы и предлоги. Выдача версий не учитывала различия вероятности верности разных вариантов понимания. Наверное еще туча недоделок.
Работу над ним я бросил, поскольку руководитель откровенно оборзел и захотел, чтобы я летом продолжал работать над этим каждый день - результат, кафедра с ворохом кода работающим по непонятным алгоритмам и моя тройка по ИИ.
Когда я доберусь до ИИ снова, то буду делать уже иначе, новое понимание пришло, так сказать.
...
Что это за семантические структуры? Что с ними потом можно делать дальше?
Синтаксический разбор предложений, насколько я знаю, задача в общем решенная.
Вопрос - что дальше? Как должны быть организованы эти самые семантические
структуры, какие алгоритмы нужны для их обработки, чтобы получить реально
полезный результат (хотя бы реализовать ведение диалога, наподобие
того, как это делает псевдо-ИИ программа Alice).
Если программа показывает хорошие результаты по сравнению с другими,
то может быть имеет смысл выложить ее в свободный доступ?
Чтобы народ ознакомился и оценил.
ц и т а т а
|
|
Guest
|
написано:06-05-2004 13:51:00
|
119
|
Знатоки ИИ, подскажите.
Пусть есть база данных (БД), состоящая из ста миллионов однотипных записей. Одна из записей (неизвестно какая) помечена. Сколько операций чтения единичных записей БД нужно, чтобы найти помеченную запись?
ц и т а т а
|
|
sergejh
|
написано:06-05-2004 14:11:17
|
120
|
Guest
Ну если n=порядковый номер этой записи,то вроде как n-операций.
Но если бы искал человек... Он бы прокручивал страницы и искал глазами помеченную запись, а найдя ее, сразу бы щелкал по ней мышкой. :) За одну операцию тут можно считать один скролл экрана, а также щелчок мышью. В этом случае количество операций будет всяко меньше, чем бы искал компьютер по типичному перебору с 1-й по N-ю. Но у человека появляется еще один фактор: внимательность... Он может запись попросту пропустить и начать искать снова, по кругу. :)
ц и т а т а
|
|
|