Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую литературу по алгоритмам и анализу алгоритмов. Теперь для меня не имеет большого значения, какие алгоритмы рассматриваются, но очень важно то , как они представлены и обрабатываются. Я больше всего ценю очень ясный и точный язык, который определяет все используемые понятия в строгой и абстрактной манере.
Я обнаружил, что классическое введение в алгоритмы , разработанное Корменом, Лизерсоном, Ривестом и Стейном, довольно изящно, но не очень хорошо справляется с математикой и довольно неформально с его доказательствами и определениями. Введение Сипсера в теорию вычислений кажется лучше в этом отношении, но все же не предлагает плавного перехода от математики к алгоритмам.
Кто-нибудь может порекомендовать что-нибудь?
Ответ: Алгоритмы должны по крайней мере задействовать управление необходимыми данными, используя классические нетривиальные абстрактные структуры данных, такие как графы, массивы, множества, списки, деревья и т. Д., Предпочтительно также работая с такими структурами данных. Я не был бы слишком заинтересован, если бы проблема использования и управления структурами данных была полностью проигнорирована. Хотя меня не волнуют проблемы, решаемые с ними.
Ответы:
Хендрик Ленстра писал в 1992 году :
Я не знаю, был ли достигнут какой-либо прогресс с тех пор, или же консенсус даже считает это «пробелом». Но дело в том, что, по крайней мере, некоторые выдающиеся математики были недовольны математической строгостью вывода алгоритмов. Таким образом, возможно, не существует книги с желаемым уровнем формализма ОП.
Рог изобилия с практическими перспективами, которые мы имеем благодаря Кнуту, Гризу , Степанову и другим, призваны помочь программистам больше, чем математике, и поэтому неизбежно не соответствуют строгости и долго не подвержены субъективности.
Тем не менее, работа Степанова широко приветствуется в Силиконовой долине как одна из лучших попыток научного синтеза.
В « Элементах программирования» Александр Степанов и Пол МакДжонс пытаются заложить абстрактные алгебраические основы алгоритмов. Книга начинается с, по общему признанию, несколько неформальных аксиоматических определений сущностей, ценностей и их атрибутов, но на 288 страницах дедуктивно продвигается через серию лемм к основам Стандартной библиотеки шаблонов.
TOC, предисловие и образец главы о трансформациях и их орбитах можно найти здесь , а также вводную лекцию здесь .
Более свежая и непринужденная книга Степанова « От математики к общему программированию» структурирована в большей степени путеводителем по истории математики, основанным на умножении египтянина на моноиды, полугруппы и теореме Лагранжа, в конечном итоге на разработке современных структур данных с их итераторами и алгоритмами, используемыми в STL.
источник
Я думаю, что книга, которую вы описываете, имеет название. Это в семи томах, только три с половиной из которых были опубликованы. Она называется «Искусство компьютерного программирования» (TAOCP) и написана Дональдом Кнутом.
Вполне возможно, что он иногда будет описывать приложения. Но вы всегда можете пропустить это, и я сомневаюсь, что это составляет большую часть контента. Вы не должны быть слишком разочарованы математикой.
источник