Страница Алексея Яшунского

For our weekly research class I had to prepare a presentation of "On random matrices" by Erdös and Rényi. Despite the title, it is essentially about bipartite graphs, proving that a random bipartite graph on vertices ( vertices in each part) with edges has positive probability of containing a set of independent edges as grows infinitely.

The paper is written in an over-concise manner and relies heavily on tricky manipulation of binomial coefficients. I spent several days figuring out all the details, so I thought it would be nice to have the commentary online, should someone ever need help on the paper.
Читать далее »

Задача о Васе в интернете.

Задача навеяна условием задачи "на соображение" из журнала Компьютерра. Программист Вася играет в интернете в такую игру: начиная с какой-то страницы он начинает ходить по страницам, переходя всегда по первой ссылке со страницы. Известно, что с каждой страницы есть хотя бы одна ссылка.

Как ему понять, что он уже "зациклился", если его браузер умеет сохранять только конечное число "закладок"? (в оригинальном условии — 2 закладки).

Участвовали: Володя, Лёша, Катя, Саша, Лена, Алёша, Настя, я.

Саша довольно быстро заметил, что на самом деле достаточно одной закладки, после чего мы занялись подсчётом сложности алгоритма в зависимости от размера и конфигурации той части сети, по которой Вася "путешествует".

Текст получился путаным, но, боюсь, что ничего более толкового я в ближайшее время не напишу, а потом — и подавно 🙁
невероятная куча вычислений

Рассматривалась задача об обмене фотографиями (она же — задача о сплетницах).

n человек съездили вместе в Калининград, каждый со своим фотоаппаратом. После этого они решили обменяться фотографиями. Когда два человека обмениваются, каждый переписывает себе все фотографии, которые к этому моменту есть у другого. Вопрос: сколько обменов данными надо осуществить, чтобы у всех были все фотографии?

Участвовали: Володя, Лёша, Катя, Саша, Оля, Кирилл, я.

маленькая часть решения

"Теперь здесь офис." (с)

— Когда о нас, математиках, говорят, как о сухарях, это ложь. Ложь! В любви я Эйнштейн. Я вот что хочу сказать: я хочу быть с вами.
— Иди, подожди на улице, я выйду.
— Правда? Иду! — уходит, но потом возвращается: — Поклянись!
— Чтоб я сдох! ... Иди, начерти пару формул.
— Хорошо.