Опубликован: 08.11.2006 | Уровень: специалист | Доступ: платный | ВУЗ: Новосибирский Государственный Университет
Курс начинается с азов комбинаторики и охватывает все основные алгоритмы, их анализ и реализацию на языках программирования, а так же рассматриваются алгоритмы на графах с точки зрения комбинаторных методов их реализации и анализа.
Курс описывает различные способы представлений конечных последовательностей и операций над ними; множества и мультимножества; производящие функции и рекуррентные соотношения; абстрактные структуры данных; алгоритмы рекуррентных соотношений; комбинаторные задачи теории информации; алгоритмы на абстрактных структурах данных; различные типы поисков (последовательный, логарифмический в статических и динамических таблицах, бинарный, по сбалансированным сильно ветвящимся деревьям); все виды сортировок (внутренняя, вставка, обменная сортировка, выбор, распределяющая сортировка, цифровая распределяющая сортировка, частичная сортировка-выбор, частичная сортировка-слияние); алгоритмы на графах Дейкстры и алгоритм Флойда. В конце курса приводится программная реализация на языках программирования Паскаль, Си, С++ классических комбинаторных алгоритмов.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
28 минут
Комбинаторные вычисления
Введение. Проблема представления: коды, сохраняющие разности. Классы алгоритмов. Анализ алгоритмов. Программа.
Оглавление
    -
    Тест 1
    9 минут
    -
    Лекция 2
    32 минуты
    Целые и последовательности (последовательное распределение)
    Введение. Целые. Последовательности. Различные способы представлений конечных последовательностей (или начальных сегментов бесконечных последовательностей) и операции над ними.
    Оглавление
      -
      Тест 2
      9 минут
      -
      Лекция 3
      23 минуты
      Последовательности (связанное распределение, стеки и очереди)
      Связанное распределение. Разновидности связанных списков. Стеки и очередь. Задачи. Программы.
      Оглавление
        -
        Тест 3
        9 минут
        -
        Лекция 4
        23 минуты
        Последовательности (деревья)
        Деревья. Представления. Прохождения. Длина путей. Задача. Программа.
        Оглавление
          -
          Тест 4
          9 минут
          -
          Лекция 5
          36 минут
          Комбинаторика разбиений
          Введение. Задачи. Разные статистики. Деревья и перестановки из n элементов. Число сочетаний Cmn. Задачи на разбиение чисел. Комбинаторные задачи теории информации.
          Оглавление
            -
            Тест 5
            9 минут
            -
            Лекция 6
            34 минуты
            Последовательности (множества и мультимножества)
            Множества и мультимножества. Формула включений и исключений. Решето Эратосфена. Примеры программ.
            Оглавление
              -
              Тест 6
              9 минут
              -
              Лекция 7
              42 минуты
              Рекуррентные соотношения
              Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".
              Оглавление
                -
                Тест 7
                9 минут
                -
                Лекция 8
                34 минуты
                Алгоритмы рекуррентных соотношений
                Решение рекуррентных соотношений. Линейные рекуррентные соотношения с постоянными коэффициентами. Случай равных корней характеристического уравнения. Производящие функции.
                Оглавление
                  -
                  Тест 8
                  9 минут
                  -
                  Лекция 9
                  30 минут
                  Комбинаторика и ряды
                  Введение. Деление многочленов. Алгебраические дроби и степенные ряды. Действия над степенными рядами.
                  Оглавление
                    -
                    Тест 9
                    9 минут
                    -
                    Лекция 10
                    26 минут
                    Производящие функции и рекуррентные соотношения
                    Применение степенных рядов для доказательства тождеств. Производящие функции. Бином Ньютона. Ряд Ньютона. Производящие функции и рекуррентные соотношения. О едином нелинейном рекуррентном соотношении.
                    Оглавление
                      -
                      Тест 10
                      9 минут
                      -
                      Лекция 11
                      24 минуты
                      Алгоритмы на абстрактных структурах данных
                      Введение. Стеки. Очереди. Связанные списки. Двоичные деревья.
                      Оглавление
                        -
                        Тест 11
                        9 минут
                        -
                        Лекция 12
                        51 минута
                        Что такое граф? Определения и примеры
                        Введение. Представления. Связность и расстояние. Остовные деревья. Клики. Изоморфизм. Планарность.
                        Оглавление
                          -
                          Тест 12
                          9 минут
                          -
                          Лекция 13
                          1 час 3 минуты
                          Поиск
                          Введение. Поиск и другие операции над таблицами. Последовательный поиск. Логарифмический поиск в статических таблицах. Бинарный поиск. Оптимальные деревья бинарного поиска. Логарифмический поиск в динамических таблицах. Сбалансированные сильно ветвящиеся деревья.
                          Оглавление
                            -
                            Тест 13
                            9 минут
                            -
                            Лекция 14
                            30 минут
                            Сортировка (часть 1)
                            Введение. Внутренняя сортировка. Вставка. Обменная сортировка.
                            Оглавление
                              -
                              Тест 14
                              9 минут
                              -
                              Лекция 15
                              34 минуты
                              Сортировка (часть 2)
                              Выбор. Распределяющая сортировка. Цифровая распределяющая сортировка. Внешняя сортировка. Частичная сортировка. Частичная сортировка (выбор). Частичная сортировка (слияние).
                              Оглавление
                                -
                                Тест 15
                                9 минут
                                -
                                Лекция 16
                                27 минут
                                Алгоритмы на графах
                                Поиск в глубину. Алгоритм Дейкстры нахождения кратчайшего пути. Алгоритм Флойда нахождения кратчайших путей между парами вершин. Программы.
                                Оглавление
                                  -
                                  Тест 16
                                  9 минут
                                  -
                                  Лекция 17
                                  46 минут
                                  Калейдоскоп из комбинаторных алгоритмов
                                  Автоматическое построение лабиринтов. Бинарное дерево. Задача о восьми ферзях. Сортировки. Задача о назначениях (задачи выбора). Ханойская башня.
                                  Оглавление
                                    -
                                    Тест 17
                                    9 минут
                                    -
                                    5 часов
                                    -
                                    Денис Хажиев
                                    Денис Хажиев
                                    Россия
                                    Замир Ашурбеков
                                    Замир Ашурбеков
                                    Россия