Все жанры Все авторы
NP=P? Алгоритмы решения NP-задач матричным методом в программе Scilab. Математическое эссе - Людмила Наумова

NP=P? Алгоритмы решения NP-задач матричным методом в программе Scilab. Математическое эссе

Страниц

15

Год

—

Книга «Алгоритмы комбинаторики в программе Scilab» имеет следующее содержание:

Введение
- Знакомство с курсом школьной математики и задачами комбинаторики
- Недостатки формул комбинаторики и необходимость алгоритмов решения
- Использование программы Scilab для нахождения решений задач комбинаторики
- Обзор основных алгоритмов и команд Scilab

Глава 1. Сущность метода, команды и типовые алгоритмы в программе Scilab 6.0.1
- Объяснение сути метода и применение команд Scilab для работы с матрицами
- Описание типовых алгоритмов решения задач комбинаторики с использованием Scilab

Глава 2. Решение NP-задач комбинаторики с помощью Scilab
- Описание особенностей NP-задач комбинаторики и их классификация
- Приведение примеров решения NP-задач комбинаторики с использованием Scilab

Заключение
- Выводы об универсальности и эффективности алгоритмов комбинаторики в программе Scilab
- Предсказание большего перехода NP-задач в класс P-задач с развитием программ и компьютеров

Книга представляет собой руководство по использованию программы Scilab для решения задач комбинаторики. Она изначально объясняет недостатки формул комбинаторики, которые дают только количество решений, но не сами решения. Затем автор показывает, как с помощью Scilab можно получить не только ответы, но и сами решения задач комбинаторики. Алгоритмы решения задач комбинаторики в программе Scilab основаны на работе с матрицами и командами Scilab. В конце книги автор делает вывод о возможности перехода NP-задач в класс P-задач с развитием программ и ростом мощности компьютеров.

Читать бесплатно онлайн NP=P? Алгоритмы решения NP-задач матричным методом в программе Scilab. Математическое эссе - Людмила Наумова

© Людмила Наумова, 2018


ISBN 978-5-4493-7193-5

Создано в интеллектуальной издательской системе Ridero

Введение

Из курса школьной математики нам все известны задачи комбинаторики, такие как задачи на перестановки, сочетания, размещения, представленные соответствующими формулами. Но эти формулы дают нам только количество решений, а не сами решения. Общих типовых алгоритмов самих решений на эти типы задач не было. Эти типы задач с большими числами можно отнести к NP задачам. Но с помощью программы Scilab раскрываются типовые алгоритмы таких задач и выдаются сами решения, и не только количество решений. Суть алгоритмов состоит в оперировании с элементами натурального ряда в строках и столбцах матрицы, а также в оперировании со строками и столбцами матрицы с помощью команд Scilab. NP- задачи, в принципе, представляют все те же задачи комбинаторики, но в больших числах. Так в одной NP- задаче могут присутствовать сразу как перестановки, так и сочетания и размещения, могут быть эти операции (сочетания, размещения, перестановки) последовательно повторяться, но уже с другими, полученными в ходе решения задачи, данными, могут быть заданы дополнительные еще какие либо условия или вычисления. Суть в том, что зная типовые алгоритмы перестановок, размещения, сочетания, эти алгоритмы можно использовать сколько угодно в одной задаче и таким образом решать NP задачи. Подчеркнем еще раз, что приведенные ниже алгоритмы дают сами решения, а не только ответы о количестве решений, хотя и их тоже дают. В больших числах решение этих задач требует большой разрешительной мощности компьютера, но алгоритмы остаются все те же. В данной книге приводятся примеры с малыми числами, но суть дела остается та же. Тем самым, автор хочет показать, что часто решение задачи лежит на поверхности, но мы иногда не можем увидеть решение под таким углом. Автор уверен, что все больше NP-задач будет переходить в разряд P- задач. Этот процесс неизбежен с развитием программ и ростом мощности компьютеров.

Глава 1. Сущность метода, команды и типовые алгоритмы в программе Scilab 6.0.1

– Сущность метода

Любое множество можно записать в виде матрицы с элементами этого множества. Сущность применяемого метода состоит из оперирования над натуральными числами (элементами множеств), применяя матричный подход, то есть оперированием элементами матриц, их столбцов и строками, а также во взаимодействиями между матрицами (множествами).

Общие типовые алгоритмы для задач комбинаторики, таких как задач на перестановки, сочетания, размещения, которые приведены ниже, применимы для NP- задач. Эти типы задач (на перестановки, сочетания, размещения) с большими числами можно отнести к NP- задачам. NP- задачи, по сути своей, представляют все те же задачи комбинаторики, но в усложненном варианте, в одной задаче могут присутствовать сразу как перестановки, так и сочетания и размещения, могут быть эти операции (сочетания, размещения, перестановки) последовательно повторяться, но уже с другими полученными в ходе решения задачи данными, могут быть заданы дополнительные еще какие либо условия или вычисления. Но с помощью программы Scilab раскрываются типовые алгоритмы таких задач и выдаются сами решения, а не только количество решений. Суть в том, что зная типовые алгоритмы перестановок, размещения, сочетания, их можно использовать сколько угодно как типовые алгоритмы в одной задаче и таким образом решать NP- задачи.

Вам может понравиться: