[Recent Entries][Archive][Friends][User Info]
Below are the 20 most recent journal entries recorded in the "tinyprince" journal:| July 17th, 2017 | |
|---|---|
| 02:12 pm [Link] |
Успехи компьютерных наук Широко известна теорема Сильвестра-Галлаи утверждающая, что для любого конечного множества точек на плоскости, которые не лежат на одной на прямой можно найти такую прямую, которая будет проходит ровно через две точки из данного множества. Теорема знаменита тем, что несмотря на то, что её не могли доказать полвека, доказывается жутко элементарным образом, первое доказательство появилось в 1944-ом. Потом появились всякого рода её обобщения и вариации. Недавно выяснилось, что её можно применять для решения задачи Равенства нулю многочлена , т.е. для следующей алгоритмической задачи: дан многочлен от нескольких переменных (скажем, над целыми числами) в виде сумм и произведений всяких скобок, нужно выяснить, является ли он тождественным нулём. Раскрывать все скобки долго, а хочется полиномиального алгоритма. Существует вероятностный полиномиальный алгоритм - подставить в многочлен несколько случайных точек, если во всех них многочлен равен нулю, то он с большой вероятностью равен нулю тождественно - лемма Шварца-Зиппеля. Отметим, что вычислять значение многочлена в точке непосредственно эффективней чем сперва пытаться упрощать этот многочлен, а потом вычислять значение (а ёбанные училки в школах учат, что наоборот). Дико важным вопросом в теоретикал компьюта сцаенс является существование полиномиального детерминированного алгоритма для задачи Равенства нулю многочлена. В частных случаях это удаётся сделать, причём доказательство полиномиальности делается с применением обобщения теоремы Сильвестра-Галлаи. Чтобы похожий алгоритм годился для более широкого класса многочленов, хочется доказать аналог этой теоремы для более широкого класса объектов чем прямые. 
|
| October 29th, 2016 | |
| 03:57 pm [Link] |
Из книжки "Человек, который принял жену за шляпу" Когда в 1966 году в государственной больнице я впервые увидел близнецов — Джона и Майкла, они уже были знамениты. Их приглашали на радио и телевидение, о них писали в академических и популярных изданиях, и, кажется, они попали даже в научную фантастику, слегка приукрашенные, но в общем такие, как описывалось в прессе. К тому времени близнецам уже исполнилось двадцать шесть. С семи лет они содержались в различных лечебных учреждениях с диагнозами от психоза и аутизма до тяжелой умственной отсталости. В конце концов большинство наблюдавших за ними пришли к выводу, что Джон и Майкл — заурядные idiots savants, «ученые идиоты», чьи таланты ограничиваются редкой «документальной» памятью на мельчайшие зрительные детали, а также умением, пользуясь хитрым подсознательным алгоритмом, моментально вычислять, на какой день недели падает дата из далекого прошлого или будущего. ( ... ) |
| July 3rd, 2015 | |
| 10:17 am [Link] | http://www.youtube.com/watch?v=Dr3JF0NG Охуительное видео про мозг всяких дельфинов и касаток. Мозг, оказывается, нужен в основном, чтобы жить в сложной социальной среде - 11:20. Касатки делают волну и сгоняют сраных тюленей со льдины - 1:01:40. |
| September 1st, 2014 | |
| 02:13 pm [Link] | читаю даже не без удовольствия contrinitiator и рому михайлова. новороссия - чисто экзистенциальный проект, несущий в себе ничего. почему у россии самая большая территория? потому что её единственной национальной идеей является захват чужих земель. ну и где-то еще было написано, что сейчас это наконец-то происходит чисто по-русски, а не под прикрытием каких-то странных идеологий. Current Music: Mark Shreeve – Aurora |
| July 14th, 2014 | |
| 12:22 am [Link] | Он меня ещё просил доказать, что могут быть эти его функции, характеризующие сложность не как число, а как функцию длина программы, нужной, чтобы найти множество маленького размера, содержащее данное число. Я ему доказал, что это может быть любая ступенчатая функция с точностью до логарифма; потом это уже было замечание самого Колмогорова, что из этого вытекает, что вообще любая монотонная функция может быть сложностью с точностью до корня из n. Это его замечание, оно со сложностью не связано, это просто свойство монотонных функций. Но я тогда же доказал, что все последовательности, у которых эта функция значительно отличается от диагонали, имеют много информации о halting problem и поэтому не встерчаются. Значит это не годится как механизм объяснения почему в некоторых случаях статистика применима в реальности, а в некоторых нет: таких последовательностей в реальности не бывает. Я к этому потерял интерес а Колмогоров по-моему не понял этого аргумента. Иначе говоря, если Вы не можете написать програмку, которая генерирует тексты не отличающиеся от эээ текстов Сорокина, то это только следствие Вашей криворукости: такая (короткая) программа должна существовать (по мнению Левина). Впрочем, если все же предположить существование хороших вещей , то получится, что все они об одном и том же. Current Music: Alexander Rudin – Chaconne from Partita No.2 |
| May 30th, 2014 | |
| 12:58 am [Link] | Подумалось, что понятия "создания"(с.) и "разрушения" (р.) есть просто нечто идущее от инстинкта самосохранения, также как понятия Добра и Зла например. То есть все, что выгодно для человека с эволюционной точки зрения, считается с., а что невыгодно - р. Поэтому подсознание людишек пытается всеми силами облагородить понятие с.; это проявляется например в (скорее всего) неправильной интуиции о том, что "ломать" легче, чем "строить". Я к тому, что Второй Закон может быть просто психологической ловушкой. Current Music: Psychic TV – Higher and Higher |
| April 29th, 2014 | |
| 10:18 pm [Link] | и где теперь silencefactory? |
| April 8th, 2014 | |
| 11:48 pm [Link] | Возвращаясь к прошлому: http://lj.rossia.org/users/tinyprince/1 Итак, у нас была максимально нестохастическая строчка длины n с колмогоровской сложностью k. Оказалось, что по любым её k битам, находящимся в простых местах её можно восстановить. Кстати эти k бит оказались ни чем иным, как первыми битами знаменитого Омега. Так вот, оказалось, что такое кодирование существует для любых k бит: для любой строки А длины k и для любого n > k существует такая строчка B, что по любым простым k битам B можно восстановить A (ну и B если n = O(k)). Мое доказательство чисто алгоритмическое, а Шень придумал вероятностное (и очень прикольно понять связь). Из всего этого несложно следует, что существует строчка длины n, по любым k битам которой можно восстановить первые k бит Омеги, но которая является стохастической. Формула красоты утекла сквозь пальцы просто. |
| March 1st, 2014 | |
| 08:57 am [Link] | ТББ кстати охуительный и смешной фильм (особенно порадовало, как Буддах стал ссаться на Румату во время их диалога). Целевая аудитория либо уходила сразу (это те кто по умнее), либо мучилась до конца, чтоб потом написать как все "тяжело и беспросветно" (ояебу). |
| February 1st, 2014 | |
| 03:43 am [Link] | Жительница Нигерии выгнала кота из дома за гомосексуализм Южная рашка же. Пиздааааааааааааааааааааа |
| December 19th, 2013 | |
| 11:11 am [Link] |  http://www.risuemsud.ru/processes/29/wo Завтра в 11:00 Current Music: Эдуардус – Контракт |
| November 22nd, 2013 | |
| 01:14 am [Link] | http://www.youtube.com/watch?v=CIkUgmgt Лекция Шеня про вероятность, квантовую механику, второй закон, односторонние функции... (только сейчас нашел - удивительно) Ну и завтра, по ссылке от ![[info]](http://lj.rossia.org/img/userinfo.gif) oort, А. Х. будет вещать про подобные вещи (сам никак не успеваю к сожалению).
|
| November 19th, 2013 | |
| 10:37 pm [Link] |
Самоподобие сильно нестохастических строк Пусть X - (p,q) нестохастическая строка длины n, то есть если X \in A и K(A) < (q - \epsilon)n,то X не является типичным для A, то есть log(A) - K(X|A) > (p - \epsilon)n. Если p + q = 1, то существует (p,q) нестохастические строки. Я буду рассматривать q << 1 (то есть объект описать не очень сложно, но он ни на что не похож), хотя это абсолютно не важно. Запишем X = a_1a_2...a_n. Cтрока B - кусочек X - записывается в виде a_{i_1} ... a_{i_k}, где 0 < i_1 < ...< i_k < n + 1. Будем называть кусочек \epsilon-нормальным, если K({i_1,...,i_k}) < \epsilon * n. (например, просто подстрока X). k - размер кусочка Утверждение: если B - \epsilon-нормальный кусочек размера >qn, то K(X|B) < 3\epsilon*n. То есть весь объект можно практически восстановить по любому нормальному кусочку того же размера, что и колмогоровская сложность объекта. Поясню про "нормальность": можно извратиться и найти большой кусок человека, в котором не будет ДНК, по такому куску человека не восстановишь; нормальность требуется чтобы избежать подобных недоразумений. Current Music: Wolvserpent – A Breath In The Shade Of Time |
| November 17th, 2013 | |
| 11:47 pm [Link] | бля я идиот: правильное определение художественной ценности тут: http://youtu.be/lgHccF0kqh4?t=26m18 ценность является положительным числом меньшим единицы, причем для любого эпсилон больше нуля существует произведение искусства ценности > 1 - эпсилон Такие дела |
| November 16th, 2013 | |
| 09:39 pm [Link] | 1)Откуда пошла истерия по поводу чрезвычайно низкой энтропии у живых организмов? Это ж неверно, то есть по логике энтропия у взятых по отдельности белков и прочих углеводов должна быть меньше, чем если их сложным образом собрать вместе. У отдельно взятых азотов (и пр.) меньше, чем у белка, и т д. [Здесь я исхожу из математического определения энтропии (до какой степени можно сжать информацию линейным образом), которое хорошо согласуется с термодинамическим, у физиков общего определения энтропии ("меры Хаоса") нет]. Вообще, у всех сложноструктурированных объектов (с большой Колмогоровской сложностью) высокая энтропия, а все почему-то думают, что энтропия это смерть. 2) Еще есть мнение, что с помощью Колмогоровской сложности можно считать Художественную Ценность. Однако последовательности случайных бит никого не интересуют, также как и последовательность одних нулей, а с помощью их комбинаций можно получить любую Колмогоровской сложность (любое отношение сложности к размеру текста). Фишка в том, что в обоих случаях сами программы получаются примитивными, только в одном случае она маленькая, а в другом - большая. Лучше взять время работы минимальной программы и разделить на количество выходящих символов. Так получиться что-то вроде выстраданности худ. произведения. |
| 09:38 pm [Link] | 
|
| 09:38 pm [Link] | 
|
| November 13th, 2013 | |
| 10:10 pm [Link] | еще один сумасшедший пытается объяснить Второй Закон: http://www.jetpletters.ac.ru/ps/2015/ar Расстояние D(\psi_1|\psi_2) между состояниями \psi_1 и \psi_2 мы определим как минимальное время, которое необходимо для перехода из состояния \psi_1 к состоянию \psi_2. Необычайность такой меры заключается в том, что она ассиметрична. Например, если \psi_2 есть результат естественной эволюции \psi_1 то в типичном случае D(\psi_1|\psi_2) << D(\psi_2|\psi_1) (что и означает необратимость). Расстояние D(\phi_1|\phi_1^*) в типичном случае экспоненциально велико (иначе говоря, изготовление комплексно-сопряженного состояния, как мы уже обсуждали, почти всегда невозможно или сложно) Ничего не доказывается естественно. Но отсутствие какой-то магической величины, которая должна неприменно увеличиваться, привлекает. Скажем, классическая "односторонняя функция" в криптографии - возведение в степень - по сути является перестановкой, то есть никакого подобного инварианта здесь нет и не может быть в принципе. Жизнь тоже должна развиваться по таким односторонним функциям, то есть вернуться назад нельзя, но всякого гавна, типа Тепловой Смерти Вселенной, не происходит. |
| October 29th, 2013 | |
| 11:59 pm [Link] |
Законы физики нарушать нельзя! Универсальные законы физики, я так понимаю, нужно воспринимать не как аксиомы, а как что-то, что должно выполняться в рамках Уважающей Себя Теории. Еще круче, когда их там удается доказать (типа закон сохранения энергии - соотв. первый интеграл можно доказать в рамках классической теории механики) Если кто-то скажет вам, что выстраданная вами теория устройства Вселенной противоречит уравнениям Максвелла, - то можно ответить, что тем хуже для уравнений Максвелла. Если окажеться, что она не согласуется с результатами наблюдений, - ну что ж, и экспериментаторы могут ошибаться. Но если ваша теория окажеться в противоречии со Вторым Законом Термодинамики, то я не могу оставить вам никакой надежды, и вашей теории придеться признать свое поражение. (ссылка из книжки Пенроуза, спасибо polytheme)Так вот, удается ли где-нибудь доказать 2-ой закон? |
| October 20th, 2013 | |
| 12:26 pm [Link] | Вдогонку: аналогией энергии в comptuter science является таки колмогоровская сложность. Мы не можем сильно изменить энергию с помощью небольшого взаимодействия, аналогично под действием (вычислимой) функции колмогоровская сложность меняется лишь на константу. Эту связь в какой-то умной форме нашел (ясное дело) Манин: http://arxiv.org/abs/1302.6695 Вообще аналогия между физикой и вычислимостью скоро перестанет удивлять. Потому что машина Тьюринга - это же блять реально машина, а еще её можно смоделировать на игре "Жызнь" как учит нас один из десяти лучших математиков мира (что-то ржу) John Horton Conway. Возвращаясь к нашим баранам: именно живые организмы почему-то уменьшают энтропию (вроде бы). Это должно что-то значить. Current Music: Oneohtrix Point Never - R Plus Seven |