Основи на алгоритмите

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

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

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

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

Алекс-Софт Пъблишинг ЕООД
София, 1528
ул. Поручик Христо Топракчиев 11
cust_serv@alexsoft.net

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

• Кой трябва да чете тази книга?
• Нужни познания
• Какво ще научите?
• Как да използваме тази книга?
• Принципни положения
• Давай по-просто
• Не оптимизирайте прекалено
• Използвайте интерфейси
• Тествайте
• Проверявайте всичко
• От какво имате нужда?
• Конвенции
• Как да се използват упражненията?
• Изходен код
• Грешки
• 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
• Понятие за оптимизация
• Практическо приложение за оптимизацията
• Обобщение