Ахо А., Хопкрофт Джон, Ульман Джефрі - Структури даних та алгоритми

  У книзі «Структури даних і алгоритми» докладно розглянуті структури даних і алгоритми, які є фундаментом сучасної методиології розробки програм.

Показані різноманітні реалізації абстрактних типів даних, починаючи від стандартних списків, стеків, чередів і закінчуючи безліччю та показами, які використовуються для неформального опису та реалізації алгоритмів.

Два розділи книги «Структури даних і алгоритми» присвячені методам аналізу та побудови алгоритмів; наведено та досліджено безліч різних алгоритмів для роботи з графами, внутрішнього та зовнішнього сортування, керування пам'яттю.

Книга «Структури даних і алгоритми» не вимагає від читача спеціальної підготовки, тільки передбачає його знайомство з будь-якими мовами програмування високого рівня, як-от Pascal.

Водночас вона буде корисною фахівцям із розроблення програм і алгоритмів і може бути використана як навчальний посібник для студентів і аспірантів, що спеціалізуються в галузі комп'ютерних наук.

 

     ОГЛАВЛЕННЯ КНИГИ:

Представлення  

Глава 1. Побудова та аналіз алгоритмів 
Глава 2. Основні абстрактні типи даних 
Глава 3. Дерева  
Глава 4. Основні оператори множників 
Глава 5. Спеціальні методи представлення множників 
Глава 6. Орієнтовані графи 
Глава 7. Неорієнтовані графи 
Глава 8. Сортування 
Глава 9. Методи аналізу алгоритмів 
Глава 10. Методи розроблення алгоритмів 
Глава 11. Структури даних і алгоритми для зовнішньої пам'яті 
Глава 12. Керування пам'яттю 
Список літератури 
Предметний покажчик 

 

 

Представлення

Ця книга являє собою опис структур даних і алгоритмів, які є фундаментом сучасного комп'ютерного програмування. Основу цієї книги становлять перші шість розділів нашої раніше виданої книги The Design and Analysis of Computer Algorithms . Ми розширили її вміст, ввімкнувши матеріал за алгоритмами зовнішнього зберігання й керування пам'яттю. Як і попередня, ця книга може скласти основу навчального курсу за структурами даних і алгоритмів. Ми непотрібна від читача спеціальної підготовки, тільки передбачаємо його знайомство з будь-якими мовами програмування високого рівня, як-от Pascal.

Ми спробували освітлити структури даних і алгоритми в ширшому контексті вирішення завдань із використанням обчислювальної техніки, а також використовували абстрактні типи даних для неформального опису та реалізації алгоритмів. І хоча сьогодні абстрактні типи даних тільки починають застосовувати у сучасних мовах програмування, автори вважають, що вони є корисним інструментом під час розроблення програм незалежно від мови програмування, що застосовується.

Ми також постійно підкреслюємо та впроваджуємо ідею обчислення й оцінки часу виконання алгоритмів (часоную складність алгоритмів) як складник процесу комп'ютерного розв'язання завдань. У цьому відбивається наша надія на те, що програмісти усвідомлюють, що під час виконання завдань прогресивно великих розмірів особливе значення має тимчасовіая складність обраного алгоритму, а не можливості нових поколінь апаратних засобів.

Образ алгоритмів

Ми використовуємо мову Pascal для представлення описуваних алгоритмів і структур даних просто тому, що це широко відома мова програмування. На початку книги алгоритми часто будуть представлені як в абстрактній формі, так і мовою Pascal. Це зроблено для того, щоб показати весь спектр проблем під час виконання практичних завдань: від проблеми формулювання завдання до проблем, що виникають під час виконання завершеної програми. Алгоритми, які ми представляємо, можна реалізувати будь-якими мовами програмування високого рівня.

Вміст книги

На чолі 1 містяться вступні зауваження й обговорюються реалізації процесу вихідне завдання — готова програма та роль абстрактних типів даних у цьому процесі. Тут також можна познайомитися з математичним апаратом, необхідним для оцінювання часу виконання алгоритмів.

На чолі 2 розглядаються традиційні структури списків, стеків і черг, а також зображення, які є абстрактним типом даних, заснованим на математичному поняттю функції. На чолі 3 вводяться дерева та основні структури даних, які ефективно підтримують різні оператори, що виконують над деревами.

У розділах 4, 5 розглянута велика кількість абстрактних типів даних, що ґрунтуються на математичній моделі множників. Досить глибоко досліджені словники та чергові з пріоритетами. Розглянуті стандартні реалізації цих абстрактних типів даних, як-от хеш-таблиці, двоїчні дерева пошуку, частково впорядковані дерева, 2-3 дерева та ін. Більш складний матеріал поміщений у розділ 5.

Глави 6, 7 містять матеріал, що належить до графів; орієнтовані графи розглянуті в розділі 6, а неорієнтовані — на чолі 7. Ці розділи починають розділ книги, який більше присвячений алгоритмам, ніж структурам даних, хоча ми й далі обговорювати основні структури даних, які підходять для представлення графів. У цих розділах представлена велика кількість алгоритмів для роботи з графами, включно з алгоритмами пошуку в глибину, перебування мінімального остьового дерева, найкоротшими шляхів і максимальними паросочепленнями.

На чолі 8 розглянуті основні алгоритми внутрішнього сортування: швидке сортування, пірамідальне сортування, "кишенькове" сортування, а також простіші (і менш ефективні) методи, наприклад, метод сортування вставками. Наприкінці розділу описані алгоритми з лінійним часом виконання для перебування медіан та інших порядкових статистик.

На чолі 9 обговорюються асимптотичні методи аналізу рекурсивних програм. Тут, звичайно ж, розглянуті методи вирішення рекуратних співвідношень.

На чолі 10 порівняно коротко (без глибокого аналізу) розглянуті методи розроблення алгоритмів, включно з методами декомпозиції, динамічним програмуванням, алгоритмами локального пошуку та різними формами організації дерев пошуку.

Останні два розділи присвячені організації зовнішнього зберігання й керуванню пам'яттю. Глава 11 охоплює методи зовнішнього сортування й організацію зовнішнього зберігання даних, включно з В-дерев'я та індексними структурами.

Матеріал із керування пам'яттю, що міститься в розділі 12, умовно можна розбити на чотири частини, залежно від того, чи є блоки пам'яті фіксованої або змінної довжини, а також від того, явно чи неявно здійснюється очищення пам'яті.

Матеріал цієї книги автори використовували в програмілекційних курсів за структурами даних і алгоритмами в Колумбійському, Корнельському та Станфордському університетів як для студентів, так і для аспірантів. Наприклад, попередньою версією цієї книги використовували в Станфордському університеті як основу 10-тижневого курсу з структур даних для студентів першого року навчання. Цей курс містить матеріал розділів 1–4, 9, 10, 12 і частково з розділів 5–7.

Вправи

Наприкінці кожного розділу наведено багато вправ різного ступеня складності. За допомогою багатьох із них можна просто перевірити засвоєння викладеного матеріалу. Деякі вправи вимагають додаткових зусиль і роздумів, вони позначені однією зіркою. Вправи, позначені двома зірочками, розраховані на студентів старших курсів і аспірантів. Бібліографічні примітки наприкінці кожного розділу пропонують посилання на додаткову літературу.

---

Про виробника