Основи на алгоритмите → Обява 47446177

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

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

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

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

СЪДЪРЖАНИЕ:

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

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