2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Конкурс для программистов - решение целочисленной СЛУ
Сообщение01.02.2011, 10:56 


26/01/10
959
Предлагаю принять участие в очередном конкурсе для программистов.

Предлагается написать программу, решающую целочисленную систему линейных уравнений
$$
Ax=b.
$$
Матрица системы и вектор правой части - целочисленные. Числа в них умещаются в 32 бита со знаком (от $-2^{31}$ до $2^{31}-1$). Ответом будет вектор рациональных чисел $x$. Числа в ответе могут получиться очень длинными, поэтому НЕ запрещается использовать библиотеки длинной арифметики (GMP, MPIR).

Предлагается ограничиться системами порядка $n=200$, но если участник предложат слишком быструю реализацию, можно увеличить это ограничение.

Кого заинтересовало, можете узнать подробности конкурса.

Почему я решил провести такой конкурс? Оказывается, мало кто умеет эффективно решать такую известную задачу в случае целых чисел, когда ответ должен быть точным. А победитель конкурса мог бы поделиться своим опытом с остальными.

К сожалению, у меня нет возможности тестировать задачу НЕ в системе Windows 7, поэтому предлагается два варианта участия: можно присылать либо EXE файлы, либо CPP, которые будут компилироваться на нашей рабочей машине. Понимаю, что не пишущих на CPP или не под Windows обижаю, но ничего не поделаешь. Конкурс любительский.

Модераторам: форум dxdy.ru указан в качестве информационного спонсора на странице конкурса.

 Профиль  
                  
 
 Re: Конкурс для программистов - решение целочисленной СЛУ
Сообщение11.02.2011, 14:18 


26/01/10
959
Конкурс завершился. Вот грустные итоги, а вот схема моего решения.

Было удивительно то, что я в советской / российской литературе никаких быстрых алгоритмов для точного решения целочисленных систем не нашёл. И на тех русскоязычных форумах, где я искал, нет никаких намёков на то, что задача может быть решена на порядки быстрее, чем методом Гаусса и его целочисленными аналогами.

Может я плохо искал? Или всё действительно так печально?

 Профиль  
                  
 
 Re: Конкурс для программистов - решение целочисленной СЛУ
Сообщение11.02.2011, 18:27 
Аватара пользователя


31/10/08
1244
Скорее всего плохо искали.
Есть замечательная книжка. Правда автор не русский. Но переведена.
Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов.

Там есть ряд алгоритмов. А еще там много идей, но я их еще плохо воспринимаю.

А возможно что и нет. И вся хвалёная Российская наука отстала лет на 20.
Я специализируюсь на обработки сигналов. Есть хорошо известный алгоритм Гаусовского размытия. Так вот вопрос в быстрой реализации. Везде описан через КИХ. Но это медленный алгоритм гораздо быстрее работает через БИХ. Но негде толкового описания на Русском не удалось. Оно отсутствовало. Когда как пришлось разбираться с английским текстами от 1994 года. Нашёл, реализовал. Проверил на простых вариантах всё работало. Спустя время руки дошли до того чтобы сделать 2D вариант. И выяснилось что в алгоритме ошибка. В результате сейчас полез разбираться. Нашел еще пару статей. А да алгоритм известен давно еще в 60-годах и ранее. А публикации американские 85,94,96 года. А русской ни одной.
Есть известный проект OpneCV так вот там до сих пор не реализован быстрый алгоритм. А да на первых порах его развивали Русский коллектив.

Есть ещё много алгоритмов о которых не написано в Русской литературе.

 Профиль  
                  
 
 Re: Конкурс для программистов - решение целочисленной СЛУ
Сообщение11.02.2011, 19:23 


26/01/10
959
Цитата:
Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов.

Мне почему-то казалось, что я внимательно листал эту книгу. Но не могли бы вы указать её раздел, в котором есть что-то про быстрое решение целочисленной СЛАУ?

Кстати, в этой же книге есть забавные алгоритмы решения теплицевых систем. Они всего-то в несколько миллионов раз медленнее, чем алгоритмы решение обычной системы, которая не имеет специального вида. Представляете как здорово? Мне всегда казалось, что алгоритмы для задачи специального вида должны работать быстрее. Но нет...

 Профиль  
                  
 
 Re: Конкурс для программистов - решение целочисленной СЛУ
Сообщение15.02.2011, 07:54 


15/02/11
1
Разве обязательно на Спп?
Можно на других ЯП писать? а то я с большими числами в си ни разу не сталкивался:)

 Профиль  
                  
 
 Re: Конкурс для программистов - решение целочисленной СЛУ
Сообщение15.02.2011, 08:57 


26/01/10
959
crab2 в сообщении #413157 писал(а):
Разве обязательно на Спп?
Можно на других ЯП писать? а то я с большими числами в си ни разу не сталкивался:)


Вы знаете, конкурс уже давно закончился.

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


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

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

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



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

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


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

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