Prog.Stone progstone@yandex.ru
декабрь 2001
"Мой отец считает, что библиотечная наука лежит в основе всех наук, так же, как ключом ко всем наукам является математика, и что выживем мы или погибнем зависит от того, как хорошо справятся со своим делом библиотекари." Роберт Хайнлайн "Наука снимала сливки, прогоняла их через отжимающую машину двузначной логики, и размещала знания в той форме, в которой каждый мог ими пользоваться." Роберт Хайнлайн "Уолдо" "Я не нашла никаких ответов. Но зато теперь знаю несколько правильных вопросов." Орсон Скотт Кард "Игра Эндера" "Если ты обладаешь мудростью, а другое лицо знает, что нуждается в этой мудрости, поделись ею с радостью. Но если эта другая особа еще не знает, что ей нужна твоя мудрость, придержи ее у себя. Еда пробуждает восхищение лишь у голодного человека." Орсон Скотт Кард "Ксеноцид" |
Итак, задача: найти в Сети алгоритм. Для начала определимся - что это такое. Одно из определений - "Алгоритм - пошаговая процедура для решения задачи за конечное время" - допускает широкое толкование.
Сузим круг до алгоритмов для компьютеров и математических методов (в каком-то смысле это математический экстремизм, но деваться некуда, ведь компьютер - это воплощенная в "железе" математика). Вот что об этом говорит математик Карлис Подниекс [0]: "Формальные теории - это физические объекты. Т.е. приложение таких теорий к некоторому природному или техническому явлению подразумевает эксплуатацию реально существующего (физического!) изоморфизма между двумя физическими объектами - теорией и явлением. Но, конечно, формальные теории - физические объекты особого рода - я назвал бы их "цифровыми" объектами, поскольку все они могут быть реализованы (по определению!) как программы для цифровых компьютеров." [Конечно, эти слова можно воспринять как шутку, учитывая платонизм математиков, подмеченный Подниексом же в книге "Теорема Геделя о неполноте", и вопросы, которые он сам после этих слов ставит. "Сужение круга", по-видимому, тоже шутка.]. "Именно разработанность математических моделей (наличие готовых алгоритмов, общих методов) делает их применение таким эффективным. Ведь модель, если ее единственное достоинство - адекватность оригиналу, сама по себе бесполезна, если нет методов и алгоритмов, позволяющих в реальное время вывести заключения, дающие новые знания об оригинале."
Процедуру решения задачи можно показать на пальцах, описать в виде текста, формул, блок-схем, псевдокода, наконец, исходного текста на одном из языков программирования. Поэтому источниками алгоритмов могут быть книги, статьи, исходные тексты (как реализации отдельных алгоритмов, так и библиотеки и даже исходники реальных законченных приложений). Причем наличие исходного текста представляется важным условием (а правовой вопрос использования опубликованных алгоритмов - это вопрос отдельный, хотя тоже важный). С учетом того, что математика - наука, то сохраняется научная традиция публиковать алгоритмы безвозмездно, т.е. даром.
Поэтому первыми источниками алгоритмов хотелось бы назвать фундаментальный труд Дональда Кнута "The Art of Computer Programming" ("Искусство программирования") [1], а также книги "Numerical Recipes [in C, in Fortran]. The Art of Scientific Computing" [2] ("Численные рецепты. Искусство научных расчетов"). [На русском языке первый трехтомник можно достаточно свободно купить в бумажном виде, в Сети - лишь фрагменты, о переводе же "Рецептов" мне не известно]. Добавлю еще такое чисто сетевое явление как Netlib [3] и Библиотеку алгоритмов [4] (последняя на русском языке). Круг тем вполне академичен - сортировка и поиск, численные методы, интегрирование и дифференцирование, решение систем дифференциальных уравнений и прочая, и прочая. Нужно также сказать, что во многих компьютерных журналах, представленных в Сети, можно найти как статьи, посвященные алгоритмам, так и целые библиотеки алгоритмов, как, например, ACM collected algorithms [5].
Есть такое подозрение, что у каждого действующего программиста есть своя собственная коллекция алгоритмов, статей, ссылок - просто как побочный результат работы над своими задачами. Некоторые не ленятся и выкладывают эти коллекции в Сети. Некоторые такие коллекции становятся большими (и полезными). Из таких коллекций упомяну лишь русскоязычные Algo4u [6] и Algolist [7], как посвященные именно алгоритмам. Нужно отметить, что подобные коллекции обычно шире "академических", и включают материалы и исходники по более прикладным темам (компрессия, криптография, обработка сигналов и изображений, искусственный интеллект, генетические алгоритмы, нейронные сети).
Из иноязычных ресурсов упомяну Cetus Links [8], Source Bank [9] и Programmer's Heaven [10], каждый из которых содержит море (тысячи и тысячи) упорядоченных ссылок, статей, библиотек и исходников.
Алгоритмы можно черпать и с сайтов, посвященных конкретным средствам разработки, как, например, ориентированный на борландовские продукты Уголок разработчика [11]. Вообще, интересные ссылки по алгоритмам можно обнаружить в самых неожиданных местах [12].
Я понимаю, что приведенные ссылки выбраны достаточно субъективно. Но эти сайты можно взять за отправные точки. А ведь еще есть каталоги, журналы, сайты, посвященные конкретным технологиям, продуктам, платформам и отдельным алгоритмам. И поисковики, наконец.
Еще один источник алгоритмов, причем в "боевом" исполнении, в контексте платформ, интерфейсов пользователя, форматов данных, API, языков программирования - это Linux. Ведь способность восстановить и понять из исходника положенные в его основу алгоритмы - пропуск в сообщество.
Пожалуй, общая закономерность - все эти ресурсы, как правило, свободны. Объяснить это можно многими причинами, например, той же научной традицией или взаимовыручкой программистов. И, возможно, еще одним немаловажным фактором: сами по себе алгоритмы - это еще не решение прикладной проблемы, их ведь еще нужно встроить в прикладную систему (с учетом платформы, целевого языка, архитектуры прикладной системы и т.д.), да еще, при необходимости, написать и отладить. Кроме того, конкретные реализации обычно создаются исходя из вполне конкретных предпосылок, а они, предпосылки, могут оказаться совсем другими в иной ситуации. (Некоторые программисты-прикладники предпочитают реализовывать алгоритмы самостоятельно, поскольку потом они знают, с чем имеют дело.)
Хотя не секрет, что вычислительная мощность современных процессоров избыточна для многих задач и можно обойтись решением в лоб, этот аргумент не универсален (запас вычислительной мощности быстро исчерпывается, семь уступок - и от лба ничего не остается) и поэтому мне не нравится.
По-видимому, как следствие из теоремы Геделя, программистам всегда будет чем заняться помимо изобретания велосипедов. Ведь как только программное решение отлито в коде, тут же найдется задача или проблема, которая этому решению не по зубам.
[0] Karlis Podnieks http://www.ltn.lv/~podnieks/
[1] Donald Knuth http://www-cs-faculty.stanford.edu/~knuth/taocp.html
[2] http://www.nr.com/ Numerical Recipes
[3] http://plan9.bell-labs.com/netlib/master/readme.html Netlib
[4] http://alglib.chat.ru/ Библиотека алгоритмов
[5] http://www.acm.org/calgo/contents/ ACM collected algorithms
[6] http://algo.4u.ru/ Algo4u
[7] http://algolist.da.ru/ Algolist
[8] http://oop.rosweb.ru/cetus/software.html Cetus Links
[9] http://www.sourcebank.com/ Source Bank
[10] http://www.programmersheaven.com/ Programmer's Heaven
[11] http://www.akzhan.midi.ru/devcorner/devcorner-home-rus.html
Акжан в Сети. Уголок разработчика
[12] http://www.sevmashvtuz.edu.ru/links/algorithms.html