Наверх


Витольд Липский, 1982 (Rus)

Комбинаторика для программистов


Введение в комбинаторику

  1. Основные понятия

  2. Функции и размещения

  3. Перестановки: разложение на циклы, знак перестановки

  4. Генерирование перестановок

  5. Подмножества множества, множества с повторениями, генерирование подмножеств множества

  6. k-элементные подмножества, биномиальные коэффициенты

  7. Генерирование k-элементных подмножеств

  8. Разбиения множества

  9. Числа Стерлинга второго и первого рода

  10. Генерирование разбиения множества

  11. Разбиения чисел

  12. Производящие функции

  13. Принцип включения и исключения

  14. Задачи


Алгоритмы на графах

  1. Машинное представление графов

  2. Поиск в глубину в графе

  3. Поиск в ширину в графе

  4. Стягивающие деревья (каркасы)

  5. Отыскание фундаментального множества циклов в графе

  6. Нахождение компонент двусвязности

  7. Эйлеровы пути

  8. Алгоритмы с возвратом

  9. Задачи


Нахождение кратчайших путей в графе

  1. Начальные понятия

  2. Кратчайшие пути от фиксированной вершины

  3. Случай неотрицательных весов - алгоритм Дейкстры

  4. Пути в бесконтурном графе

  5. Кратчайшие пути между всеми парами вершин, транзитивное замыкание отношения

  6. Задачи

Потоки в сетях и родственные задачи

  1. Максимальный поток в сети

  2. Алгоритм построения максимального потока

  3. Наибольшие паросочетания в двудольных графах

  4. Системы различных представителей

  5. Разложение на цепи

  6. Задачи

Матроиды

  1. Жадные алгоритмы решения оптимизационных задач

  2. Матроиды и их основные свойства

  3. Теорема Радо-Эдмондса

  4. Матричные матроиды

  5. Графовые матроиды

  6. Матроиды трансверсалей

  7. Задачи



Наверх


А.Д.Плотников, 2003 (Rus)

Элементы математической логики

  1. Общие сведения о математической логике

  2. Понятия простого и сложного высказывания

  3. Булевы функции

  4. Свойства булевых функций

  5. Классы булевых функций

  6. Функционально полные системы

  7. Дизъюнктивная нормальная форма

  8. Конъюнктивная нормальная форма

  9. Способы задания булевых функций

  10. Задача ВЫПОЛНИМОСТЬ

  11. Предикаты

  12. Построение математических моделей

    1. Пример 1. Схема управления освещением

    2. Пример 2. Сумматор последовательного действия

    3. Пример 3. Логическая модель гамильтоновости графа

  13. Реализация математических моделей



Наверх

   
  Н.Кристофидес
(Rus)
  Теория графов. Алгоритмический подход


Предисловие

Глава 1. Введение

  1. Графы. Определение

  2. Пути и маршруты

  3. Петли, ориентированные циклы и циклы

  4. Степени вершины

  5. Подграфы

  6. Типы графов

  7. Сильно связные графы и компоненты графа

  8. Матричные представления

  9. Задачи

  10. Список литературы


Глава 2. Достижимость и связность

  1. Введение

  2. Матрица достижимостей и контрадостижимости

  3. Нахождение сильных компонент

  4. Базы

  5. Задачи, связанные с ограниченной достижимостью

  6. Задачи

  7. Список литературы


Глава 3. Независимые и доминирующие множества. Задача о покрывающих множествах

  1. Введение

  2. Независимые множества

  3. Домминирующие множества

  4. Задача о наименьшем покрытии

  5. Приложения задачи о покрытии

  6. Задачи

  7. Список литературы

 

Глава 4. Раскраски

  1. Введение

  2. Некоторые теоремы и оценки, относящиеся к хроматическим числам

  3. Точные алгоритмы раскраски

  4. Приближенные алгоритмы раскрашивания

  5. Обобщения и приложения

  6. Задачи

  7. Список литературы


Глава 5. Размещение центров

  1. Введение

  2. Разделения

  3. Центр и радиус

  4. Абсолютный центр

  5. Алгоритмы нахождения абсолютных центров

  6. Кратные центры (р-центры)

  7. Абсолютные р-центры

  8. Алгоритм нахождения абсолютных р-центров

  9. Задачи

  10. Список литературы


Глава 6. Размещение медиан на графе

  1. Введение

  2. Медиана графа

  3. Кратные медианы (р-медианы) графа

  4. Обобщенная р-медиана графа

  5. Методы решения задач о р-медиане

  6. Задачи

  7. Список литературы


Глава 7. Деревья

  1. Введение

  2. Построение всех остовных деревьев графа

  3. Кратчайший остов (SST) графа

  4. Задача Штейнера

  5. Задачи

  6. Список литературы


Глава 8. Кратчайшие пути

  1. Введение

  2. Кратчайший путь между двумя заданными вершинами s и t

  3. Кратчайшие пути между всеми парами вершин

  4. Обнаружение циклов отрицательного веса

  5. Нахождение К кратчайших путей между двумя заданными вершинами

  6. Кратчайший путь между двумя заданными вершинами в ориентированном ациклическом графе

  7. Задачи, близкие к задачи о кратчайшем пути

  8. Задачи

  9. Список литературы


Глава 9. Циклы, разрезы и задача Эйлера

  1. Введение

  2. Цикломатическое число и фундаментальные циклы

  3. Разрезы

  4. Матрицы циклов и разрезов

  5. Эйлеровы циклы и задача китайского почтальона

  6. Задачи

  7. Список литературы


Глава 10. Гамильтоновы циклы, цепи и задача коммивояжера

  1. Введение

    ЧАСТЬ 1

  2. Гамильтоновы циклы в графе

  3. Сравнение методов поиска гамильтоновых циклов

  4. Простая задача планирования

    ЧАСТЬ 2

  5. Задача коммивояжера

  6. Задача коммивояжера и задача о кратчайшем остове

  7. Задача коммивояжера и задача о назначениях

  8. Задачи

  9. Список литературы

  10. Приложение


Глава 11. Потоки в сетях

  1. Введение

  2. Основная задача о максимальном потоке (от s к t)

  3. Простые варианты задачи о максимальном потоке (от s к t)

  4. Максимальный поток между каждой парой вершин

  5. Поток минимальной стоимости от s к t

  6. Потоки в графах с выигрышами

  7. Задачи

  8. Список литературы

 

Глава 12. Паросочетания, транспортная задача и задача о назначениях

  1. Введение

  2. Наибольшие паросочетания

  3. Максимальные паросочетания

  4. Задача о назначениях

  5. Общая задача построения остовного подграфа с предписанными степенями

  6. Задачи о покрытии

  7. Задачи

  8. Список литературы

 

Приложение 1. Методы поиска, использующие дерево решений.

  1. Принцип поиска, использующий дерево решений

  2. Некоторые примеры ветвления

  3. Типы поиска, использующего дерево решений

  4. Применение границ

  5. Функции ветвления

Предметный указатель



Наверх


Томас Ниман
, 1998 (Rus)
Сортировка и поиск: Рецептурный справочник


Оглавление

  1. Введение

  2. Сортировка

    1. Сортировка вставками

    2. Сортировка Шелла

    3. Быстрая сортировка

    4. Сравнение методов

  3. Словари

    1. Хеш-таблицы

    2. Поиск в бинарных деревьях

    3. Красно-черные деревья

    4. Разделенные списки

    5. Сравнение методов

  4. Тексты программ

    1. Коды для сортировки вставками

    2. Коды для сортировки Шелла

    3. Коды для быстрого поиска (функции Quicksort)

    4. Коды для стандартной реализации быстрого поиска

    5. Коды для хеш-таблиц

    6. Коды для бинарных деревьев

    7. Коды для красно-черных деревьев

    8. Коды для разделенных списков

  5. Литература

  6. Словарь



Наверх


В.Д.Далека, А.С.Деревянко, О.Г.Кравец, Л.Е.Тимановская, 2000
(Rus)
Моделирование и структуры данных

Оглавление
Предисловие к электронному изданию

Введение

1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
1.1. Понятие структур данных и алгоритмов
1.2. Информация и ее представление в памяти
   1.2.1. Природа информации
   1.2.2. Хранение информации
1.3. Системы счисления
   1.3.1. Непозиционные системы счисления
   1.3.2. Позиционные системы счисления
   1.3.3. Изображение чисел в позиционной системе счисления
   1.3.4. Перевод чисел из одной системы счисления в другую
1.4. Классификация структур данных
1.5. Операции над структурами данных
1.6. Структурность данных и технология программирования


2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ
2.1. Числовые типы
   2.1.1. Целые типы
   2.1.2. Вещественные типы
   2.1.3. Десятичные типы
   2.1.4. Операции над числовыми типами
2.2. Битовые типы
2.3. Логический тип
2.4. Символьный тип
2.5. Перечислимый тип
2.6. Интервальный тип
2.7. Указатели
   2.7.1. Физическая структура указателя
   2.7.2. Представление указателей в языках программирования
   2.7.3. Операции над указателями


3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
3.1. Векторы
3.2. Массивы
   3.2.1. Логическая структура
   3.2.2. Физическая структура
   3.2.3. Операции
   3.2.4. Адресация элементов с помощью векторов Айлиффа
   3.2.5. Специальные массивы
3.3. Множества
   3.3.1. Числовые множества
   3.3.2. Символьные множества
   3.3.3. Множество из элементов перечислимого типа
   3.3.4. Множество от интервального типа
   3.3.5. Операции над множествами
3.4. Записи
   3.4.1. Логическое и машинное представление записей
   3.4.2. Операции над записями
3.5. Записи с вариантами
3.6. Таблицы
3.7. Операции логического уровня над статическими структурами. Поиск
   3.7.1. Последовательный или линейный поиск
   3.7.2. Бинарный поиск
3.8. Операции логического уровня над статическими структурами. Сортировка
   3.8.1. Сортировки выборкой
   3.8.2. Сортировки включением
   3.8.3. Сортировки распределением
   3.8.4. Сортировки слиянием


4. ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
4.1. Характерные особенности полустатических структур
4.2. Стеки
   4.2.1. Логическая структура стека
   4.2.2. Машинное представление стека и реализация операций
   4.2.3. Стеки в вычислительных системах
4.3. Очереди FIFO
   4.3.1. Логическая структура очереди
   4.3.2. Машинное представление очереди FIFO и реализация операций
   4.3.3. Очереди с приоритетами
   4.3.4. Очереди в вычислительных системах
4.4. Деки 
   4.4.1. Логическая структура дека
   4.4.2. Деки в вычислительных системах
4.5. Строки
   4.5.1. Логическая структура строки
   4.5.2. Операции над строками
   4.5.3. Представление строк в памяти


5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ
5.1. Связное представление данных в памяти
5.2. Связные линейные списки
   5.2.1. Машинное представление связных линейных списков
   5.2.2. Реализация операций над связными линейными списками
   5.2.3. Применение линейных списков
5.3. Мультисписки
5.4. Нелинейные разветвленные списки
   5.4.1. Основные понятия
   5.4.2. Представление списковых структур в памяти
   5.4.3. Операции обработки списков
5.5. Язык программирования LISP
5.6. Управление динамически выделяемой памятью


6. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ
6.1.Графы
   6.1.1. Логическая структура, определения
   6.1.2. Машинное представление оpгpафов
6.2. Деревья
   6.2.1. Основные определения
   6.2.2. Логическое представление и изображение деревьев
   6.2.3. Бинарные деревья
   6.2.4. Представление любого дерева, леса бинарными деревьями
   6.2.5. Машинное представление деревьев в памяти ЭВМ
   6.2.6. Основные операции над деревьями
   6.2.7. Приложения деревьев
   6.2.8 Деревья Хаффмена (деревья минимального кодирования)
   6.2.9 Деревья при работе с арифметическими выражениями
   6.2.10 Формирование таблиц символов
   6.2.11 Сбалансированные деревья

ЛИТЕРАТУРА