Автор: Джеймс Рос, Саймън Харис
Обем: 720 стр.
Размер в мм.: 165 х 235
Издател: АлексСофт
Корица: Мека
Година на издаване: 2006
Състояние: На склад при доставчик
Доброто разбиране на известни компютърни алгоритми и знания кога и къде трябва да се прилагат са жизненоважни при създаване на софтуер, който не само работи правилно, но и ефективно. Това е единствената книга, която дава тази ценна информация – от основите на алгоритми, структури данни и характеристики на производителността до специфичните алгоритми в ежедневието.
Тази книга е пълна с подробни обяснения и ясни примери. Тя започва с представяне на някои фундаментални структури от данни и след това обяснява различни алгоритми за сортиране. После ще научите за ефективни методи за съхранение и търсене на информация чрез хеширане, дървета, множества и карти. Авторите дават съвети за оптимизиране и начини за избягване на чести грешки свързани с производителността. В края на тази книга ще бъдете готови да изграждате алгоритмите и структурите от данни, най-често срещани в ежедневната работа на програмистите.
Какво ще научите в тази книга:
- основи на алгоритми, като итерация и рекурсия
- елементарни структури като списък, стек и опашка
- основни и сложни алгоритми за сортиране включително сортиране с вмъкване, бързо сортиране и сортиране на Шел
- сложни структури от данни като двоични дървета, троични дървета и пирамида
- алгоритми за търсене и напасване на низове, хеширане и изчислителна геометрия
- как се използват техники за разработване, водени от тестове за гарантиране на качество
- как може да се подобри драматично производителността на един код с приложни техники за профилиране и оптимизация
Тази книга е за всеки, който разработва приложения или точно сега започва с това, и иска да разбере компютърните алгоритми и структурите от данни. Едно начално разбиране на програмирането би било от полза.
СЪДЪРЖАНИЕ:
За авторите
Благодарности
Въведение
- Кой трябва да чете тази книга?
- Нужни познания
- Какво ще научите?
- Как да използваме тази книга?
- Принципни положения
- Давай по-просто
- Не оптимизирайте прекалено
- Използвайте интерфейси
- Тествайте
- Проверявайте всичко
- От какво имате нужда?
- Конвенции
- Как да се използват упражненията?
- Изходен код
- Грешки
Начало
- Дефиниция за алгоритъм
- Разбиране на сложността по отношение на алгоритмите
- Нотация с “Голямо О”
- Постоянно време – О(1)
- Линейно време – О(N)
- Квадратично време – О(N2)
- Логаритмична сложност – О(log N) и О(N log N)
- Факториелна сложност – О(N!)
- Модулно тестване
- Какво е модулното тестване?
- Защо е важно модулното тестване?
- Буквар по Junit
- Разработване, водено от тестове
- Обобщение
Итерация и рекурсия
- Извършване на изчисления
- Обработка на масиви
- Използване на итерация за преодоляване на проблеми с масиви
- Как работи?
- Рекурсия
- Пример за рекурсивно извеждане на дърво
- Анатомия на рекурсивен алгоритъм
- Обобщение
- Упражнения
Списъци
- Какво са списъците?
- Тестване на списъци
- Реализиране на списъци
- Масив-списък
- Свързан списък
- Обобщение
- Упражнения
Опашки
- Понятия за опашки
- Операции с опашки
- Интерфейс на опашките
- Опашка “Първи влязъл, първи излязъл”
- Реализиране на опашка FIFO
- Блокираща опашка
- Пример – симулация на център за обаждания
- Стартиране на приложението
- Обобщение
- Упражнения
Стекове
- Стекове
- Тестове
- Реализация
- Пример – реализация на Undo/Redo
- Обобщение
Основно сортиране
- Важност на сортирането
- Основи на сортирането
- Разбиране на компараторите
- Операци на компаратор
- Интерфейс на компаратор
- Някои стандартни компаратори
- Естествен компаратор
- Метод за сортиране на мехурчето
- Интерфейс ListSorter
- Тестване на AbstractListSorter
- Сортиране с пряк избор
- Сортиране чрез вмъкване
- Какво е стабилност?
- Сравнение на основните алгоритми за сортиране
- CallCountringListComparator
- ListSorterCallCountingTest
- Разбиране на сравнението на алгоритми
- Обобщение
- Упражнения
Сортиране за напреднали
- Разбиране сортирането на Шел
- Разбиране на бързото сортиране
- Разбиране на съставните компаратори и стабилността
- Разбиране на сортирането чрез сливане
- Сливане
- Алгоритъм за сортиране чрез сливане
- Сравняване на сложни алгоритми за сортиране
- Обобщение
- Упражнения
Приоритетни опашки
- Разбиране за приоритетни опашки
- Проста приоритетна опашка
- Работа с приоритетни опашки
- Описание на неподредена приоритетна опашка върху списък
- Какво е приоритетна опашка върху сортиран списък?
- Какво е приоритетна опашка в подредена пирамида?
- Сравняване на реализации на приоритетна опашка
- Обобщение
- Упражнение
Двоично търсене и вмъкване
- Разбиране за двоично търсене
- Подходи към двоичното търсене
- List Searcher
- Итеративно двоично търсене
- Оценяване на работата на List Searcher
- Разбиране на двоично вмъкване
- List Inserter
- Оценяване на производителността
- Обобщение
Двоични дървета за търсене
- Разбиране за двоично дърво за търсене
- Минимална стойност
- Максимална стойност
- Наследник
- Предшественик
- Търсене
- Вмъкване
- Изтриване
- Поредно обхождане
- Обхождоне “корен ляво дясно” (КЛД)
- Обхождане “ляво дясно корен” (ЛДК)
- Балансиране
- Тестване и прилагане на двоично дърво за търсене
- Оценка на производителността на двоично дърво за търсене
- Обобщение
- Упражнения
Хеширане
- Какво е хеширане?
- Работа с хеширане
- Как работи?
- Линейно сортиране
- Работа с кофи
- Оценка на производителността
- Обобщение
- Упражнение
Множества
- Понятия за множества
- Тестване на реализациите на множества
- Списъчно множество
- Хеш-множество
- Дървовидно множество
- Обобщение
- Упражнения
Карти
- Понятие за карти
- Тестване на реализациите на карта
- Списъчна карта
- Хеш-карта
- Дървовидна карта
- Обобщение
- Упражнения
Троични дървета за търсене
- Понятие за троични дървета з търсене
- Търсене на дума
- Вмъкване на дума
- Търсене на представки
- Съпоставяне на схеми
- Практическо използване на троични дървета за търсене
- Пример за помощник за кръстословици
- Обобщение
- Упражнение
В-дървета
- Понятието В-дърво
- Практическо използване на В-дървета
- Обобщение
- Упражнения
Търсене на низове
- Основен интерфейс за търсене на низове
- Основен тестов пакет
- Алгоритъм, използващ груба сила
- Алгоритъм Бойър-Мур
- Създаване на тестовете
- Реализиране на алгоритъма
- Итератор за съвпадение на низ
- Сравняване на производителността
- Измерване на производителността
- Как се сравяват?
- Обобщение
Съпоставяне на низове
- Запознаване със Soundex
- Запознаване с разстоянието в думи на Левенщайн
- Обобщение
Изчислителна геометрия
- Бърз опреснителен курс по геометрия
- Координати и точки
- Отсечки
- Откриване на пресечната точка на две отсечки
- Наклон
- Пресичане на оста Y
- Откриване на пресечната точка
- Откриване на най-близката двойна точка
- Обобщене
- Упражнения
Прагматична оптимизация
- Къде се прилага оптимизацията?
- Понятие за профили
- Примерна програма FileSortingHelper
- Профилиране с hprof
- Профилиране с JMP
- Понятие за оптимизация
- Практическо приложение за оптимизацията
- Обобщение