Н.Н.Кузюрин, 2003 (Rus)
Лекции по курсу "Сложность комбинаторных алгоритмов"


ОГЛАВЛЕНИЕ

1. ЭЛЕМЕНТЫ ТЕОРИИ СЛОЖНОСТИ

1.1 Несложно о сложности. Примеры алгоритмов
    1.1.1 Примеры задач на натуральных числах
    1.1.2 Приближенные алгоритмы. Многопроцессорные расписания
    1.1.3 Примеры задач на графах. Кратчайшие пути и задача коммивояжера
    1.1.4 Задача сортировки и поиска
    1.1.5 Еще о поиске кратчайших путей
1.2 Формально об алгоритмах
    1.2.1 Машины с произвольным доступом (RAM)
    1.2.2 Машины Тьюринга и вычислимость
1.3 Сложность алгоритмов
   1.3.1 Сложность в худшем случае (Worst Case Compexity)
   1.3.2 Полиномиальные алгоритмы
   1.3.3 Полиномиальность и эффективность
1.4 Эффективность и классы сложности DTIME, DSPACE
1.5 Схемы и схемная сложность
1.6 Полиномиальные сводимости и NP-полнота
   1.6.1 Сводимость по Куку
   1.6.2 Недетерминированные алгоритмы
   1.6.3 Сводимость по Карпу


2. ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ

2.1 Жадный алгоритм в задаче о покрытии
2.2 Алгоритм Кристофидеса для метрической задачи коммивояжера
2.3 Динамическое программирование для задачи о рюкзаке
2.4 Полностью полиномиальная приближенная схема для задачи о рюкзаке


3. АНАЛИЗ СЛОЖНОСТИ В СРЕДНЕМ. ВЕРОЯТНОСТНЫЕ АЛГОРИТМЫ

3.1 Анализ сложности в среднем. Задача упаковки
3.2 Точность жадного алгоритма почти для всех исходных данных
3.3 Вероятностные алгоритмы (Лас-Вегас и Монте-Карло)
3.4 Вероятностное округление
3.5 Дерандомизация. Метод условных вероятностей


4. ПРИЛОЖЕНИЯ ТЕОРИИ СЛОЖНОСТИ

4.1 Элементы криптографии с открытым ключом
   4.1.1 Дискретный алгоритм. Обмен ключами
   4.1.2 Криптография с открытым ключом. Система RSA и ее анализ
4.2 Коммуникационная сложность


5. ГЛОССАРИЙ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

5.1 Список упражнений
5.2 Литература

В.А. Носов, 2002 (Rus)
Комбинаторика и теория графов

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


ОГЛАВЛЕНИЕ

• ГЛАВА I
  ВВЕДЕНИЕ В КОМБИНАТОРИКУ

  § 1. Множества. Отображения

  1. Множества

  2. Отображения

  3. Алгебра множеств

  4. Упражнения

  § 2. Принципы перечисления и примеры

  1. Элементарные тождества

  2. Упражнения

  § 3. Бинарные отношения

  1. Определения

  2. Операции над отношениями

  3. Свойства операций над отношениями

  4. Упражнения

  § 4. Специальные классы бинарных отношений

  1. Отношения эквивалентности

  2. Отношения толерантности

  3. Отношения частичного порядка

  4. Упражнения

  § 5. Элементы теории подстановок

  Упражнения

  § 6. Порождение сочетаний и перестановок
  
  

• ГЛАВА II
  МЕТОДЫ ПЕРЕЧИСЛЕНИЯ

  § 1. Метод включения-исключения
  § 2. Метод рекуррентных соотношений
  § 3. Производящие функции и формулы обращения
  § 4. Обращение Мебиуса
  § 5. Перманенты и их применение к перечислительным задачам

  Упражнения
  
  

• ГЛАВА III
  ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

  § 1. Основные понятия теории графов
  § 2. Эйлеровы графы
  § 3. Гамильтоновы графы
  § 4. Кратчайшие пути
  § 5. Деревья
  § 6. Планарные графы
  § 7. Раскраска графов
  § 8. Потоки в сетях

  Упражнения
  
  

• ЛИТЕРАТУРА

Д. Кнут, 2000 (Rus)
Сортировка и Поиск

ИЗБРАННЫЕ ФРАГМЕНТЫ ТРЕТЬЕГО ТОМА КНИГИ "ИСКУССТВО ПРОГРАММИРОВАНИЯ"


5 СОРТИРОВКА

5.1 Комбинаторные свойства перестановок
  5.1.1 Инверсии
  5.1.2 Перестановки мультимножества

5.2 Внутренняя сортировка
  5.2.1 Сортировка вставками
  5.2.2 Обменная сортировка
  5.2.3 Сортировка посредством выбора
  5.2.4 Сортировка слиянием
  5.2.5 Сортировка с двумя лентами
  5.2.6 Диски и барабаны


6 ПОИСК

6.1 Последовательный поиск
6.2 Сбалансированные деревья

В.П.Гладков, 1998 (Rus)
Конспект лекций по программированию для начинающих

Изложены основы программирования для студентов младших курсов специальностей АСУ, КРЭС и ЭВТ, читавшегося автором в Пермском государственном техническом университете на протяжении ряда лет. Подробно отражены методы построения алгоритмов на основе их классификации. Приведено большое количество решенных примеров и упражнений для самостоятельной работы и проверки усвоения материала. Пособие может быть использовано учителями средних учебных заведений, лицами, занимающимися самообразованием, любителями информатики

ПРЕДИСЛОВИЕ

1. ВВЕДЕНИЕ 

2. ИНФОРМАЦИЯ
    2.1. Понятие информации 
    2.2. Информационные процессы 

3. ИСПОЛНИТЕЛИ. КОМПЬЮТЕР - УНИВЕРСАЛЬНЫЙ ИСПОЛНИТЕЛЬ 
    3.1. Понятие "исполнитель. Структура компьютера 
    3.2. Работа компьютера

4. АЛГОРИТМ И ЕГО СВОЙСТВА

5. ДАННЫЕ 
    5.1. Стандартный домен integer (целый тип)
    5.2. Стандартный домен real (вещественный тип)
    5.3. Стандартный домен char (символьный тип)
    5.4. Стандартный домен string (строковый тип)
        5.4.1. Функции
        5.4.2. Процедуры
    5.5. Стандартный домен boolean (логический тип)
        5.5.1. Законы логических операций

6. ВЫРАЖЕНИЯ 

7. СТРУКТУРА ПРОГРАММ НА ЯЗЫКЕ PASCAL

8. ЛИНЕЙНЫЕ АЛГОРИТМЫ 
    8.1. Оператор ввода 
    8.2. Оператор вывода 
    8.3. Оператор присваивания 
    8.4. Примеры построения линейных алгоритмов 
    8.5. Спецификации 
    8.6. Продолжение обучения робота "Кибик" 
    8.7. Линейные алгоритмы на языке Pascal

9. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ
    9.1. Построение условий
    9.2. Высказывания и их запись на языке Pascal
    9.3. Построение ветвящихся алгоритмов 
    9.4. Таблицы решений 
        9.4.1. Построение таблиц решений 
    9.5. Задачи, приводящие к ветвящимся алгоритмам 

10. ЦИКЛЫ
    10.1. Основные понятия. Виды циклов. Общий подход к построению циклов 
    10.2. Запись циклов на языке Pascal 
    10.3. Примеры программ с циклами 
        10.3.1. Арифметические циклы 
        10.3.2. Итерационные циклы 
        10.3.3. Поисковые циклы 
    10.4. Модификации построенных алгоритмов 
        10.4.1. Модификация 1 
        10.4.2. Модификация 2 
        10.4.3. Модификация 3 
        10.4.4. Модификация 4 
        10.4.5. Модификация 5 
        10.4.6. Модификация 6 
    10.5. Задачи на построение циклов 
    10.6. Способы уяснения действий, составляющих тело цикла 
    10.7. Рекуррентные формулы 
        10.7.1. Основные понятия 
        10.7.2. Получение рекуррентных формул для последовательностей 
    10.8. Вложенные циклы 
    10.9. Стратегии ввода данных и вывода результатов 
    10.10. Переборный метод решения задач 
    10.11. Графика 

11. МЕТОДЫ РАБОТЫ С МАССИВАМИ
    11.1. Понятие массива 
    11.2. Массивы 
    11.3. Способы перебора элементов массива 
    11.4. Перебор подмассивов 
    11.5. Нелинейные схемы перебора элементов массива 
    11.6. Классы задач по обработке массивов 
        11.6.1. Решение задач первого класса 
        11.6.2. Решение задач второго класса 
        11.6.3. Решение задач третьего класса 
        11.6.4. Решение задач четвертого класса 
    11.7. Сортировка массивов 
        11.7.1. Сортировка включениями 
        11.7.2. Сортировка выбором 
        11.7.3. Сортировка обменом 
    11.8. Двумерные массивы 
    11.9. Решение задач с использованием массивов 

12. РАБОТА СО СТРОКАМИ 

13. ПРОЦЕДУРЫ И ФУНКЦИИ
    13.1. Общие понятия 
    13.2. Рекурсивные процедуры и функции

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Ростов-на-Дону, Росиия © М.Э.Абрамян, 2001 (Rus)
Оформление и подготовка к публикации Любек, ФРГ © А.С.Чигиринский, 2003
Практикум по программированию

Учебное пособие содержит 420 заданий по программированию. Все задачи имеют короткую и четкую формулировку. В отдельных задачах поддерживается инвариативность. Предназначено для преподавателей школ и вузов, школьников и студентов.

ОГЛАВЛЕНИЕ

1. СКАЛЯРНЫЕ ТИПЫ И УПРАВЛЯЮЩИЕ ОПЕРАТОРЫ
    1.1 Линейные алгоритмы 
    1.2 Логические выражения 
    1.3 Условные операторы 
    1.4 Операторы выбора 
    1.5 Операторы цикла 
    1.6 Обработка последовательностей 
    1.7 Минимумы и максимумы

2. МАССИВЫ И СТРОКИ
    2.1 Одномерные массивы 
    2.2 Двумерные массивы (матрицы) 
    2.3 Символы и строки

3. РАБОТА С ФАЙЛАМИ
    3.1 Двоичные файлы 
    3.2 Текстовые файлы

4. ПРОЦЕДУРЫ И ФУНКЦИИ 
    4.1 Обработка числовых данных 
    4.2 Массивы 
    4.3 Строки 
    4.4 Файлы 
    4.5 Простейшие рекурсивные алгоритмы 
    4.6 Разбор выражений 
    4.7 Деревья 

5. УКАЗАТЕЛИ И ДИНАМИЧЕСКИЕ СТРУКТУРЫ
    5.1 Стеки и очереди
    5.2 Двусвязные списки