Обновить
20
0
Николай Мартынов@nikolaysmartynov

Разработчик

Отправить сообщение

Совершенный алгоритм. Алгоритмы для NP-трудных задач

Время на прочтение3 мин
Охват и читатели3.9K

Совершенный алгоритм. Алгоритмы для NP-трудных задач - четвертая и заключительная часть лекций от Тима Рафгардена.

Для NP-трудных задач мы снова имеем треугольник, в котором для решения предлагается выбрать две характеристики из трех:

- Универсальность

- Правильность (точность)

- Скорость

Компромисс по универсальности рассмотрен вскользь на примере задач о рюкзаке и взвешенном независимом множестве (максимизация суммы весов несмежных вершин). Хотелось бы больше примеров на эту тему ведь данный подход может дать наилучший результат. Тут и там можно встретить дополнительные примеры частных случаев, но какая-либо систематизация по данной теме не приводится.

Неточные алгоритмы - самые многочисленные из рассмотренных в книге.

Читать далее

Совершенный алгоритм. Жадные алгоритмы и динамическое программирование

Время на прочтение4 мин
Охват и читатели8.7K

Совершенный алгоритм. Жадные алгоритмы и динамическое программирование - это третья часть лекций от Тима Рафгардена. Стиль первых частей сохранён: тем и алгоритмов не много, но разобраны они детально и даны не просто готовыми, но автор показывает, как к ним можно было бы прийти.

Первое, что удивило так это неожиданная встреча с WSJF - weighted shortest job first. WSJF - это популярная методика приоритизации задач в Scrum и Kanban. Например, Дин Леффингуэлл в своём руководстве по SAFe (Agile Software Requirements: Lean Requirements Practices for Teams, Programs, and the Enterpriseна пальцах иллюстрирует результаты нескольких вариантов порядка выполнения задач (распределение эпиков, функциональностей и историй по инкрементам, итерациям и спринтам):

Читать далее

Совершенный алгоритм. Графовые алгоритмы и структуры данных

Время на прочтение2 мин
Охват и читатели7.3K

Вторая книга (Графовые алгоритмы и структуры данных) из серии Совершенный алгоритм Тима Рафгардена является продолжением, по сути, единого цикла лекций. Автор не только сохранил стиль первой книги, но и часто ссылается на материал, который был в ней преподнесён. Стиль обоих книг я считаю очень удачным. А именно, детальное и всестороннее изложение небольшого количества тем доступным языком.

Снова, это не каталог решений, а именно лекции. Поэтому автор далеко не сразу дает готовые алгоритмы. По сути, автор рассказывает как к этим алгоритмам можно прийти. Либо пробуя разные варианты, либо постепенно улучшая решения. Так например, поиск кратчайшего пути:

Читать далее

Совершенный алгоритм. Основы

Время на прочтение1 мин
Охват и читатели17K

Книга "Совершенный алгоритм. Основы" Тима Рафгардена первая в серии из четырёх книг примерно одинакового размера. В сумме они примерно соответствуют часто цитируемой классике "Алгоритмы. Построение и анализ".

Читать далее

Java. Решение практических задач

Время на прочтение9 мин
Охват и читатели11K

Книга Анджела Леонарда позиционируется как каталог типовых решений для Java разработчиков младшего и среднего уровней. Заявляется, что представленные решения производительны, корректны и поддерживаемы.

В книге все разбито на "задачи". Они тут нескольких типов:

Читать далее

Программирование: теоремы и задачи

Время на прочтение4 мин
Охват и читатели9.7K

После неудачного (с точки зрения эффективности траты времени) погружения в "Грокаем алгоритмы" по совету Яндекс Практикум и решения нескольких задач в "Бесплатный курс: подготовка к собеседованиям" от того же Яндекса решил поискать литературу на тему разбора задач. Довольно много рекомендаций указывало на книгу "Программирование: теоремы и задачи" от Александра Шень. Предыдущее издание книги можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.

Сам автор характеризует книгу как справочник и задачник для преподавателя. Причем во введении и аннотации упоминает школу на порядок чаще университета. Да и формулировки многих задач намекают на школьную аудиторию. На этом стоит остановиться сразу. Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.

Читать далее

Грокаем алгоритмы

Время на прочтение4 мин
Охват и читатели248K

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих от Бхаргава А. Эта книга рекомендована Яндекс Практикум при подготовке к алгоритмическому собеседованию. Сам автор указывает, что книга для самоучек, студентов, выпускников и тех, у кого программирование не является основным профилем.

Мое впечатление неоднозначно. С одной стороны, до сего момента я не встречал описания динамического программирования, поиска кратчайшего пути в графе по алгоритму Дейкстры и использование K ближайших соседей для классификации и аппроксимации (возможно, все это есть в 4м или последующих томах Кнута, но в магазине они мне не встречались). С другой стороны, описания и примеры, приведенные в книге, таковы, что практической пользы не представляют. Описания очень поверхностны, примеры нарочно примитивны, код в половине случаев не приведен. Но даже там где есть код, он нарочито упрощен под конкретный пример и на практике бесполезен.

Казалось бы, есть масса книг - каталогов шаблонов. Они реально полезны и новичку и профессионалу. Эта книга не из их числа. Но, видимо, это и не было целью. Напоминает научно-популярные книги издававшиеся в СССР: простым языком рассказывает о сложных вещах, прививает у читателя интерес к теме, расширяет кругозор. Не более. Но тоже важно.

Вернемся к Яндекс Практикум и их рекомендации. Если алгоритмы так важны, то почему именно эта книга? Есть масса других, где и алгоритмов больше и разобраны они так, что бери да пользуй. Например, классический труд Д. Э. Кнута Искусство программирования. Да, рисунки в детском стиле в Грокаем алгоритмы забавны. Но иллюстрации в Искусство программирования полезны для понимания. Разве это не важнее, если уж кандидата посылают на алгоритмическое собеседование?

Читать далее

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Дата рождения
Зарегистрирован
Активность