Информация об изменениях

Сообщение Re: МакКоннелл от 23.04.2016 14:34

Изменено 09.05.2016 10:23 LaptevVV

Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
У меня на руках такая:
Дж. МакКоннелл. Анализ алгоритмов. Активный обучающий подход.
3-е дополненное издание. — М.: Техносфера, 2009. — 416 с.

Книжка весьма неплохая.
Глав всего 11. К каждой главе есть упражнения.
В начале каждой главы определены цели изучения и даны советы по изучению.
Видимо, это и называется активным обучающим подходом...

В конце книги приведены ответы к некоторой части упражнений.

Алгоритмы приводятся на псевдокоде, похожем на паскаль (как у Рода Стивенса).
Иногда с вкраплениями неформальных действий (как у Вирта в методе пошагового уточнения).
Математика есть, хотя и не такая серьезная, как в Кнуте и Кормене.

Содержание:
1. Основы анализа алгоритмов.
Ну, здесь достаточно простым языком объясняется, что анализируем, скорости роста, нижние границы...
Вспоминаем элементарную математику, логарифмы, суммы, факториалы и т.п.

2. Рекурсивные алгоритмы.
Тут математика рекуррентных соотношений и собственно анализ рекурсивных алгоритмов с их помощью.
Рассматриваются три задачи: пара ближайших точек, выпуклая оболочка и генерация перестановок.
Все довольно подробно объясняется словами, а вот математического анализа как такового нет. Так — пара формул приводится, и все.
Здесь же про связь рекрсии со стеком.

3. Поиск и выборки.
Поиск линейный и двоичный. Здесь анализ как раз есть — длинные формулы суммирования на пол-страницы.
Выборка — это поиск к-то по величине значения в массиве.

4. Сортировка. (ответы на упражнения начинаются с главы 4).
Тут классика: вставки, пузырек, Шелла, поразрядная (почему-то названная корневой),
пирамидальная, быстрая, слияние и внешнее многофазное слияние.
Анализ худшего и анализ среднего случаев. И в зависимости от сортировки — нюансы.

5. Численные алгоритмы.
Конспективная глава: схема Горнера, умножение матриц по Винограду и Штрассену,
решение систем линейных уравнений по схеме Жордана-Гаусса.
Никаких рассуждений не приводится, просто сразу даются таблички с формулами количества операций.

6. Алгоритмы формальных языков. В книжках по алгоритмам этого практически не встречается.
Главу смело можно рекомендовать как введение в формальные грамматики и автоматы.
Конечные автоматы детерминированные и недетерминированные, регулярные выражения и регулярные грамматики.
Эквивалентности, преобразование автомата в программу, проектирование, ограничения и возможности.
МП-автоматы детерминированные и недетерминированные, контекстно-свободные грамматики,
преобразование грамматик, нормальная форма Грейбах.
Преобразование грамматики в МП-автомат, проектирование МП-автомата, ограничения и возможности.
Введение в синтаксический разбор.
Теорем нет, математики нет, и изложение очень практическое. С элементами теории формальных языков, грамматик и автоматов.

7. Сравнение с образцом.
Это поиск подстроки в строке.
Простой, конечно-автоматный упоминается, Кнута-Морисса-Пратта — основное содержание главы.
И немного про приблизительное сравнение строк. Анализ есть не везде, а где есть — очень лаконично, буквально 1 абзац.
Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
У меня на руках такая:
Дж. МакКоннелл. Анализ алгоритмов. Активный обучающий подход.
3-е дополненное издание. — М.: Техносфера, 2009. — 416 с.

Книжка весьма неплохая.
Глав всего 11. К каждой главе есть упражнения.
В начале каждой главы определены цели изучения и даны советы по изучению.
Видимо, это и называется активным обучающим подходом...

В конце книги приведены ответы к некоторой части упражнений.

Алгоритмы приводятся на псевдокоде, похожем на паскаль (как у Рода Стивенса).
Иногда с вкраплениями неформальных действий (как у Вирта в методе пошагового уточнения).
Математики мало. Фактически и не математика (как у Кнута), а просто вывод простых комбинаторных формул в некоторых алгоритмах.

Содержание:
1. Основы анализа алгоритмов.
Ну, здесь достаточно простым языком объясняется, что анализируем, скорости роста, нижние границы...
Вспоминаем элементарную математику, логарифмы, суммы, факториалы и т.п.

2. Рекурсивные алгоритмы.
Тут математика рекуррентных соотношений и собственно анализ рекурсивных алгоритмов с их помощью.
Рассматриваются три задачи: пара ближайших точек, выпуклая оболочка и генерация перестановок.
Все довольно подробно объясняется словами, а вот математического анализа как такового нет. Так — пара формул приводится, и все.
Здесь же про связь рекрсии со стеком.

3. Поиск и выборки.
Поиск линейный и двоичный. Здесь анализ как раз есть — длинные формулы суммирования на пол-страницы.
Выборка — это поиск к-то по величине значения в массиве.

4. Сортировка. (ответы на упражнения начинаются с главы 4).
Тут классика: вставки, пузырек, Шелла, поразрядная (почему-то названная корневой),
пирамидальная, быстрая, слияние и внешнее многофазное слияние.
Анализ худшего и анализ среднего случаев. И в зависимости от сортировки — нюансы.

5. Численные алгоритмы.
Конспективная глава: схема Горнера, умножение матриц по Винограду и Штрассену,
решение систем линейных уравнений по схеме Жордана-Гаусса.
Никаких рассуждений не приводится, просто сразу даются таблички с формулами количества операций.

6. Алгоритмы формальных языков. В книжках по алгоритмам этого практически не встречается.
Главу смело можно рекомендовать как введение в формальные грамматики и автоматы.
Конечные автоматы детерминированные и недетерминированные, регулярные выражения и регулярные грамматики.
Эквивалентности, преобразование автомата в программу, проектирование, ограничения и возможности.
МП-автоматы детерминированные и недетерминированные, контекстно-свободные грамматики,
преобразование грамматик, нормальная форма Грейбах.
Преобразование грамматики в МП-автомат, проектирование МП-автомата, ограничения и возможности.
Введение в синтаксический разбор.
Теорем нет, математики нет, и изложение очень практическое. С элементами теории формальных языков, грамматик и автоматов.

7. Сравнение с образцом.
Это поиск подстроки в строке.
Простой, конечно-автоматный упоминается, Кнута-Морисса-Пратта — основное содержание главы.
И немного про приблизительное сравнение строк. Анализ есть не везде, а где есть — очень лаконично, буквально 1 абзац.

8. Алгоритмы на графах.
Тут классика в минимальном объеме: обходы, поиск путей, остовное дерево.
Алгоритм определения компонент двусвязности, разбиение множеств (на массивах.

А вот следующая глава — это фишка книги.
9. Параллельные алгоритмы.
Сначала — классификация Флинна, описывается неформально каждый класс.
Потом кратенькое введение в архитектуры параллельных машин.
Важный параграф — Модель памяти PRAM. Простые операции в разных моделях PRAM.
И понеслась — параллельные алгоритмы поиска, сортировки (четно-нечетная, на линейных сетяхи др.).
Численные — параллельное умножение матриц, решение системы линейных уравнений.
Параллельные алгоритмы на графах.

10. Вычислимое и невычислимое.
Здесь все про машины Тьюринга (много всяких описано) и NP — довольно неплохо, на 50 страницах.

11. Другие алгоритмические инструмента.
Здесь собраны жадные алгоритмы, алгоритмы с возвратом, ветвей и границ,
вероятностные (в частности, Монте-Карло, Лас-Вегас, Шервудские).
И динамическое программирование.
Хорошая глава.

И в приложении еще Генерирование случайных чисел есть.
В общем — весьма неплохая книжка.
Алгоритмы с псевдокода легко конвертируются в Си-подобный язык.