Delphi - Готовые алгоритмы - Стивенс Р. - 2004.
Программирование всегда было достаточно сложной задачей. Эта книга поможет вам легко преодолеть возникающие трудности с помощью библиотеки мощных алгоритмов, полностью реализованных в исходном коде Delphi. Вы узнаете, как выбрать способ, наиболее подходящий для решения конкретной задачи, и как добиться максимальной производительности вашего приложения. Рассматриваются типичные и наихудшие случаи реализации алгоритмов, что позволит вам вовремя распознать возможные трудности и при необходимости переписать или заменить часть программы. Подробно описываются важнейшие элементы алгоритмов хранения и обработки данных (списки, стеки, очереди, деревья, сортировка, поиск, хеширование и т.д.). Приводятся не только традиционные решения, но и методы, основанные на последних достижениях объектно-ориентированного программирования.
Книга предназначена для начинающих программистов на Delphi, но благодаря четкой структуризации материала и богатой библиотеке готовых алгоритмов будет также интересна и специалистам.
Введение.
Глава 1. Основные понятия
Что такое алгоритмы.
Анализ скорости выполнения, алгоритмов
Память или время.
Оценка с точностью до порядка
Определение сложности.
Сложность рекурсивных алгоритмов
Средний и наихудший случай.
Общие функции оценки сложности.
Логарифмы
Скорость работы алгоритма в реальных условиях
Обращение к файлу подкачки.
Резюме.
Глава 2. Списки
Основные понятия о списках.
Простые списки.
Изменение размеров массивов.
Список переменного размера
Класс SimpleList.
Неупорядоченные списки.
Связанные списки.
Добавление элементов.
Удаление элементов.
Глава 3. Стеки и очереди
Стеки.
Стеки на связанных списках.
Очереди
Циклические очереди.
Очереди на основе связанных списков.
Очереди с приоритетом
Многопоточные очереди.
Резюме.
Глава 4. Массивы
Треугольные массивы
Диагональные элементы
Нерегулярные массивы
Линейное представление с указателем.
Нерегулярные связанные списки.
Динамические массивы Delphi.
Разреженные массивы.
Индексирование массива
Сильно разреженные массивы.
Резюме.
Глава 5. Рекурсия
Что такое рекурсия
Рекурсивное вычисление факториалов Анализ сложности
Рекурсивное вычисление
наибольшего общего делителя
Анализ сложности.
Рекурсивное вычисление чисел Фибоначчи
Анализ сложности.
Рекурсивное построение кривых Гильберта
Анализ сложности.
Рекурсивное построение кривых Серпинского.
Анализ сложности
Недостатки рекурсии.
Бесконечная рекурсия
Потери памяти
Необоснованное применение рекурсии.
Когда нужно использовать рекурсию.
Удаление хвостовой рекурсии
Нерекурсивное вычисление чисел Фибоначчи.
Устранение рекурсии в общем случае.
Нерекурсивное создание кривых Гильберта.
Нерекурсивное построение кривых Серпинского Резюме.
Глава 6. Деревья
Определения
Представления деревьев.
Полные узлы
Списки дочерних узлов
Представление нумерацией связей.
Полные деревья
Обход дерева.
Упорядоченные деревья
Добавлениеэлементов.
Удаление элементов.
Обход упорядоченных деревьев
Деревья со ссылками
Особенности работы.
Q-деревья.
Изменение значения MAXQTREENODES
Восьмеричные деревья.
Резюме.
Глава 7. Сбалансированные деревья
Балансировка.
AVL-деревья
Добавление узлов к AVL-дереву.
Удаление узлов из AVL-дерева.
Б-деревья.
Производительность Б-дерева.
Удаление элементов из Б-дерева
Добавление элементов в Б-дерево
Разновидности Б-дерева.
Усовершенствование Б-деревьев.
Вопросы доступа к диску
База данных на основе Б+дерева
Резюме.
Глава 8. Деревья решений
Поиск в игровых деревьях
Минимаксный перебор
Оптимизация поиска в деревьях решений
Поиск нестандартных решений
Ветви и границы.
Эвристика.
Сложные задачи
Задача о выполнимости.
Задача о разбиении
Задача поиска Гамильтонова пути.
Задача коммивояжера
Задача о пожарных депо.
Краткая характеристика сложных задач
Резюме
Глава 9. Сортировка
Общие принципы.
Таблицы указателей.
Объединение и сжатие ключей.
Пример программы
Сортировка выбором
Перемешивание
Сортировка вставкой
Вставка в связанных списках
Пузырьковая сортировка
Быстрая сортировка
Сортировка слиянием.
Пирамидальная сортировка.
Пирамиды.
Очереди с приоритетом.
Алгоритм пирамидальной сортировки
Сортировка подсчетом.
Блочная сортировка
Блочная сортировка с использованием связанных списков
Резюме
Глава 10. Поиск
Примеры программ
Полный перебор
Перебор сортированных списков.
Перебор связанных списков
Двоичный поиск.
Интерполяционный поиск.
Строковые данные.
Следящий поиск
Двоичное отслеживание и поиск
Интерполяционный следящий поиск.
Резюме.
Глава 11. Хеширование
Связывание.
Преимущества и недостатки связывания
Блоки.
Хранение хеш-таблиц на диске.
Связывание блоков.
Удаление элементов.
Преимущества и недостатки использования блоков Открытая адресация
Линейная проверка.
Квадратичная проверка
Псевдослучайная проверка
Удаление элементов.
Резюме.
Глава 12. Сетевые алгоритмы
Определения
Представления сетей
Управление узлами и связями
Обход сети
Наименьший каркас дерева,
Кратчайший путь
Расстановка меток.
Коррекция меток
Варианты поиска кратчайшего пути.
Применение алгоритмов поиска кратчайшего пути.
Максимальный поток
Сферы применения.
Резюме
Глава 13.Объектно-ориентированные методы.
Преимущества ООП.
Инкапсуляция.
Полиморфизм
Многократное использование и наследование
Парадигмы ООП.,.
Управляющие объекты
Контролирующий объект
Итератор,.
Дружественный класс.
Интерфейс
Фасад
Фабрика.
Единственный объект
Сериализация
Парадигма Модель/Вид/Контроллер Резюме.
Приложение 1. Архив примеров
Содержание архива с примерами
Аппаратные требования
Запуск примеров программ
Информация и поддержка пользователей
Приложение 2. Список примеров программ
Предметный указатель
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Delphi - Готовые алгоритмы - Стивенс Р. - fileskachat.com, быстрое и бесплатное скачивание.
Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.
Visual Basic. Готовые алгоритмы - В книге изложены важные концепции программирования, которые могут быть с успехом применены для решения многих практических задач. В предлагаемых алгоритмах используются мощные методы, такие как рекурсия, разбиение на части, динамическое распределение памяти и сетевые структуры данных, что поможет вам создавать гибкие и сложные приложения.
Подробно рассматриваются важнейшие понятия теории алгоритмов и обработки данных (списки, стеки, очереди, деревья, сортировка, поиск, хэширование и т.д.).
Книга содержит большое количество примеров, которые вы можете использовать в собственных приложениях либо вовсе без изменений, либо модифицировав их по своему усмотрению.
Предназначена в первую очередь для опытных пользователей Visual Basic, но благодаря доступности изложения и богатой библиотеке готовых алгоритмов будет интересна и начинающим программистам.
Название:
Visual Basic. Готовые алгоритмы (+ примеры)
Стивенс Р.
Издательство:
ДКМ Пресс
Год:
2000
Страниц:
377
Формат:
DJVU
Размер:
20,3 МБ
ISBN:
5-94074-001-4
Качество:
Отличное
Серия или Выпуск:
Для программистов
Введение
Глава 1. Основные понятия
Что такое алгоритм
Анализ скорости выполнения алгоритмов
Ресурсы и время
Оценка с точностью до порядка
Поиск проблемных частей алгоритма
Сложность рекурсивных алгоритмов
Наихудший и усредненный случай
Функции оценки порядка сложности
Логарифмы
Скорость работы алгоритма в реальных условиях
Обращение к файлу подкачки
Псевдоуказатели, ссылки на объекты и коллекции
Резюме
Глава 2. Списки
Основные вопросы главы
Простые списки
Коллекции
Список переменного размера
Класс SimpleList
Неупорядоченные списки
Связанные списки
Добавление элементов
Удаление элементов
Уничтожение связанного списка
Сигнальные метки
Инкапсуляция связанных списков
Доступ к ячейкам
Разновидности связанных списков
Циклические связанные списки
Проблема циклических ссылок
Двусвязанные списки
Потоки
Другие связанные структуры
Псевдоуказатели
Резюме
Глава 3- Стеки и очереди
Стеки
Множественные стеки
Очереди
Циклические очереди
Очереди на основе связанных списков
Применение коллекций в качестве очередей
Очереди с приоритетами
Многопоточные очереди
Резюме
Глава 4. Массивы
Треугольные массивы
Диагональные элементы
Нерегулярные массивы
Линейное представление с указателями
Нерегулярные связанные списки
Разреженные массивы
Индексирование массива
Очень разреженные массивы
Резюме
Глава 5. Рекурсия
Что такое рекурсия
Рекурсивное вычисление факториалов
Рекурсивное вычисление наибольшего общего делителя
Анализ времени выполнения программы
Рекурсивное вычисление чисел Фибоначчи
Анализ времени выполнения программы
Рекурсивное построение кривых Гильберта
Анализ времени выполнения программы
Рекурсивное построение кривых Серпинского
Анализ времени выполнения программы
Недостатки рекурсии
Бесконечная рекурсия
Потери памяти
Необоснованное применение рекурсии
Когда нужно использовать рекурсию
Хвостовая рекурсия
Нерекурсивное вычисление чисел Фибоначчи
Устранение рекурсии в общем случае
Нерекурсивное построение кривых Гильберта
Нерекурсивное построение кривых Серпинского
Резюме
Глава 6. Деревья
Основные термины
Представления деревьев
Полные узлы
Списки потомков
Представление нумерацией связей
Полные деревья
Обход дерева
Упорядоченные деревья
Добавление элементов
Удаление элементов
Обход упорядоченных деревьев
Деревья со ссылками
Особенности работы
Q-деревья
Изменение количества элементов в узле
Использование псевдоуказателей
Восьмеричные деревья
Резюме
Глава 7. Сбалансированные деревья
Сбалансированность дерева
АВЛ-деревья
Добавление узла
Удаление узла
Б-деревья
Производительность Б-деревьев
Вставка элементов
Удаление элементов
Разновидности Б-деревьев
Увеличение производительности Б-деревьев
Балансировка
Вопросы, связанные с обращением к диску
База данных на основе Б+дерева
Резюме
Глава 8. Деревья решений
Поиск в деревьях игры
Минимаксный поиск
Оптимизация поиска
Поиск нестандартных решений
Метод ветвей и границ
Эвристики
Сложные задачи
Задача о выполнимости
Задача о разбиении
Задача поиска Гамильтонова пути
Задача коммивояжера
Задача о пожарных депо
Краткая характеристика сложных задач
Резюме
Глава 9. Сортировка
Общие принципы
Таблицы указателей
Объединение и сжатие ключей
Примеры программ
Сортировка выбором
Перемешивание
Сортировка вставкой
Вставка в связанных списках
Пузырьковая сортировка
Быстрая сортировка
Сортировка слиянием
Пирамидальная сортировка
Пирамиды
Очереди с приоритетами
Алгоритм пирамидальной сортировки
Сортировка подсчетом
Блочная сортировка
Блочная сортировка с применением связанного списка
Блочная сортировка на основе массива
Резюме
Глава 10. Поиск
Примеры программ
Поиск методом полного перебора
Поиск в упорядоченных списках
Поиск в связанных списках
Двоичный поиск
Интерполяционный поиск
Строковые данные
Следящий поиск
Интерполяционный следящий поиск
Резюме
Глава 11. Хеширование
Связывание
Преимущества и недостатки связывания
Блоки
Хранение хеш-таблиц на диске
Связывание блоков
Удаление элементов
Преимущества и недостатки применения блоков
Открытая адресация
Линейная проверка
Квадратичная проверка
Псевдослучайная проверка
Удаление элементов
Резюме
Глава 12. Сетевые алгоритмы
Основные термины
Представления сети
Оперирование узлами и связями
Обходы сети
Наименьший каркас дерева
Кратчайший маршрут
Расстановка меток
Коррекция меток
Варианты поиска кратчайшего маршрута
Приложения, использующие метод поиска кратчайшего маршрута
Максимальный поток
Сферы применения
Резюме
Глава 13. Объектно-ориентированные методы
Преимущества ООП
Инкапсуляция
Полиморфизм
Наследование и повторное использование
Парадигмы ООП
Управляющие объекты
Контролирующий объект
Итератор
Дружественный класс
Интерфейс
Фасад
Порождающий объект
Единственный объект
Преобразование в последовательную форму
Парадигма Модель/Вид/Контроллер
Резюме
Приложение 1. Архив с примерами
Приложение 2. Список примеров программ
Алфавитный указатель
Скачать Visual Basic. Готовые алгоритмы (+ примеры)
При изучении информатики немало внимания уделяется изучению алгоритмов и их видам. Не зная основных сведений о них, нельзя написать программу или проанализировать ее работу. Изучение алгоритмов начинается еще в школьном курсе информатики. Сегодня мы рассмотрим понятие алгоритма, свойства алгоритма, виды.
Понятие
Алгоритм - это определенная последовательность действий, которая приводит к достижению того или иного результата. Составляя алгоритм, детально прописывают каждое действие исполнителя, которое в дальнейшем приведет его к решению поставленной задачи.
Довольно часто алгоритмы используют в математике для решения тех или иных задач. Так, многим известен алгоритм решения квадратных уравнений с поиском дискриминанта.
Свойства
Прежде чем рассматривать в информатике, необходимо выяснить их основные свойства.
Среди основных свойств алгоритмов необходимо выделить следующие:
- Детерминированность, то есть определенность. Заключается в том, что любой алгоритм предполагает получение определенного результата при заданных исходных.
- Результативность. Означает, что при наличии ряда исходных данных после выполнения ряда шагов будет достигнут определенный, ожидаемый результат.
- Массовость. Написанный единожды алгоритм может использоваться для решения всех задач заданного типа.
- Дискретность. Она подразумевает, что любой алгоритм можно разбить на несколько этапов, каждый из которых имеет свое назначение.
Способы записи
Вне зависимости от того, какие виды алгоритмов в информатике вы рассматриваете, существует несколько способов их записи.
- Словестный.
- Формульно-словестный.
- Графический.
- Язык алгоритма.
Наиболее часто изображают алгоритм в виде блок-схемы, используя специальные обозначения, зафиксированные ГОСТами.
Основные виды
Выделяют три основных схемы:
- Линейный алгоритм.
- Ветвящийся алгоритм, или разветвленный.
- Циклический.
Линейный
Наиболее простым в информатике считается Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».
1. Встаем, когда звенит будильник.
2. Умываемся.
3. Чистим зубы.
4. Делаем зарядку.
5. Одеваемся.
6. Кушаем.
7. Обуваемся и идем в школу.
8. Конец алгоритма.
Разветвляющийся алгоритм
Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения - в другом.
Например, возьмем следующую ситуацию - переход дороги пешеходом.
1. Подходим к светофору.
2. Смотрим на сигнал светофора.
3. Он должен быть зеленым (это условие).
4. Если условие выполняется, мы переходим дорогу.
4.1 Если нет - ждем, пока загорится зеленый.
4.2 Переходим дорогу.
5. Конец алгоритма.
Циклический алгоритм
Изучая виды алгоритмов в информатике, детально следует остановиться на Данный алгоритм предполагает участок вычислений или действий, который выполняется до выполнения определенного условия.
Возьмем простой пример. Если ряд чисел от 1 до 100. Нам необходимо найти все то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа».
1. Берем число 1.
2. Проверяем, меньше ли оно 100.
3. Если да, проверяем простое ли это число.
4. Если условие выполняется, записываем его.
5. Берем число 2.
6. Проверяем, меньше ли оно 100.
7. Проверяем, простое ли оно.
…. Берем число 8.
Проверяем, меньше ли оно 100.
Проверяем, простое ли число.
Нет, пропускаем его.
Берем число 9.
Таким образом перебираем все числа, до 100.
Как видите, шаги 1 - 4 будут повторяться некоторое число раз.
Среди циклических выделяют алгоритмы с предусловием, когда условие проверяется в начале цикла, или с постусловием, когда проверка идет в конце цикла.
Другие варианты
Алгоритм может быть и смешанным. Так, он может быть циклическим и разветвленным одновременно. При этом используются разные условия на разных отрезках алгоритма. Такие сложные структуры приеняются при написании сложных программ и игр.
Обозначения в блок-схеме
Мы с вами рассмотрели, какие виды алгоритмов есть в информатике. Но мы не рассказали о том, какие обозначения используются при их графической записи.
- Начало и конец алгоритма записываются в овальной рамке.
- Каждая команда фиксируется в прямоугольнике.
- Условие прописывается в ромбе.
- Все части алгоритма соединяются при помощи стрелок.
Выводы
Мы с вами рассмотрели тему "Алгоритмы, виды, свойства". Информатика уделяет немало времени изучению алгоритмов. Их используют при написании различных программ как для решения математических задач, так и для создания игр и различного рода приложений.
