2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Седьмой любительский конкурс по программированию
Сообщение10.04.2011, 21:11 


26/01/10
959
Модераторам: форум dxdy прорекламирован в видеопрезентации конкурса.

Предлагаю принять участие в седьмом любительском конкурсе по программированию.

Задача. Задан неориентированный граф $G=(V,E)$ без петель и кратных рёбер. Требуется посчитать в нём количество циклов длиной 3, 4, ..., n. (n - число вершин). Это называется статистика распределения циклов по длинам. Ограничение на число вершин $n\leq 21$ (для быстрых алгоритмов) и $n\leq 14$ для алгоритмов полного перебора.

Конкурс не совсем обычный, так как можно задействовать видеокарту GeForce 250 GTS и оба ядра процессора Core 2 Duo E8400.

Подробное описание конкурса с примером и видеопрезентацией на странице конкурса. В презентации даются дополнительные сведения о задаче и о конкурсе.

 Профиль  
                  
 
 Re: Седьмой любительский конкурс по программированию
Сообщение11.04.2011, 01:40 
Заслуженный участник


26/07/09
1559
Алматы
Zealint писал(а):
Требуется посчитать в нём количество циклов

Имеются ввиду простые циклы?

Может быть кому-нибудь будут полезны эти статейки:
N.Alon, R.Yuster, U.Zwick, Color-coding;
___, Finding and Counting Given Length Cycles.
В последней упомянутой работе, в частности даются "явные" формулы для $n\leqslant 7$.

 Профиль  
                  
 
 Re: Седьмой любительский конкурс по программированию
Сообщение11.04.2011, 07:22 


26/01/10
959
Цитата:
Имеются ввиду простые циклы?

Да, разумеется. Об этом сказано в презентации.

Цитата:
N.Alon, R.Yuster, U.Zwick, Color-coding;
___, Finding and Counting Given Length Cycles.
В последней упомянутой работе, в частности даются "явные" формулы для $n\leqslant 7$

Там нет формулы для k=7. Там есть только намёк на то, как она выводится. Саму эту формулу (как и остальные формулы до k=13) впервые получил мой коллега, на которого я ссылаюсь в видео.

 Профиль  
                  
 
 Re: Седьмой любительский конкурс по программированию
Сообщение24.04.2011, 19:31 


26/01/10
959
Конкурс завершился. Можно посмотреть итоги. Видео смотреть не обязательно, там только описание алгоритма имеет смысл, если кто-то его не изучал.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:54 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group