Теория множеств. Конструктивная математика

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

В пособии рассмотрены различные подходы к формализации понятия алгоритм: машина Тьюринга, алгоритмы Маркова, рекурсивные функции. Пособие ориентировано на студентов 3-4 курсов математических факультетов педагогических вузов, обучающихся по специальности 050201 «Математика и информатика» и 050202 «Информатика и математика».

Учебное пособие (продолжение одноименного учебного пособия, изданного в 2004 г.) посвящено различным аспектам построения и анализа эффективных алгоритмов решения некоторых задач. Материал разбит на главы по предметным областям и по методам решения задач. Главы посвящены геометрическим методам в задачах информатики, рекурсии, динамическому программированию и структурам данных. Пособие рассчитано на студентов факультетов информатики и вычислительной техники, обучающихся по специальности 351500 Математическое обеспечение и администрирование информационных систем (дисциплина "Методы построения эффективных алгоритмов", блок ДС), очной формы обучения, а также может оказаться интересным для школьников, принимающих участие в олимпиадах по информатике.

Учебное издание содержит краткий теоретический материал по каждому из разделов дисциплины «Теория множеств», примеры решения типовых задач и задачи для самостоятельного решения.

Приведены основные понятия и факты, относящиеся к языку высказываний, языку предикатов, теории aлгоритмов, теории нечетких миожеств и нечеткой логике. Наряду с традиционными разделами математической логики изложен метод резолюций, полезный для приложений. Рассмотрены типовые задачи.

В учебно-методическом пособии по дисциплине «Теория алгоритмов» представлены разделы, традиционно изучаемые в курсе теории алгоритмов: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции и т.д. Рассмотрены вопросы интуитивного и формального определения алгоритмов, сложности и нумерации алгоритмов, алгоритмически неразрешимых проблем, конструирования машин Поста.

Пособие содержит теоретический материал, а также варианты индивидуальных и проектных заданий, связанных как с основными разделами языка программирования Python (функции, строки, списки и т. п.), так и с использованием распространенных библиотек научного программирования — Numpy, Matplotlib, Pandas. В качестве средства выполнения заданий предполагается использование среды Jupyter Notebook.

Изложен теоретический материал по разделам дискретной математики: множества, отношения, математическая логика, графы, который проиллюстрирован большим количеством примеров. Каждый раздел завершается вопросами и заданиями для самоконтроля. Приведены задания для самостоятельной работы.

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

Пособие содержит материал по элементам теории множеств, исчислению высказываний, исчислению предикатов, булевым функциям. Приведён ряд задач, дополняющих основное содержание пособия.