Я ищу краткий вводный текст об алгоритмах с высоким отношениемОн должен начинаться с самого начала, но затем быстро развиваться, не тратя слишком много времени на примеры из реального мира, методики элементарных доказательств и т. Д. Как математик-исследователь, у меня есть глубокие знания в области математики, которые я с удовольствием использую, например, для понимания формализмов и сжатых доказательств. ,
Существуют ли такие тексты? Любые рекомендации?
ds.algorithms
Грегор
источник
источник
Ответы:
Мне очень нравится этот учебник:
Санджой Дасгупта, Христос Пападимитриу и Умеш Вазирани: Алгоритмы,
опубликованные McGraw-Hill 2007.
Я не подсчитываю предложенное вами соотношение, но думаю, вам тоже понравится :)
источник
Джефф Эриксон не скажет этого сам, но его онлайн-лекции являются одними из лучших, которые охватывают основы разработки алгоритмов на уровне, который не покровительствует читателю. Я использую их в своем классе алгоритмов градации, и для математика-исследователя эти заметки передают правильный вид (и уровень) интуиции, позволяя вам легко заполнять детали самостоятельно.
источник
Кнута « Искусство программирования », вероятно , будет книга с самым высоким отношением.
Если вам нужна книга в стиле учебника, то Cormen, Leiserson, Rivest и Stein " Введение в алгоритмы " были бы моим предложением для математика.
Есть также много лекционных заметок и несколько вики-книг по алгоритмам.
источник
Разработка алгоритмов Кляйнбергом Тардосом Эта книга помогает выработать конкретное понимание того, как разрабатывать хорошие алгоритмы, и говорить об их правильности и эффективности. (Я изучал это на первом курсе в колледже, очень читабельно)
Для онлайн копирования / записи лекций / ссылки, (как это было предложен Суреш Venkat) пойти с Джеффом Эриксоном конспектами . Они действительно потрясающие!
источник
Я бы пошел на комбинаторную оптимизацию: теория и алгоритмы - Korte & Vygen . Это даст вам хороший обзор алгоритмов с постоянным акцентом на оптимизацию. Эта книга предназначена для тех, кто с большим математическим уклоном ИМХО.
Это будет хорошо с Алгоритмами: Dasgupta & Papdimitrou, я полагаю.
источник
Я написал распоряжение для курса алгоритмов, которые я посещал. Это была цель именно этого; быть краткой версией наиболее важных тем, освещаемых в нашем текстовом поле (которое было CLRS). Я не хочу публиковать его на Scribd.com или где-либо еще, пока я не изучу документ полностью и не буду удовлетворен его содержанием, но рабочую копию можно получить по адресу https://github.com/CasperBHansen/DIKU_AD_2013/ . Чтобы прочитать его, вам нужно знать, как создать документ в формате pdf из исходного кода LaTeX, для чего предназначен репозиторий. Сам документ имеет длину всего 65 страниц.
Более старую копию можно скачать прямо с моего сайта по адресу http://casperbhansen.dk/files/ad-disposition.pdf - в ней, очевидно, содержится больше опечаток / ошибок, которые с тех пор были исправлены.
Он содержит несколько опечаток, потому что он был написан всего за несколько дней, когда он проходил еще один экзамен и, очевидно, готовился к экзамену на алгоритмы, отрабатывая доказательства, и я до сих пор исправляю опечатки и ошибки, поскольку с тех пор я был очень занят. Но я уверен, что любой, кто его читает, легко распознает ошибки, так как они обычно противоречат сопровождающему тексту или формулам, поэтому его легко выяснить всякий раз, когда происходит опечатка.
Я надеюсь, что это может помочь вам начать.
источник
Вот еще две ссылки, которые могут быть полезны.
Алгоритмы Седжвика вы назвали «вводными»; эта книга иногда используется в студенческих классах CS, хотя она может быть использована в некоторых аспирантуре. У Седжвика есть другие очень технические ссылки на TCS, и некоторые из этого математического стиля отражены в Алгоритмах и его в общем лаконичном стиле. покрытие очень важно для (T) CS (но не так сильно в продвинутых областях). Также, обратите внимание на «влияние», что он защитил кандидатскую диссертацию под руководством Кнута.
Компьютеры и труднопреодолимость, руководство к теории полноты NP более старой, но все еще очень актуальной ссылки. конечно, он фокусируется на полноте NP, но во многих отношениях «именно там много действия». область применения широка и, вероятно, будет привлекательна для математиков, поскольку она сфокусирована на многих математических объектах, например, на графиках и т. д., и обратите внимание на раздел, посвященный теории чисел. как говорится в википедии
источник
источник
попробуйте краткую энциклопедию информатики , Wiley. к сожалению, полное / полное оглавление для этой ссылки, по-видимому, недоступно в Интернете [в наше время это несколько необычное упущение, может быть, Wiley мог бы исправить это по запросу], но полный индекс , по-видимому, просматривается на amazon. он имеет охват, который намного шире, чем TCS, например, концепции аппаратного обеспечения и т. д., но, по-видимому, он охватывает важные части TCS, например:
это сокращенная версия полной энциклопедии 902pp, Энциклопедия компьютерных наук, 4-е издание , 2064pp
источник