Автор: Джеймс Рос, Саймън Харис

Обем: 720 стр.

Размер в мм.: 165 х 235

Издател: АлексСофт

Корица: Мека

Година на издаване: 2006

Състояние: На склад при доставчик

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

Какво ще научите в тази книга:

• основи на алгоритми, като итерация и рекурсия
• елементарни структури като списък, стек и опашка
• основни и сложни алгоритми за сортиране включително сортиране с вмъкване, бързо сортиране и сортиране на Шел
• сложни структури от данни като двоични дървета, троични дървета и пирамида
• алгоритми за търсене и напасване на низове, хеширане и изчислителна геометрия
• как се използват техники за разработване, водени от тестове за гарантиране на качество
• как може да се подобри драматично производителността на един код с приложни техники за профилиране и оптимизация

Тази книга е за всеки, който разработва приложения или точно сега започва с това, и иска да разбере компютърните алгоритми и структурите от данни. Едно начално разбиране на програмирането би било от полза.

СЪДЪРЖАНИЕ:

За авторите
Благодарности
Въведение

• Кой трябва да чете тази книга?
• Нужни познания
• Какво ще научите?
• Как да използваме тази книга?
• Принципни положения
  • Давай по-просто
  • Не оптимизирайте прекалено
  • Използвайте интерфейси
  • Тествайте
  • Проверявайте всичко
• От какво имате нужда?
• Конвенции
  • Как да се използват упражненията?
• Изходен код
• Грешки
  • p2p.wrox.com

Начало

• Дефиниция за алгоритъм
• Разбиране на сложността по отношение на алгоритмите
• Нотация с “Голямо О”
  • Постоянно време – О(1)
  • Линейно време – О(N)
  • Квадратично време – О(N2)
  • Логаритмична сложност – О(log N) и О(N log N)
  • Факториелна сложност – О(N!)
• Модулно тестване
• Какво е модулното тестване?
  • Защо е важно модулното тестване?
  • Буквар по Junit
  • Разработване, водено от тестове
• Обобщение

Итерация и рекурсия

• Извършване на изчисления
  • Как работи?
  • Как работи?
• Обработка на масиви
  • Използване на итерация за преодоляване на проблеми с масиви
  • Как работи?
• Рекурсия
  • Пример за рекурсивно извеждане на дърво
  • Анатомия на рекурсивен алгоритъм
• Обобщение
• Упражнения

Списъци

• Какво са списъците?
• Тестване на списъци
• Реализиране на списъци
  • Масив-списък
  • Свързан списък
• Обобщение
• Упражнения

Опашки

• Понятия за опашки
  • Операции с опашки
  • Интерфейс на опашките
• Опашка “Първи влязъл, първи излязъл”
  • Реализиране на опашка FIFO
• Блокираща опашка
• Пример – симулация на център за обаждания
  • Стартиране на приложението
• Обобщение
• Упражнения

Стекове

• Стекове
• Тестове
• Реализация
• Пример – реализация на Undo/Redo
  • Тестване на Undo/Redo
• Обобщение

Основно сортиране

• Важност на сортирането
• Основи на сортирането
• Разбиране на компараторите
  • Операци на компаратор
  • Интерфейс на компаратор
  • Някои стандартни компаратори
  • Естествен компаратор
  • Метод за сортиране на мехурчето
  • Интерфейс ListSorter
  • Тестване на AbstractListSorter
• Сортиране с пряк избор
• Сортиране чрез вмъкване
• Какво е стабилност?
• Сравнение на основните алгоритми за сортиране
  • CallCountringListComparator
  • ListSorterCallCountingTest
  • Разбиране на сравнението на алгоритми
• Обобщение
• Упражнения

Сортиране за напреднали

• Разбиране сортирането на Шел
• Разбиране на бързото сортиране
• Разбиране на съставните компаратори и стабилността
• Разбиране на сортирането чрез сливане
  • Сливане
  • Алгоритъм за сортиране чрез сливане
• Сравняване на сложни алгоритми за сортиране
• Обобщение
• Упражнения

Приоритетни опашки

• Разбиране за приоритетни опашки
  • Проста приоритетна опашка
  • Работа с приоритетни опашки
  • Описание на неподредена приоритетна опашка върху списък
  • Какво е приоритетна опашка върху сортиран списък?
  • Какво е приоритетна опашка в подредена пирамида?
• Сравняване на реализации на приоритетна опашка
• Обобщение
• Упражнение

Двоично търсене и вмъкване

• Разбиране за двоично търсене
  • Подходи към двоичното търсене
  • List Searcher
  • Итеративно двоично търсене
  • Оценяване на работата на List Searcher
• Разбиране на двоично вмъкване
  • List Inserter
  • Оценяване на производителността
• Обобщение

Двоични дървета за търсене

• Разбиране за двоично дърво за търсене
  • Минимална стойност
  • Максимална стойност
  • Наследник
  • Предшественик
  • Търсене
  • Вмъкване
  • Изтриване
  • Поредно обхождане
  • Обхождоне “корен ляво дясно” (КЛД)
  • Обхождане “ляво дясно корен” (ЛДК)
  • Балансиране
• Тестване и прилагане на двоично дърво за търсене
• Оценка на производителността на двоично дърво за търсене
• Обобщение
• Упражнения

Хеширане

• Какво е хеширане?
• Работа с хеширане
  • Как работи?
  • Линейно сортиране
  • Работа с кофи
• Оценка на производителността
• Обобщение
• Упражнение

Множества

• Понятия за множества
  • Тестване на реализациите на множества
• Списъчно множество
• Хеш-множество
• Дървовидно множество
• Обобщение
• Упражнения

Карти

• Понятие за карти
• Тестване на реализациите на карта
• Списъчна карта
• Хеш-карта
• Дървовидна карта
• Обобщение
• Упражнения

Троични дървета за търсене

• Понятие за троични дървета з търсене
  • Търсене на дума
  • Вмъкване на дума
  • Търсене на представки
  • Съпоставяне на схеми
• Практическо използване на троични дървета за търсене
• Пример за помощник за кръстословици
• Обобщение
• Упражнение

В-дървета

• Понятието В-дърво
• Практическо използване на В-дървета
• Обобщение
• Упражнения

Търсене на низове

• Основен интерфейс за търсене на низове
• Основен тестов пакет
• Алгоритъм, използващ груба сила
• Алгоритъм Бойър-Мур
  • Създаване на тестовете
  • Реализиране на алгоритъма
• Итератор за съвпадение на низ
• Сравняване на производителността
  • Измерване на производителността
  • Как се сравяват?
• Обобщение

Съпоставяне на низове

• Запознаване със Soundex
• Запознаване с разстоянието в думи на Левенщайн
• Обобщение

Изчислителна геометрия

• Бърз опреснителен курс по геометрия
  • Координати и точки
  • Отсечки
  • Откриване на пресечната точка на две отсечки
  • Наклон
  • Пресичане на оста Y
• Откриване на пресечната точка
• Откриване на най-близката двойна точка
• Обобщене
• Упражнения

Прагматична оптимизация

• Къде се прилага оптимизацията?
• Понятие за профили
• Примерна програма FileSortingHelper
  • Профилиране с hprof
  • Профилиране с JMP
• Понятие за оптимизация
• Практическо приложение за оптимизацията
• Обобщение