Category: история

Category was added automatically. Read all entries about "история".

wall

Верхний пост

Всем привет.

Я мало френжу, простите.
У меня есть привычка читать всю ленту и ввязываться в дискуссии, из-за этого приходится держать количество друзей (особенно, активно пишуших друзей) в разумных пределах.

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

100 лет

Всех с праздником.

А сказать я наверное хотел вот это https://fat-crocodile.livejournal.com/129860.html

Им 200 лет примерно понадобилось, а у нас пока всего сто лет прошло. А если считать от распада СССР, то итого меньше, всего 26. Будущее ещё десять раз все переоценит.
wall

Случайные перестановки

Есть правильный алгоритм для случайной перестановки элементов массива:
def permute_good(a):
    n = len(a)
    for i in range(n-1):            # в этом алгоритме последний элемент менять не с кем
        j = random.randint(i, n-1)  # обратите внимание на диапазон: [i, n-1]
        a[i], a[j] = a[j], a[i]

То есть, на каждом шаге меняем i-й элемент на один из оставшихся в хвосте массива начиная с самого i-го элемента.

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

И есть неправильный алгоритм:
def permute_bad(a):
    n = len(a)
    for i in range(n):
        j = random.randint(0, n-1)  # обратите внимание на диапазон: [0, n-1]
        a[i], a[j] = a[j], a[i]

То есть, на каждом шаге меняем i-й элемент на произвольный элемент массива.

Про него... Про него довольно быстро приходит в голову, что возможных перестановок n!, а возможных путей в рамках этого алгоритма nn. Пути все равновероятны, но одно на другое нацело не делится почти никогда, а значит перестановки не будут равновероятны, где-то получится не совсем ровно. Это то, что пришло в голову мне и это единственное, что я нашел в википедии. И на этом мысль останавливается.

Побился немного головой, внятных причин не придумал, решил поставить эксперимент. Можно взять какой-нибудь небольшой массивчик, провести все возможные пути и просто посчитать, сколько каких перестановок получится.

Collapse )

Итого: второй алгоритм неожиданно плох. Если кто-нибудь знает почему -- объясните мне, пожалуйста.

Ответ (идея voidex, я только переформулировал построже): посмотрим, каким образом во втором алгоритме последний элемент может оказаться на первом месте.

а) он может попасть туда с первой перестановкой и в дальнейшем там же и остаться. Вероятность этого 1/n * ((n-1)/n)n-1
б) он может всю дорогу простоять на последнем месте и попасть туда с последней перестановкой. Вероятность этого ((n-1)/n)n-1 * 1/n

и все, других вариантов нет. Почему нет, может быть он как-нибудь хитро обменяется? Нет, не может.

Collapse )

Значит вероятность того, что последний элемент оказался на первом месте равна 2/n * ((n-1)/n)n-1. Для n=8 это будет 0.098 (по таблице так и получилось), это меньше чем равномерная 1/8.
wall

Lycian Way

Ликийская тропа это 500 километровый трекинговый маршрут по побережью Средиземного моря в Турции, с небольшими заходами вглубь.

Вот тут это место на большой карте Турции


Выделенная область это Ликийский полуостров. А вот сама тропа немного подробнее (отмечена синим, там есть несколько развилок)


Она появилась в 1999-м году, с первым изданием книжки The Lycian Way. На всем пути тропа отмечена краской, красно-белыми маркерами на камнях, деревьях, столбах и т.п., периодически стоят указатели.

Нигде подробно не описано, как создавалась тропа. Но вроде как она сделана фактически одним человеком, Kate Clow, живущей в Турции пожилой англичанкой, автором книжки. Легенда (кроме которой ничего нет) говорит, что она ходила в походы по античным тропам, изучала их, видимо частично расчищала, объединила в одну тропу и разметила её маркерами (сейчас чистить тропу и обновлять раскраску приглашают волонтеров). И написала путеводитель.

Сейчас по тропе ежегодно проходят десятки тысяч людей (не всю целиком конечно, там можно начинать и заканчивать почти где угодно), сами по себе или с гидами, с неё кормится куча местных турков и турфирм. По каким-то рейтингам тропа входит в десятку лучших многдневных маршрутов. В 2010, 2011-м и 2012-м по ней проводился ультрамарафон, в 2015 снова планируют.

Мне кажется, интересная история.

Не без недостатков, конечно. Например, книжку покупать не советую, так как основное её содержание это "поверните налево, пройдите 200 метров, перешагните через поваленное дерево, потом прямо ещё 100 метров, дальше направо". В ней встречаются содержательные врезки о деревнях/поселках/городах, мимо которых проходит путь, но в целом сейчас это довольно бессмысленно. Наверное она имела смысл в 1999-м, если тогда тропа была хуже размечена, а GPS был дорогой экзотикой.

Но недостатки у всех есть, а вот такую штуку сделать -- это многого стоит.
wall

почему LZ77 лучше чем LZ78

Вот например пишут:

LZ77 и LZSS обладают следующими очевидными недостатками:

1. невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря;
2. длина подстроки, которую можно закодировать, ограничена размером буфера.

Если механически чрезмерно увеличивать размеры словаря и буфера, то это приведет к снижению эффективности кодирования, т.к. с ростом этих величин будут расти и длины кодов для смещения и длины, что сделает коды для коротких подстрок недопустимо большими. Кроме того, резко увеличится время работы алгоритма-кодера.

В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков.

Однако наблюдаемая реальность намекает нам, что что-то тут не чисто: алгоритмы на основе LZ78 гораздо менее распространены. Хотя в преимущества ещё можно смело добавить линейную скорость работы. Наверное частично повлияли проблемы с патентами на LZW, но дело всё же не в них.

Collapse )
wall

Алгоритмы LZ* и оптимизации

LZ это Lempel-Ziv, два израильских математика Abraham Lempel и Jacob Ziv, на высказанной ими идее основана примерно половина современных алгоритмов архивирования. В двух словах идея формулируется так: помни историю! То есть, если последовательность символов нам уже встречалась, то не будем повторяться, а сошлёмся на ту.

Несколько подробнее, но не опускаясь до уровня битов...
Статьи, на которые нет ссылок я брал с соответствующего раздела сайта comperssion.ru

Алгоритмы

LZ77
Оригинальная статья Ziv, Lempel "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. 23, no. 3, may 1977. Статья написана настоящими математиками! На высоком уровне абстракции, с большим количеством формул и доказательством каких-то оценок. Понять что-либо непросто. А доказательства я даже и не пытался читать.
Есть разные версии алгоритма, я буду следовать статье.


Collapse )

LZ78
Ziv, Lempel "Compression of Individual Sequences via Variable-Rate Coding", IEEE Transactions on Information Theory, vol. 24, no. 5, september 1978. Но эту статью совсем не надо читать. Алгоритм там действительно описан, но появляется он несколько неожиданно: в качестве конструктивного доказательства сформулированной теоремы о существовании некоторого алгоритма. Алгоритм простой, а уже даже формулировка теоремы сложная и вдаваться в её подробности не возникает ну ни какого желания.

Collapse )

LZW, 1984
"W" от Welch. Статья Terry A. Welch, "A Technique for High-Performance Data Compression", IEEE Computer, vol.17, N6, June 1984. Это статья написана инженером, формул тут нет совсем, зато есть картинки и псевдокод. Но сам алгоритм по прежнему абзаца на два, так что картинки не про него и вообще основное содержание статьи это рассуждения о том, как можно было бы реализовать прозрачную для пользователя архивацию данных и какие при этом возникают проблемы. Рассуждения разумные.

Collapse )

LZRW1, 1991
Ross N. Williams, "An Extremly Fast ZIV-Lempel Data Compression Algorithm", 1991. Наконец полноценная статья, посвященная именно алгоритму и сравнению скорости/качества работы его реализации с популярными архиваторами.
также см. http://www.ross.net/compression/lzrw1.html


Collapse )

Оптимизации

Допустим, реализуем LZ77. При архивации он выплёвывает тройки. Первый вопрос, который встаёт -- как их кодировать. И тут в голову почти сразу же приходят две мысли, первая и вторая.

Collapse )

Collapse )

Collapse )



Вроде бы это всё, что можно выжать из идеи LZ в чистом виде. Более интересные алгоритмы добавляют что-то ещё.
wall

Хаффман с ограниченной разрядностью

Все знаю про кодирование Хаффманом. Оказывается есть интересные вариации.

На всякий случай напомню о чём это. У нас есть некий алфавит и написанный им текст, и мы хотим записать этот текст в двоичном виде, причём очень простым способом:
  • сопоставить каждой букве алфавита двоичный код

  • записать текст, используя коды вместо букв

При этом
  • длины кодов различных букв могут отличаться

  • хочется, чтобы декодер, читая получившуюся бинарную строку от начала к концу мог однозначно определить границы кодов, не используя какие-то сложные правила. Требуем чтобы ни один код не был префиксом другого. Такой код называется префиксным.

    То есть набор кодов (0, 10, 110, 111) подходит, например строку 00101000100111110 можно однозначно разбить на 0-0-10-10-0-0-10-0-111-110. А (0, 10, 101, 111) не подходит: 1010 это 101-0 или 10-10?
    Это довольно слабое ограничение, например любой код фиксированной длины очевидно префиксный и т.п., отсекаются только довольно странные вещи

  • нужно чтобы бинарная строка была бы покороче

Ну и в общем понятно, что для того чтобы результат получился покороче, символам, которые встречаются почаще стоит дать коды покороче, а тем что пореже -- можно подлиннее. Это и есть основная мысль. Алгоритм построения оптимального (с точки зрения длины получающейся строки) кода, удовлетворяющего этим условиям, придумал David A. Huffman, статья опубликована в 1952-м.

Вот, кстати, интересно: учёный, дожил до 1999, а известен всем только как автор четырёхстраничной статьи написанной в аспирантуре, с алгоритмом, который можно объяснить школьнику. И даже в 1998, а потом в 1999 его ещё два раза наградили за неё, напоследок. Наверное ему было немного обидно от всего этого. Хотя вики и пишет, что у него были значительные достижения в других областях, видимо они были не настолько значительными, чтобы описывать в вики сами эти достижения. Просто хоть не становись знаменитым.

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

Классический алгоритм Хаффмана несложный и широко известный, код действительно оптимальный. Но коды редких символов могут получаться довольно длинными, иногда это неудобно. И оказывается, что попытка наложить ограничение на максимальную длину значительно всё усложняет.

Теперь какие-то чуть менее всем известные вещи.

Collapse )

И собственно к поставленной задаче. То что написано ниже это пересказ в свободной форме следующей статьи:

LAWRENCE L. LARMORE, DANIEL S. HIRSCHBERG
"A Fast Algorithm for Optimal Length-Limited Huffman Codes"
Journal of the Association for Computing Machinery, Vol. 37, No. 3, July 1990

Статья гуглится.

Collapse )
wall

(no subject)

Прочитал серию статей makkawity (Константин Асмолов) "Антиревизионизм"

Collapse )

Поскольку автор профессионально занимается Кореей, в изложении довольно часто встречаются примеры "не про нас", это интересно. А то всё Сталин да Гитлер, ну сколько можно.

Интересно понятие "государственного мифа", оно довольно естественное (и значит не совсем то, что вы, возможно, подумали), но я раньше его не встречал. Но тут скорее всего дело в том, что я раньше по этой теме ничего не читал.

Очень интересно предложение, высказанное в №15: добавить в школьную программу по истории чего-нибудь источниковедческое и таким образом не просто вдолбить школьникам факты и идеологию, но научить их отличать совсем явные глупости от может-быть-и-не-глупостей. Мысль мне понравилась, но на мой вопрос, может ли он что-то мне порекомендовать подобного плана, Константин предложил как раз этот цикл. В котором, на мой взгляд, ничего подобного нет (ну, кроме очевидностей).

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

Собственно, я бы не стал давать ссылку, если бы не встречающиеся иногда феерические примеры, которыми просто хочется поделиться. Какие всё-таки люди разнообразные бывают!

К примеру, доказывая преступные планы кровавого сталинского режима, Резун дает ссылку на номер «Правды» от 4 марта 1941 года на страницу 4, откуда приводится развернутая цитата о том, как надо поступать с союзниками, натравливая их друг на друга и не упуская своей выгоды.
Это действительно ссылка на ту самую страницу той самой газеты, на которой, однако, находится не правительственная статья, а рецензия Емельяна Ярославского на том первый книги "История дипломатии" под редакцией Потемкина, в тексте которой цитируется данное высказывание, принадлежащее герцогу Сфорца.


Это из №11.

Похожая логика сквозит в тексте, авторство которого одна из газет российских корейцев приписала М. Н. Паку . Речь шла о секретном советско-японском соглашении, по которому в обмен на нейтралитет во Второй мировой войне Советский Союз должен был репрессировать корейское землячество и осуществить геноцид корейского народа, частью которого стала депортация советских корейцев с Дальнего Востока в Казахстан и Среднюю Азию. По мнению автора материала, то, что ни в российских, ни в японских документах вообще нет никаких ссылок на тайный договор между этими странами, доказывает то, что такое соглашение было, но оно было особо секретным.

Тоже №11

Так, по мнению одного из сторонников существования жидомасонского заговора, то, что в 1240 г. Русь одновременно подверглась нападению и с Запада, и с Востока, неопровержимо свидетельствует о наличии между монголами и тевтонцами скоординированного плана действий, направленного на раздел страны. А поскольку евреи проживали и на тевтонской, и на монгольской территориях, то совершенно ясно, кто именно обеспечивал связь между этими двумя силами и координировал их действия.

Это из №12

Другой вариант этой ошибки или преднамеренной манипуляции – история с публикацией в определенном сегменте Интернета антирусской и экспансионистской статьи с некоего китайского сайта с подтекстом «Вот что китайцы думают о нашей стране и вот какие планы они строят». Так как ссылка на сайт имелась, кто-то из владеющих китайским языком не поленился на него заглянуть и выяснил, что означенный сайт является фактически домашней страницей двадцатидвухлетнего молодого человека.

Тоже №12

Жару добавляют читатели.

Другой пример - 110000 изнасилованных немок в Берлине в конце Великой отечественной. Оценка делалась так. Были взяты данные одной больницы и посчитаны все родившиеся в конце 45-46 г.г дети, чей отец был записан как "русский". Затем полученный процент "русских детей" экстраполировали на общее число детей, рожденных в Берлине. Получилась тысяча с небольшим. Затем были выбраны весьма произвольные модификаторы относительно того, какой % изнасилованных забеременел и какой % забеременевших не сделал аборт (20%; 10%). Таким образом, изначальное число в тысячу "русских детей" было умножено сразу на 50. Затем, предположив, что насиловали и женщин не детородного возраста это число умножили еще на два. Т.е., на основании того факта, что отцами 34 детей, которых лечили в одной больнице, были "русские" была сделана оценка, что 110000 немок были изнасилованы.

Это комментарий labas к №9.

Или, менее смешное, но тоже показательное:

Да нет, я имел ввиду конкретно, например, "Самолётостроение в СССР" (из разряда ВПК-истории). Там (т.2, сс.36-38) проводится сравнение характеристик истребителей СССР и Германии на начало войны, при этом за СССР даются самолёты "новых типов" (ЛаГГ-3, Як-1, МиГ-3), а за немцев берётся Ме-109Е-3. Наши выходят самыми лучшими. В то время как порядка половины немецких одномоторных истребителей на Востоке перед вторжением относились уже к следующему поколению - Me-109F, с заметно лучшими характеристиками.

Это комментарий fat_yankey там же.
wall

Сортировка Шелла

Узнал новое для себя. Известно, что сортировка Шелла (это когда сортируют сначала с большим шагом, потом поменьше, и так до шага 1) самая быстрая из простых. Оказывается, её эффективность критично зависит от последовательности длинн шагов. Настолько критично, что ассимптотика меняется с квадратичной до N3/2 уже при очень простой последовательности, а при сложных там вообще чёрти что (нет, я не знаю доказательств, увы). В вики описан десяток вариантов. Существование оптимальной последовательности, насколько я понимаю, открытый вопрос.

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

Сравнения:
    10    100      1000      10 000        100 000         1 000 000         2 000 000
2i 2989825 945759 75320 397 455 ----
2i-1 4188219 528315 1665 868 129114 179 223--
3xi+1 2373513 797249 1153 851 73864 448 695--
Седжвик 2174813 364195 8772 622 31932 742 122--
-----
quick sort 4391215 495212 8682 760 005 34 204 660 70 082 896
merge sort 265678 722123 7541 566 757 18 716 209 39 431 932


Обмены/копирования:
    10    100      1000      10 000        100 000         1 000 000         2 000 000
2i 1653320 131671 24519 304 210 ----
2i-1 2651113 702226 6704 775 075101 211 073--
3xi+1 144378 809178 1502 926 03353 053 975--
Седжвик 124567740107 5471 407 81217 386 677--
-----
quick sort 152172 96036 651440 820 5 163 019 10 863 532
merge sort 4080010 000140 0001 800 000 20 000 000 44 000 000

Вариант "Седжвик" это слияние двух последовательностей {9 * 4i - 9 * 2i + 1} и {4i - 3 * 2i + 1}.

Более того, поскольку это всё равно только для относительно коротких массивов подходит, народ частично плюёт на ассимптотику и борется тупо за результат.

"эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): {1, 4, 10, 23, 57, 132, 301, 701, 1750} является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов" это из нашей вики

И действительно, на отрезке до 8000 бъёт остальные четыре и по количеству сравнений и по количеству пересылок. Сильно дальше не смотрел, там очевидные проблемы с тем, что последовательность слишком короткая, а для больших массивов нужны большие шаги -- ну так дальше и не обещали. От квиксорта на тысячах отстаёт, но не сильно и зато насколько проще код!
wall

Model Thinking -- 7

Интересная первая часть, не думал раньше о таких ситуациях. Пока искал ссылки, нашёл An Essay on The Existence and Causes of Path Dependence, 37 страниц за авторством того самого профессора, ещё не прочитал, но собираюсь. А больше хороших ссылок что-то не видно.

Седьмая неделя -- 1 -- Path Dependence

Проще всего на примере.

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

(а) Модель Пойа (Polya process)
Модель Пойа: урна, красные и синие шарики. Достаёшь шарик, записываешь цвет, кладёшь обратно два шарика: этот и ещё один того же цвета. Вероятность получить тот или другой цвет меняется, так как меняется соотношение шариков в урне.

Что тут интересно:
  • результирующая вероятность не зависит от последовательности выборов, только от их значений. Потому что независимо от того, в какой последовательности выбирать, каждый шарик приносит в урну ровно один такой же дополнительный. Он назвал это "phat dependency" (переставил буквы в слове path).

  • это значит, что исходов у нас не столько же сколько путей, а столько, сколько распределений шариков. Это гораздо меньше. Начиная с (1К, 1С) распределение (3К, 3С) можно получить как ККСС или как КСКС или как СККС и т.п. Разные пути но один результат.

  • доказывается (несложно), что все пути, ведущие к одному результату равновероятны.

  • доказывается (посложнее), что, если начинать с (1К, 1С), то все результаты равновероятны

То есть, когда мы на старте имеем 50/50, мы можем получить что угодно, любое распределение, и у нас нет никаких идей о том, что получится.

Где это может реализоваться: покупатели выбирают товары смотрят, что купили их друзья и берут такие же. И чем более распространена модель, там больше вероятность, что она будет распространяться ещё шире.

Collapse )

Седьмая неделя -- 2 -- Networks

Математик сказал бы "графы", но это не так модно звучит, поэтому сети. Но в общем, рассказ про графы, все в курсе что это такое, поэтому я буду кратко.

Разговор начинается с того, что можно измерить. Помимо традиционных степени вершины (и средней степени по графу), расстоянию между двумя вершинами (и среднему по всем парам тоже) и количеству компонент связности, упомянул характеристику, которой я раньше не слышал: коэффициент кластеризации (clustering coefficient).

Вводится понятие "тройка вершин", они бывают открытые и закрытые. Закрытая тройка это три вершины, которые соединены рёбрами каждая с каждой, выглядит это как треугольник. Открытой тройке на хватает до треугольника одной стороны.

C = количество_закрытых_троек/общее_количество_троек

Collapse )

Upd: Это последняя часть конспекта, лекции 8-9-10 я не стал записывать. Интересного там особо не было, на мой взгляд.