![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaБыл сегодня в Станфорде на лекции В.И.Арнольда. Арнольд был очень живой и веселый, рассказывал много интересного. В какой-то момент я осознал, что прямо передо мной сидит и слушает Арнольда Дональд Кнут :)
Арнольд рассказывал об определенном подходе к измерению сложности конечных строк (не сложность по Колмогорову). Предположим, у нас есть строка нулей и единиц длиной 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, чтобы дойти до цикла, и сам цикл длинный). Поскольку по Колмогорову тоже почти все строки "сложные", выходит, что это определение сложности хорошо коррелирует с определением сложности по Колмогорову, но не по внутренним причинам, а из статистических соображений.
После лекции еще немного (вместе с еще двумя коллегами из Гугла, с которыми туда приехал) поговорили с Кнутом, и много - с Арнольдом, хотя в основном это заключалось в том, что говорил он :), и рассказывал очень много интересного. Я попытался пригласить его прочитать лекцию к нам в Гугль, но он решительно отказался. По-моему, он не очень любит Интернет, поисковые сайты и особенно Википедию.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
лекции В.И.Арнольда
Date: 2007-05-01 04:37 am (UTC)Re: лекции В.И.Арнольда
Date: 2007-05-01 04:42 am (UTC)no subject
Date: 2007-05-01 04:50 am (UTC)http://lib.mexmat.ru/forum/viewtopic.php?t=2845
no subject
Date: 2007-05-01 02:06 pm (UTC)"заворачивая n-ный бит обратно в 0" = "При этом для определения последнего элемента принимается f(n)=f(0)"
no subject
Date: 2007-05-01 05:12 am (UTC)По-моему, единственное разумное определение сложности - Колмогоровское :)
no subject
Date: 2007-05-01 05:21 am (UTC)no subject
Date: 2007-05-01 05:31 am (UTC)no subject
Date: 2007-05-01 05:36 am (UTC)no subject
Date: 2007-05-01 06:00 am (UTC)no subject
Date: 2007-05-01 06:31 am (UTC)"Когда в сентябре я спрашиваю второкурсников: "Знаете ли вы Арнольда?", то, как правило, нарываюсь на встречный вопрос: "Шварценеггера?". Но затем, когда в течение семестра его имя упоминается неоднократно, студенты начинают осознавать, что звёзды бывают не только в Голливуде. Сегодня я выкладываю у себя некоторые очерки из книги В. И. Арнольда "Истории давние и недавние". Некоторые — это потому что книга свежая, стоит недорого, купить можно запросто (линк издательства внутри). Я, конечно, понимаю, что Арнольд в моей рекламе не нуждается, но вдруг кто-то, интересуясь математикой, всё же пропустил выход этого очаровательного сборника миниатюр."
Сам сборник: http://ega-math.narod.ru/Arnold3.htm, написано живо и с юмором. Как оказалось, и сам Арнольд такй же.
no subject
Date: 2007-05-01 10:18 pm (UTC)Там же много других книжек Арнольда.
no subject
Date: 2007-05-02 04:38 am (UTC)no subject
Date: 2007-05-02 06:23 am (UTC)no subject
Date: 2007-05-02 06:23 am (UTC)no subject
Date: 2007-05-01 06:53 am (UTC)no subject
Date: 2007-05-01 07:49 am (UTC)Шутка из стенгазеты той конференции:
"Лекция В.И.Арнольда "ядерные операторы в пограничном слое" вызвала интерес особого отдела. С автора взята подписка о невыезде".
no subject
Date: 2007-05-01 07:59 pm (UTC)no subject
Date: 2007-05-02 12:31 pm (UTC)Я бывал там в 198x, c 1985
no subject
Date: 2007-05-01 07:58 am (UTC)это смелый вывод ;)
хотя, может, и правда коррелирует
no subject
Date: 2007-05-01 08:47 am (UTC)А можно определить, что строка сложная, если в ней примерно поровну нулей и единиц. Тоже будет коррелировать :)
no subject
Date: 2007-05-01 09:25 am (UTC)no subject
Date: 2007-05-01 09:35 am (UTC)no subject
Date: 2007-05-01 03:19 pm (UTC)http://www.csam.montclair.edu/~thomasd/john.pdf
no subject
Date: 2007-05-01 08:47 am (UTC)В.И. про как-то это рассказывал так: "Я спросил [о чём-то] у моего друга Дональда... Вы знаете Дональда? Он написал книжку "Железобетонная математика"..."
no subject
Date: 2007-05-01 02:01 pm (UTC)Если эта цитата из русского перевода, то перевод не из лучших - книжка переведена как "КОНКРЕТНАЯ МАТЕМАТИКА" (МОСКВА, МИР 1998 ISBN 5-03-001793-3)
В оригинале названа как "concrete" (бетон), потому как это комбинация "continues" and "discrete"...
no subject
Date: 2007-05-01 03:30 pm (UTC)no subject
Date: 2007-05-01 05:10 pm (UTC)просто книжка на столе как раз лежала - решил выпендриться :-)
no subject
Date: 2007-05-01 03:40 pm (UTC)А в английском языке есть слово concrete в значении "конкретный".
no subject
Date: 2007-05-01 05:11 pm (UTC)no subject
Date: 2007-05-01 02:06 pm (UTC)no subject
Date: 2007-05-01 03:31 pm (UTC)no subject
Date: 2007-05-01 10:41 pm (UTC)Почему эта арнольдовская сложность в самом деле сложность, совершенно неясно. Кроме того, что оператор дифференцирования "хорош", аргументов нет. Если последовательность чуть изменить, то длина цепочки может резко измениться.
Владимир Игоревич не то что не очень любит интернет, а очень не любит.
Привет.
no subject
Date: 2007-05-02 08:08 pm (UTC)Колмогоров:
К(x)=min_i:phi_i(0)==y
где phi_0, phi_1.. - список машин Тьюринга
Арнольд:
А(x)=min_i:psi_i(0)==y
где psi_0, psi_1... - список машин, генерируюзий строчки по Арнольдовскому методу (LFSR, более-менее)
Можно и другие списки было бы рассматривать. (Машины, работающие в полиномиальном времени, примитивно рекурсивные функции итп). Тоже сложность статистически коррелировать будет.
При этом мы обычно будем терять универсальность (т.е. сложности, определяемые по различным спискам машин Тьюринга, различаются не более, чем на константу), но приобретем вычислимость сложности. Хорошо для практитки, но не совсем ясно, хорошо ли для теории.
no subject
Date: 2007-05-02 08:32 pm (UTC)no subject
Date: 2007-05-04 02:42 pm (UTC)no subject
Date: 2007-05-09 12:47 am (UTC)http://evgen-v.livejournal.com/105040.html
http://www.livejournal.com/allpics.bml?user=evgen_v
http://evgen-v.livejournal.com/profile