?

Log in

жизнь - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

жизнь [апр. 30, 2007|09:24 pm]
Anatoly Vorobey

Был сегодня в Станфорде на лекции В.И.Арнольда. Арнольд был очень живой и веселый, рассказывал много интересного. В какой-то момент я осознал, что прямо передо мной сидит и слушает Арнольда Дональд Кнут :)

Арнольд рассказывал об определенном подходе к измерению сложности конечных строк (не сложность по Колмогорову). Предположим, у нас есть строка нулей и единиц длиной n. Мы можем представить эту строку в виде функции f из Z_n в {0,1}, где f(i), 0≤i<n, определяет, стоит на i-том месте в строке 0 или 1. Другая возможность визуализации такой строки - она обозначает определенную вершину n-мерного единичного куба.

Вычислим строку разностей соседних битов данной строки, т.е. бит i в новой строке будет разницей битов i+1 и i в старой строке, без переносов между битами и заворачивая n-ный бит обратно в 0. Если, скажем, эта новая строка будет одни нули, это означает, что исходная строка была линейной функцией. Если нет, то вычислим следующую строку, если теперь будут одни нули, то исходная строка была квадратичным многочленом, итд. Вычисление строки разностей является применением определенного оператора A над функциями из Z_n в {0,1}. Последовательное применение A в конце концов приводит к циклу. Выпишем все строки длиной n, и сделаем из них направленный граф, где стрелка из одной строки в другую означает применение A. Как будет выглядеть этот граф?

Это будет лес из нескольких разъединенных между собой графов. Каждый из этих отдельных графов будет состоять из ровно одного цикла, к вершинам которого присоединяются хвосты-деревья. Один из отдельных графов, т.е. один из connected components леса, будет графом многочленов: его цикл состоит из замыкающейся на себя строки 00....0, а дерево, присоединяющееся к этому нулю, содержит все функции-многочлены начиная с линейных, потом квадратичные итд. Другие connected components (если они есть) выглядят по-другому: их циклы длиннее, и к ним присоединяется больше одного дерева. Оказывается, что для данного графа все деревья, которые приводят к вершинам его цикла, изоморфны между собой. Эти деревья все одинаковы по структуре, их можно классифицировать одним параметром глубины. Циклы можно классифицировать одним параметром их размера. Полностью весь лес можно записать в таком виде: 9 O(3)xT(4) + 5 O(2)xT(2) + O(1)*T(15), например, означает 9 изоморфных копий графа, состоящего из цикла из трех вершин, к каждой из которых присодиняется дерево глубины 4, плюс 5 копий графа итд. (цифры неточны, я их выбрал наугад). Выпишем такую запись леса для многих значений n и будет искать и доказывать закономерности между этими коэффициентами. Далее следовало несколько примеров таких закономерностей.

Если мы посмотрим на случайную строку из 0 и 1, то она почти наверняка окажется в графе с самым длинным циклом из всех графов данного леса, притом в дереве этого графа она будет где-то высоко (т.е. далеко от самого цикла). В этом смысле почти все строки "сложные" (к ним нужно много раз применять A, чтобы дойти до цикла, и сам цикл длинный). Поскольку по Колмогорову тоже почти все строки "сложные", выходит, что это определение сложности хорошо коррелирует с определением сложности по Колмогорову, но не по внутренним причинам, а из статистических соображений.

После лекции еще немного (вместе с еще двумя коллегами из Гугла, с которыми туда приехал) поговорили с Кнутом, и много - с Арнольдом, хотя в основном это заключалось в том, что говорил он :), и рассказывал очень много интересного. Я попытался пригласить его прочитать лекцию к нам в Гугль, но он решительно отказался. По-моему, он не очень любит Интернет, поисковые сайты и особенно Википедию.

СсылкаОтветить

Comments:
From: vantive_98
2007-05-01 04:37 am

лекции В.И.Арнольда

(Ответить) (Thread)
[User Picture]From: avva
2007-05-01 04:42 am

Re: лекции В.И.Арнольда

Спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: relf
2007-05-01 04:50 am
вот тут обсуждали определение сложности по Арнольду:
http://lib.mexmat.ru/forum/viewtopic.php?t=2845
(Ответить) (Thread)
From: qaraabayna
2007-05-01 02:06 pm
спасибо. Если я не один такой тупой, то следующее будет полезно:

"заворачивая n-ный бит обратно в 0" = "При этом для определения последнего элемента принимается f(n)=f(0)"
(Ответить) (Parent) (Thread)
[User Picture]From: averros
2007-05-01 05:12 am
Гм. Результат работы линейного клеточного автомата (2цвета, 3->1 правила) с правилом #30 и одной белой клеткой получается произвольно сложным по этому определеню (зависит от количества итераций, необходимых для распространиения начальной пертурбации вправо и влево). см. Wolfram, The New Kind of Science.

По-моему, единственное разумное определение сложности - Колмогоровское :)
(Ответить) (Thread)
[User Picture]From: starshoj
2007-05-01 05:21 am
Как можно учиться таким неитересным вещам, кофда можно научиться, где делают хороший кофе?
(Ответить) (Thread)
[User Picture]From: avva
2007-05-01 05:31 am
Я с удовольствием научусь и этому тоже, как только будет хоть несколько часов выбраться самому в Пало Альто :) надеюсь, на этой неделе.
(Ответить) (Parent) (Thread)
[User Picture]From: starshoj
2007-05-01 05:36 am
Ждёмс
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2007-05-01 06:00 am
направляясь в ту сторону, где, судя по голосам, стояли существа, подобные ему.
(Ответить) (Thread)
[User Picture]From: nchaly
2007-05-01 06:31 am
Несколько лет назад нашел на http://ega-math.narod.ru:

"Когда в сентябре я спрашиваю второкурсников: "Знаете ли вы Арнольда?", то, как правило, нарываюсь на встречный вопрос: "Шварценеггера?". Но затем, когда в течение семестра его имя упоминается неоднократно, студенты начинают осознавать, что звёзды бывают не только в Голливуде. Сегодня я выкладываю у себя некоторые очерки из книги В. И. Арнольда "Истории давние и недавние". Некоторые — это потому что книга свежая, стоит недорого, купить можно запросто (линк издательства внутри). Я, конечно, понимаю, что Арнольд в моей рекламе не нуждается, но вдруг кто-то, интересуясь математикой, всё же пропустил выход этого очаровательного сборника миниатюр."

Сам сборник: http://ega-math.narod.ru/Arnold3.htm, написано живо и с юмором. Как оказалось, и сам Арнольд такй же.
(Ответить) (Thread)
[User Picture]From: relf
2007-05-01 10:18 pm
Там сборник не полностью. Полностью вот, например: http://techlibrary.ru/books.htm
Там же много других книжек Арнольда.
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2007-05-02 04:38 am
Ух ты, какой классный сайт!
(Ответить) (Parent) (Thread)
From: (Anonymous)
2007-05-02 06:23 am
спасибо
(Ответить) (Parent) (Thread)
[User Picture]From: nchaly
2007-05-02 06:23 am
Всмысле, спасибо :)
(Ответить) (Parent) (Thread)
[User Picture]From: kinad
2007-05-01 06:53 am
Ну, Арнольд и в Израиле бывал несколько раз, на моей памяти, в 95 году в ТА, наверное и в других местах тоже. Правда тогда он рассказывал точно не о деревьях и алгортимах. Сейчас уже не помню абсолютно.
(Ответить) (Thread)
[User Picture]From: e2pii1
2007-05-01 07:49 am
Помню на Воронежской Зимней Математической Школе в 198x Арнольд бегал на лыжах в одних трусах. Но зато эти трусы у него были очень хорошо утеплены!

Шутка из стенгазеты той конференции:
"Лекция В.И.Арнольда "ядерные операторы в пограничном слое" вызвала интерес особого отдела. С автора взята подписка о невыезде".
(Ответить) (Thread)
[User Picture]From: pussbigeyes
2007-05-01 07:59 pm
Я стал там бывать с начала 90-х, Арнольд уже не приезжал, но легенда жила. Замечательные были школы. Турбаза "Березка", да? И лыжи, и ночные застолья, и лекции Хелемского о британских королях... После перерыва был еще раз в 98-м, но все уже сильно изменилось. Дух выветрился.
(Ответить) (Parent) (Thread)
[User Picture]From: e2pii1
2007-05-02 12:31 pm
И лыжи, и ночные застолья, и лекции Хелемского - Дa!
Я бывал там в 198x, c 1985
(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2007-05-01 07:58 am
В этом смысле почти все строки "сложные" (к ним нужно много раз применять A, чтобы дойти до цикла, и сам цикл длинный). Поскольку по Колмогорову тоже почти все строки "сложные", выходит, что это определение сложности хорошо коррелирует с определением сложности по Колмогорову, но не по внутренним причинам, а из статистических соображений.

это смелый вывод ;)

хотя, может, и правда коррелирует
(Ответить) (Thread)
[User Picture]From: flaass
2007-05-01 08:47 am
Ну, если и там, и там сложные "почти все", то и пересечение будет "почти все".
А можно определить, что строка сложная, если в ней примерно поровну нулей и единиц. Тоже будет коррелировать :)
(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2007-05-01 09:25 am
почти все, но это не значит что коррелировано. У почти всех людей две ноги и у почти всех людей меньше 10 букв в имени. Однако корреляция между одноногостью и длинным именем может быть какой угодно ;)
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2007-05-01 09:35 am
Кстати, таки не коррелирует. Там в обсуждении на форуме говорят, что самая сожная "по Арнольду" строчка нечетной длины - это чередующиеся нули и единицы.
(Ответить) (Parent) (Thread)
[User Picture]From: relf
2007-05-01 03:19 pm
Ага. Вот еще полезная статья по теме:
http://www.csam.montclair.edu/~thomasd/john.pdf
(Ответить) (Parent) (Thread)
[User Picture]From: jewgeniusz
2007-05-01 08:47 am
Ага, Арнольд с Кнутом давние приятели.

В.И. про как-то это рассказывал так: "Я спросил [о чём-то] у моего друга Дональда... Вы знаете Дональда? Он написал книжку "Железобетонная математика"..."
(Ответить) (Thread)
[User Picture]From: ivanvr
2007-05-01 02:01 pm
>"Я спросил [о чём-то] у моего друга Дональда... Вы знаете Дональда? Он написал книжку "Железобетонная математика"..."

Если эта цитата из русского перевода, то перевод не из лучших - книжка переведена как "КОНКРЕТНАЯ МАТЕМАТИКА" (МОСКВА, МИР 1998 ISBN 5-03-001793-3)

В оригинале названа как "concrete" (бетон), потому как это комбинация "continues" and "discrete"...
(Ответить) (Parent) (Thread)
[User Picture]From: jewgeniusz
2007-05-01 03:30 pm
Спасибо, я в курсе.
(Ответить) (Parent) (Thread)
[User Picture]From: ivanvr
2007-05-01 05:10 pm
не за что.

просто книжка на столе как раз лежала - решил выпендриться :-)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-05-01 03:40 pm
Это шутка (Арнольда).
А в английском языке есть слово concrete в значении "конкретный".
(Ответить) (Parent) (Thread)
[User Picture]From: ivanvr
2007-05-01 05:11 pm
да, согласен.
(Ответить) (Parent) (Thread)
[User Picture]From: ivanvr
2007-05-01 02:06 pm
А если он это сказал так по русски - то то что, я написал прозьба проигнорировать ;-)
(Ответить) (Parent) (Thread)
[User Picture]From: jewgeniusz
2007-05-01 03:31 pm
Да, это было сказано по-русски.
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2007-05-01 10:41 pm
привычная русская транскрипция -- это Стенфорд, почему-то пишут даже, скорее, Стэнфорд. Станфорд - там так его называют, да, но писать по-русски так неправильно.

Почему эта арнольдовская сложность в самом деле сложность, совершенно неясно. Кроме того, что оператор дифференцирования "хорош", аргументов нет. Если последовательность чуть изменить, то длина цепочки может резко измениться.

Владимир Игоревич не то что не очень любит интернет, а очень не любит.

Привет.
(Ответить) (Thread)
[User Picture]From: malaya_zemlya
2007-05-02 08:08 pm
Correct me if I am wrong, но вся разница между Колмогоровской сложностью и Арнольдовской состоит в том, что у Арнольда рассматривается ограниченное подмножество машин, генерирющих строки.
Колмогоров:
К(x)=min_i:phi_i(0)==y
где phi_0, phi_1.. - список машин Тьюринга

Арнольд:
А(x)=min_i:psi_i(0)==y
где psi_0, psi_1... - список машин, генерируюзий строчки по Арнольдовскому методу (LFSR, более-менее)

Можно и другие списки было бы рассматривать. (Машины, работающие в полиномиальном времени, примитивно рекурсивные функции итп). Тоже сложность статистически коррелировать будет.

При этом мы обычно будем терять универсальность (т.е. сложности, определяемые по различным спискам машин Тьюринга, различаются не более, чем на константу), но приобретем вычислимость сложности. Хорошо для практитки, но не совсем ясно, хорошо ли для теории.
(Ответить) (Thread)
[User Picture]From: avva
2007-05-02 08:32 pm
Ага, примерно так.
(Ответить) (Parent) (Thread)
[User Picture]From: spartach
2007-05-04 02:42 pm
"connected components"="связные компоненты". Вполне устоявшийся термин.
(Ответить) (Thread)