Разработка и сложность алгоритмов - как мыслить таким образом?

15

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

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

Основная проблема, с которой я сталкиваюсь в этом курсе (и аналогичных теоретических курсах): Как я узнаю, что решения, которые я придумаю, правильные? Я считаю теоретическую часть произвольной, особенно когда «доказательство» определенного алгоритма действует или ведет себя определенным образом?

Наш курс будет использовать стандартный текст: Введение в алгоритмы от CLRS.

Есть ли учебники / сайты / книги / и т. Д. что может предложить способ стать уверенным в этой области?

Спасибо всем,

Джейсон Дейн

Джейсон Дейн
источник
2
Я предлагаю взглянуть на этот пост . Я специально предлагаю книгу Уди Манбера.
MS Dousti
1
Это обсуждение StackOverflow предлагает несколько предложений: stackoverflow.com/questions/2256721/…
Джефф
2
Я второй рекомендации Manber. Также посмотрите, как думать об алгоритмах Джеффа Эдмондса: amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104
Джефф
«Откуда мне знать, что решения, которые я придумаю, верны?» Вы имеете в виду, что (1) вы придумали алгоритм, но не знаете, как доказать его правильность, или (2) у вас есть доказательство, но вы не уверены в его правильности?
Юкка Суомела
Шаг первый: перестаньте давать прямые ответы и вместо этого обратитесь к решениям других. ;)
Рафаэль

Ответы:

18

Я думаю, что курсы по разработке алгоритмов и сложности вычислений всегда сложны для студентов, которые не знакомы с этими предметами, потому что они требуют определенной степени математической зрелости и навыков решения проблем. В моем первом выпускном курсе по «вычислительной сложности» мой друг, который получил степень по чистой математике, сказал мне, как он удивлен тем, что хотя этот курс не требует большого математического образования (по крайней мере, это было сказано в план курса), это фактически потребовало почти все навыки, которые он получил через все его степень бакалавра математики!

Я обнаружил, что больше всего узнал о «пути» (когда я впервые начал обучение в аспирантуре), читая и выполняя упражнения из книги Сипсера . Обязательно выполняйте упражнения, потому что навыки решения проблем и математическая зрелость - это то, что вы хотите изучить, а не просто набор фактов или определений.

Однако книга Сипсера хороша только для сложностей и NP-полноты, ее недостаточно для замены книги CLRS. Единственная проблема с книгой CLRS состоит в том, что ее преимущество всестороннего охвата может стать ее слабостью, так как книга может выглядеть довольно страшной или подавляющей для студентов. Поэтому я советую вам действительно пойти в библиотеку и поискать книги по алгоритмам, просмотреть одну за другой и выбрать те, которые наиболее соответствуют вашему образу мышления. И снова не забывайте делать упражнения!

Для алгоритмов я лично предлагаю следующие книги (помимо тех, которые предложены Sadeq и JeffE):

  • Очень читаемая и красивая книга Алгоритмы С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани.
  • Записки убийцы (или книжный набросок) Джеффа Эриксона. (Поскольку Джефф слишком скромен, чтобы предлагать свои заметки, я должен сделать это сам.)

В общем, всякий раз, когда вы изучаете определенный алгоритм или структуру данных, если каким-то образом изложение в вашем учебнике недостаточно ясно для вас, тогда лучшим способом будет поиск в google лекционных заметок по этой конкретной теме. В некоторых случаях различные объяснения одной и той же вещи в конечном итоге дают вам полную картину. По крайней мере, так у меня работает.

Дай Ле
источник
8
+1 для заметок убийцы Джеффа. Мне всегда нравится читать их. Арабская каллиграфия слова Алгоритм очень красивая.
Мухаммед Аль-Туркистани