Хорошая математическая книга по алгоритмам [закрыто]

11

Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую ​​литературу по алгоритмам и анализу алгоритмов. Теперь для меня не имеет большого значения, какие алгоритмы рассматриваются, но очень важно то , как они представлены и обрабатываются. Я больше всего ценю очень ясный и точный язык, который определяет все используемые понятия в строгой и абстрактной манере.

Я обнаружил, что классическое введение в алгоритмы , разработанное Корменом, Лизерсоном, Ривестом и Стейном, довольно изящно, но не очень хорошо справляется с математикой и довольно неформально с его доказательствами и определениями. Введение Сипсера в теорию вычислений кажется лучше в этом отношении, но все же не предлагает плавного перехода от математики к алгоритмам.

Кто-нибудь может порекомендовать что-нибудь?


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

k.stm
источник
2
Это субъективно; определить «хорошо». Кроме того, в то время как у нас нет строгой политики для вопросов списка, есть общая неприязнь . Обратите внимание также на это и это обсуждение; Вы можете улучшить свой вопрос, чтобы избежать проблем, описанных там. Если вы не знаете, как улучшить свой вопрос, может быть, мы поможем вам в чате по информатике ?
Рафаэль
Смежный вопрос .
Рафаэль
@ Рафаэль Спасибо. Я использовал только слово «хорошо» в названии, в своем вопросе я указал, что я хочу. Хотя я намеренно не стал слишком конкретным, по крайней мере, должно быть ясно, что я сосредоточен (как намекнул) на математическую элегантность и строгость . Я не думаю, что этот ответ кричит о списке книг, потому что не должно быть слишком много книг, попадающих в эту категорию, - и даже если это так, я не верю в это «сохранение чистоты строгого вопроса» структура ответа », что происходит на нескольких сайтах стек-обмена здесь, но я думаю, это не мой звонок. Я не уверен, что смогу улучшить вопрос.
ksstm
Кроме того, я не думаю, что «ссылка-запрос» подходит для вопроса. По крайней мере, не в соответствии с его описанием: я не ищу бумаги и не заинтересован в конкретной и узкой проблеме. На самом деле, я довольно открыт для того, чтобы охватить содержание, см. Мое второе предложение. Это нормально, если я снова уберу тег? Может быть, я мог бы и должен сузиться, какими алгоритмами я буду доволен?
k.stm
2
Возможно, вам следует изучить денотационную семантику и проверку программы.
Юваль Фильмус

Ответы:

7

Хендрик Ленстра писал в 1992 году :

Хотя с строгой математической точки зрения желательно, чтобы я определял, что я имею в виду под алгоритмом и временем его выполнения, я не буду этого делать. Мое главное оправдание в том, что я сам не знаю этих определений. Хуже того, я никогда не видел подходящей теории, которая была бы точной, элегантной и удобной для работы. Было бы похвальным занятием заполнить этот очевидный пробел в литературе.

Я не знаю, был ли достигнут какой-либо прогресс с тех пор, или же консенсус даже считает это «пробелом». Но дело в том, что, по крайней мере, некоторые выдающиеся математики были недовольны математической строгостью вывода алгоритмов. Таким образом, возможно, не существует книги с желаемым уровнем формализма ОП.

Рог изобилия с практическими перспективами, которые мы имеем благодаря Кнуту, Гризу , Степанову и другим, призваны помочь программистам больше, чем математике, и поэтому неизбежно не соответствуют строгости и долго не подвержены субъективности.

Тем не менее, работа Степанова широко приветствуется в Силиконовой долине как одна из лучших попыток научного синтеза.

В « Элементах программирования» Александр Степанов и Пол МакДжонс пытаются заложить абстрактные алгебраические основы алгоритмов. Книга начинается с, по общему признанию, несколько неформальных аксиоматических определений сущностей, ценностей и их атрибутов, но на 288 страницах дедуктивно продвигается через серию лемм к основам Стандартной библиотеки шаблонов.

TOC, предисловие и образец главы о трансформациях и их орбитах можно найти здесь , а также вводную лекцию здесь .

Более свежая и непринужденная книга Степанова « От математики к общему программированию» структурирована в большей степени путеводителем по истории математики, основанным на умножении египтянина на моноиды, полугруппы и теореме Лагранжа, в конечном итоге на разработке современных структур данных с их итераторами и алгоритмами, используемыми в STL.


источник
?!? «в настоящее время не существует точного, элегантного и удобного математического вывода концепции алгоритма ...» как насчет машины Тьюринга!
vzn
1
Ленстра обращается к машинам Тьюринга в связанной статье, но я думаю, что идея в том, что они не дают полного алгебраического анализа. Цитата в значительной степени дословная, включая часть «пробела», если вы хотите прочитать ее самостоятельно. Я отредактирую пост, чтобы удалить предложенный «консенсус», на случай, если он будет считаться дискуссионным.
OFC утра / сознавал вы цитировали Ленстра , но вы можете добавить кавычки или более длинную цитату из его замечательной / дискуссионной / сомнительное утверждение
ВЗН
думаю, что машины Тьюринга не могут быть получены , наоборот, они образуют аксиому вычислительной системы ( тезис Черча-Тьюринга ). это весь анализ Lenstras и CS в целом, который получен из аксиомы существования TM.
vzn
1
@ Рафаэль, если мама говорит, что это будет "похвальное предприятие", чтобы убрать мою комнату должным образом, суть ее речи заключается в том, чтобы "не беспокоиться о уборке своей комнаты". Я вас неправильно понимаю, или вы меня неправильно понимаете?
7

Я думаю, что книга, которую вы описываете, имеет название. Это в семи томах, только три с половиной из которых были опубликованы. Она называется «Искусство компьютерного программирования» (TAOCP) и написана Дональдом Кнутом.

Вполне возможно, что он иногда будет описывать приложения. Но вы всегда можете пропустить это, и я сомневаюсь, что это составляет большую часть контента. Вы не должны быть слишком разочарованы математикой.

Babou
источник
Я боялся, что этот ответ может прийти. Я посмотрел в нее, и она меня не устраивала. «Вы не должны быть слишком разочарованы математикой». - возможно, но Кнут также, кажется, не определяет вещи, но он скорее представляет это неофициально, объясняя это. Здорово донести идею, но не то, что я ожидаю от математики.
ksstm
Возможно, вы могли бы внести свой вклад в эту область, опубликовав математически запутанную версию его работы. Но если вас интересует «плавный переход от математики к алгоритмам», лучшей темой для вас может быть теория типов. Связь между математикой и алгоритмами все еще остается предметом исследования.
Бабу
1
PS Если вы «боялись, что этот ответ может появиться», вы должны были сказать это в своем вопросе, поскольку это один из основных справочников. Полные и задокументированные вопросы получают лучшие ответы.
Бабу
Он пришел ко мне только после того, как я задал вопрос, когда я был далеко от компьютера. Мое замечание о книге Кнута не должно восприниматься уничижительно (как я думаю, что вы восприняли это как «публикацию математически запутанной версии») - это было бы похоже на богохульство. Его путь просто не тот, который я ищу. Может быть, там нет ничего похожего на то, что я себе представляю ...
k.stm
2
@ k.stm Ну, забудьте про запутанность, которая сама по себе является целой темой. Дело в том, что я считаю, что алгоритмика - это еще не математика. Может случиться так, что вы можете получить формализации, но они, вероятно, будут простыми кодировками, которые теряют сущность, с небольшой выгодой. Это зависит от темы. Это, вероятно, гораздо менее верно для теории автоматов, которая имеет значительную алгоритмику. Дело в том, что адекватное выявление абстрактной математической природы структур неочевидно. Это вопрос понимания, а не формализации, и это занимает годы. Думайте об этом как о физике
Бабу