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

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

Изменено 09.05.2016 9:41 LaptevVV

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

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

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

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

Содержание:
1. Основы анализа алгоритмов.
Ну, здесь достаточно простым языком объясняется, что анализируем, скорости роста, нижние границы...
Вспоминаем элементарную математику, логарифмы, суммы, факториалы и т.п.
2. Рекурсивные алгоритмы.
Тут математика рекуррентных соотношений и собственно анализ рекурсивных алгоритмов с их помощью.
Рассматриваются три задачи: пара ближайших точек, выпуклая оболочка и генерация перестановок.
Все довольно подробно объясняется словами, а вот математического анализа как такового нет. Так — пара формул приводится, и все.
Здесь же про связь рекрсии со стеком.
3. Поиск и выборки.
Поиск линейный и двоичный. Здесь анализ как раз есть — длинные формулы суммирования на пол-страницы.
Выборка — это поиск к-то по величине значения в массиве.
4. Сортировка. (ответы на упражнения начинаются с главы 4).
Тут классика: вставки, пузырек, Шелла, поразрядная (почему-то названная корневой),
пирамидальная, быстрая, слияние и внешнее многофазное слияние.
Анализ худшего и анализ среднего случаев. И в зависимости от сортировки — нюансы.
5. Численные алгоритмы.
Конспективная глава: схема Горнера, умножение матриц по Винограду и Штрассену,
решение систем линейных уравнений по схеме Жордана-Гаусса.
Никаких рассуждений не приводится, просто сразу даются таблички с формулами количества операций.
6. Алгоритмы формальных языков.
Книжки МакКоннелла по алгоритмам переводились не менее 2 раз.
У меня на руках такая:
Дж. МакКоннелл. Анализ алгоритмов. Активный обучающий подход.
3-е дополненное издание. — М.: Техносфера, 2009. — 416 с.

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

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

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

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

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

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

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

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

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

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