| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Господа, это видео о лучшем алгоритмисте в мире.
Все что он говорит переворачивает мое представление о том, что я знал до этого.
Интересно, какой у него цвет на CF?
Думаю за предложенный им алгоритм ему точно нужно дать премию Тьюринга
P.S. Если кто скажет как вставлять видео прямо в страницу, скажу спасибо.
еще статья с xakep.ru о самом антивирусе.
Не перевелись еще таланты на Руси.
Спасибо за поднятое настроение на весь день.
Особенно понравился феерический алгоритм сжатия данных в миллионы раз, который, если я все правильно понимаю, сам автор подробно описал в таком известном месте собрания признанных и не очень гениев, как vk.com. Цитирую (думаю, он не против):
Алгоритм архивации таков: любой файл представляет собой HEX-последовательность символов, переводим этот HEX в DEC, получаем неебически-большое число, дописываем перед этим число 0, — получаем число в диапазоне от 0 до 1 с огромным числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Беда в подборе чисел, которое может идти и 2 часа, а может идти и 2 недели. Есть опытные образцы и работающая программа, и всё это работает.
Ну а что, работает ведь. Вот дадут нам информацию вида 10000000000... (миллиард нулей), он возьмет, заменит ее на 1/2 (и точность нужную еще где-то запишет) — и вот вам мировой рекорд по сжатию данных. И можно снова на TV.
Одно мне, скромному хомячку, никак не понять — зачем в DEC переводить:)
тогда уж 1/10 если в твоем примере.
Ах, да. Я исполнил менее странный алгоритм. Просто не задумался над тем, насколько бредово звучит идея автора, и до твоего замечания даже не заметил, что у меня не то, что в оригинале.
Я почему-то взял двоичное 1000000000, приписал в начале 0 (0.100000), приблизил, а уже потом перевел в DEC.
В dec наверное либо чтоб числа длиннее были (чтоб слишком сильно не сжалось, гы), либо он в двоичной считать не умеет. Правда если даже отвлечься от анализа длины получившихся чисел, стоит таки упомянуть что эта гениальная но абстрактная идея украдена из книжки Мартина Гарднера (глава "Трансцендентное число Пи"), а он в свою очередь ссылается на Стивена Барра.
Мне нравится, как Гарднер делает суперфлешку — берем метровый стержень, делаем на нем отметку на расстоянии k от начала... При этом число k как раз хранит в себе нужную нам информацию. Потом главное точно измерить это k — и вот она, феерическая суперфлешка будущего.
По поводу анализа длины получившихся чисел — грубая оценка показывает, что у нас вместо одного числа длины О(N) получается два числа длины О(M), где M=N/2. Т.е. мы, понятное дело, имеем ненулевую вероятность того, что информация сожмется в K раз, для любого K (при достаточном количестве потенциальных пакетов для сжимания), но голое матожидание коэффициента сжатия у нас вроде бы не впечатляющее.
Ну... Одно из чисел можно взять за 1. А в целом это далёкий предок арифметического сжатия, как в архиваторе HA по-моему :)
UPD: По поводу "одного из чисел" я видимо мысль неправильно понял, сорри.