LITMIR.BIZ

В первой части дается введение в теорию алгоритмов (часто называемую также теорией вычислимых функций или просто теорией вычислимости). Намечаются разные варианты её построения, основанные на использовании теории рекурсивных функций, машин Тьюринга, Поста и Минского, бесконечного абака, алгорифмов Маркова и экзотического языка Фрактран, предложенного Конвеем. Приводятся классические примеры алгоритмически неразрешимых проблем. Во второй части излагаются основы теории NP-полных задач. Доказывается NP-полнота ряда классических комбинаторных проблем переборного характера, таких как проблема выполнимости логических формул, проблемы коммивояжера, упаковки рюкзака, размена монет, поиска минимального покрытия и максимальной клики и др. Рассматриваются точные и приближенные алгоритмы для решения этих задач. В конце каждой части приводится список задач, дополняющих ее содержание. К некоторым из них даны указания к решению. В основу книги положен семестровый курс, читавшийся автором на факультете математики и компьютерных наук Бакинского филиала МГУ им. М. В. Ломоносова.

Подробнее

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

Подробнее

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

Подробнее

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

Подробнее

В книге собраны задачи Московских математических олимпиад 1981—1992 г. с ответами, указаниями и решениями. Решения изложены с такой степенью подробности и обоснованности, чтобы их чтение и понимание без использования дополнительной литературы было доступно как можно более широкому кругу любителей красивых математических задач. Помещённый в приложении путеводитель призван облегчить поиск задач по заданной теме или методу решения. Все задачи в том или ином смысле нестандартные, их самостоятельное решение помимо владения общеобразовательным материалом требует также смекалки, сообразительности, а иногда и многочасовых размышлений. Книга предназначена для учителей математики, руководителей кружков, школьников старших классов, студентов математических и педагогических специальностей и направлений подготовки.

Подробнее

В учебном пособии (2-е изд. – 2002 г.) впервые в отечественной литературе рассматривается связь вопросов арифметики с современными проблемами кибернетики. Книга представляет собой сборник задач по арифметике и теории сложности арифметических алгоритмов и позволяет получить систематические знания в этих областях математики. Для студентов университетов, педагогических вузов и вузов с углубленным изучением математики.

Подробнее