|
|
|
December 14th, 2009
12:32 pm - Дерандомизация
На последнем туре была такая задача: вывести n целочисленных точек с координатами от 0 до 2n таких, что никакие три не лежат на одной прямой. Авторы и участники генерировали ответ как-то безумно переборно-рандомизированно. ![[info]](http://l-stat.livejournal.com/img/userinfo.gif) ilyakor придумал совершенно гениальную, простую и явную конструкцию. Найдем простое p от n до 2n. В ответ выдадим такие точки: (i, i^2 mod p), где i пробегает значения от 0 до n-1. Этакая красивая дерандомизация.
|
December 12th, 2009
10:49 pm - Время, вперед!
Эх, а год назад я не верил, что счастье бывает. Счастье, когда появляется смысл и ласковые руки.
А уж два года назад я ни во что не верил.
|
December 10th, 2009
10:25 pm - илсым
Пересмотрели тут "Gran Torino". Очень сильная штука. Еще спасибо Игнату за то, что познакомил с "Dream Theater". "Pull Me Under" -- вещь!
А еще какое-то гнетущее настроение по поводу предстоящего непойми-какого Нового Года, сессии и всего такого.
P.S. Есть фильмы, которые надо смотреть без "метких" комментариев. Жалко, что не все это понимают.
P.P.S. Пойдемте на каток как-нибудь? :)
|
December 7th, 2009
11:16 pm - Опять математика
Есть такой любопытный факт. Рассмотрим ненаправленный граф. У него есть две характеристики: длина кратчайшего простого цикла и хроматическое число (наименьшее количество цветов, в которое можно раскрасить вершины так, чтобы все ребра были разноцветными). Интуитивно кажется, что если нет коротких циклов, то хроматическое число маленькое. Однако, это не так. Оказывается, что для любых p и q существует граф, в котором нет циклов длины меньше p, и хроматическое число которого не меньше q. Это результат Эрдеша 1959 года. Он показывает, почему определять хроматическое число трудно -- оно определяется нелокальными свойствами графа.
|
December 3rd, 2009
03:23 am - Тервер for dummies
А вот интересно: как читают тервер нематематикам? Не вводят же в подобных курсах сразу меру Лебега. И насколько строгое и стройное изложение в итоге получается?
Просто стало интересно, как объяснить тервер сильным школьникам, к примеру.
|
December 2nd, 2009
03:19 pm - За миллиард...
Наверное, мое самое любимое произведение Стругацких -- это "За миллиард лет до конца света". Прочитав интервью, обнаружил, что прототип Вечеровского -- вполне себе Сахаров. Забавно.
|
12:17 am - Blade Runner
"Blade Runner"... Довольно прикольная атмосфера без сюжета. Осциллографы в качестве компов -- это сильно, да. Еще чем-то напоминает "Кин-дза-дзу". Вобщем, рекомендую.
|
November 28th, 2009
10:24 pm - Амели
Сходили сегодня на Амели. Довольно-таки сочный фильм. Милый, наивный и светлый. Чем-то напомнил "Науку сна".
|
03:44 pm - Что-то странное
Нашел тут у себя планы каких-то двух летних рассказов. Выкладываю, не редактируя.
Хеширование без коллизий: http://narod.ru/disk/15463168000/main.pdf.html
Теорема о неподвижной точке: http://narod.ru/disk/15463179000/main.pdf.html
|
02:33 pm - Ночи без мягких знаков
Только созрел пойти на их концерт, как они развалились. :(
|
November 25th, 2009
11:34 pm - CS
Научился понимать результаты уровня FOCS/STOC/SODA. Осталось дело за малым -- научиться получать результаты такого уровня.
Это я к тому, что сегодня удалось разобраться в конструктивном доказательстве леммы Ловаса, что радует. Вот оно.
Тут есть более простая и понятная (но более слабая) версия того же утверждения.
|
November 24th, 2009
11:37 am - Решение предыдущей задачи
Пусть у нас есть монотонная булева функция (функция большинства как раз такая). Тогда ее можно выразить через "И" и "ИЛИ". Оказывается, наука умеет строить монотонную схему для функции большинства с глубиной O(log n) (это не сильно сложно, я это даже рассказывал школьникам на летних сборах). Покажем, как с ее помощью можно решить нашу задачу.
У нас есть два набора x1, x2, ..., xn и y1, y2, ..., yn. Известно, что в первом больше единиц, чем нулей, а во втором больше нулей, чем единиц. Первый набор хранится у Алисы, второй -- у Боба. Они должны обменяться O(log n) битами и найти такое i, что xi = 1, а yi = 0. Рассмотрим монотонную схему для функции большинства. У нее есть выход. Будем двигаться от него к какому-то входу, который и будет ответом. Будем поддерживать такой инвариант: если мы сейчас находимся на каком-то проводе, то его значение на наборе x равно единице, а на значении y равно нулю. Пусть мы находимся на каком-то проводе. Посмотрим, какой функциональный элемент идет последним. Если это конъюнкция, то Боб передает Алисе номер входа (1 бит), на котором значение на наборе y равно нулю, а если дизъюнкция, то Алиса передает Бобу номер входа, на котором значение на наборе x равно единице. Так, двигаясь, ко входам, мы получим требуемую переменную.
|
November 23rd, 2009
09:25 pm - Выборы
В одной демократической стране проходили выборы: выбирали президента. Было две кандидатуры: действующий президент и кандидат от оппозиции. В стране n избирателей. Выборы проходят по правилу большинства. По результатам выборов переизбрали действующего президента. Но независимые наблюдатели нашли массу огрехов и было решено провести выборы повторно. Провели. И что вы думаете -- на этот раз выбрали кандидата от оппозиции. Действующий президент, конечно, усмирил всех с помощью танков, но задумался... И решил покарать какого-нибудь избирателя, который вначале голосовал за него, а во второй раз отрекся. Но все оказалось не так просто. Результаты выборов хранились на двух суперкомпьютерах: первый тур хранился на одном, второй -- на другом. Президент поручил верховному программисту написать программу, которая найдет избирателя-перебежчика. Но все оказалось еще сложнее. Компьютеры появились в администрации президента не очень давно, поэтому сеть пока провести не успели. Пока ее заменяли секретарши, которые бегали с бумажками между компьютерами. На каждой бумажке был записан один (!) бит. Вот и возникла у программиста непростая задача: обойтись лишь O(log n) пересылками бумажек между компьютерами и найти предателя.
Как вы думаете, что предпринял программист?
|
03:12 pm - Функан revisited
Сейчас я буду пытаться понять доказательство спектральной теоремы. Надеюсь, я выживу.
|
November 22nd, 2009
11:54 pm - ACM
Вася Астахов -- нереальный отец. Это я к тому, что сегодняшний кубок команда MSU Unpredictable писала в составе Астахов-Гусаков-Корнаков. И блистательно выиграла.
|
11:42 am - Иудейская война
Читаю тут в перерывах между функаном Фейхтвангера. Узнал наконец-то, почему задача Иосифа Флавия так называется. :) На самом деле, книга просто замечательная.
|
November 15th, 2009
11:37 pm - Дела :)
Что-то на меня какое-то нереальное количество дел навалилось. Будем разгребать. Как бы только не свихнуться?
|
November 13th, 2009
12:11 am - Задача
Есть множество из 1000 элементов. Рассмотрим какое-то семейство его подмножеств F. Известно, что каждый из 1000 элементов встречается ровно в 1 проценте элементов семейства. Доказать, что мощность F не превосходит 2^100.
|
November 12th, 2009
11:10 am - ACM ICPC
Ура, мы прошли в финал (который, кстати, состоится в Харбине) и заняли 2 место! Удалось нормально собраться и не слажать старт. Удалось затолкать минкост в 3 секунды, удалось не набажить в геометрии и вообще... Все было замечательно! Ну а теперь миллиарды дел. Привет, приятная обыденность.
Нет, правда, ради таких моментов стоит жить.
|
November 8th, 2009
04:14 pm - Дыбр
Прочитал сегодня "Гадкие лебеди". Как раз погода соответствующая: беспросветный дождик и туман. Теперь дилемма: перечитать "За миллиард лет до конца света" или прочитать "Град обреченный".
Сегодня уезжаем на NEERC. Последний для нас в таком составе. Мы будем очень стараться, потому что конкуренты на редкость сильные.
После NEERC'а напишу про информацию в комбинаторике, про различие олимпиадной и математики и про тепло.
|
|
|
