Erdös and Rényi's "On Random Matrices"

Математика Нет комментариев »

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 2n vertices (n vertices in each part) with n\log n + cn + o(n) edges has positive probability of containing a set of n independent edges as n 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.
Читать далее »

Математика в кафе. S2E2.

Математика 4 комментария »

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

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

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

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

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

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

Математика в кафе. S2E1.

Математика 3 комментария »

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

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

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

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

Львов. Шкотська кав'ярня.

Восточная Европа, Математика, Путешествия 5 комментариев »

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



из классики

Fun, Математика 3 комментария »

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

Тема WordPress и иконки разработаны N.Design Studio
© 2017 Страница Алексея Яшунского RSS записей RSS комментариев Войти