Главная » Просмотр файлов » 8_Теория алгоритмов.

8_Теория алгоритмов. (1019129), страница 5

Файл №1019129 8_Теория алгоритмов. (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004) 5 страница8_Теория алгоритмов. (1019129) страница 52017-07-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Редукция — настолько мощная вещь, что если любую из NP-полных задач удастся свести к задаче класса Р, то и все NP задачи получат полиномиальное решение. До сих пор ни одна из попыток построить такое сведение не удалась.

Типичные NP задачи

Каждая из задач, которые мы будем обсуждать, является либо опти­мизационной, либо задачей о принятии решения. Целью оптимизацион­ной задачи обычно является конкретный результат, представляющий собой минимальное или максимальное значение. В задаче о принятии решения обычно задается некоторое пограничное значение, и нас ин­тересует, существует ли решение, большее (и задачах максимизации) или меньшее (в задачах минимизации) указанной границы. Ответом в задачах оптимизации служит полученный конкретный результат, а в задачах о принятии решений — «да» или «нет».

Ранее мы занимались оптимизационным вариантом задачи о комми­вояжере. Это задача минимизации, и нас интересовал путь минималь­ной стоимости. В варианте принятия решения мы могли бы спросить, существует ли путь коммивояжера со стоимостью, меньшей заданной константы С. Ясно, что ответ в задаче о принятии решения зависит от выбранной границы. Если эта граница очень велика (например, она превышает суммарную стоимость всех дорог), то ответ «да» получить несложно. Если эта граница чересчур мала (например, она меньше сто­имости дороги между любыми двумя городами), то ответ «нет» также дается легко. В остальных промежуточных случаях время поиска от­вета очень велико и сравнимо со временем решения оптимизационной задачи. Поэтому мы будем говорить вперемешку о задачах оптимиза­ции и принятия решений, используя ту из них, которая точнее отвечает нашим текущим целям.

В следующих нескольких разделах мы опишем еще шесть NP за­дач — как в оптимизационном варианте, так и в варианте принятия решения.

Раскраска графа

Как мы уже говорили, граф G = (V, Е) представляет собой набор вершин, или узлов, V и набор ребер Е соединяющих вершины по­парно. Здесь мы будем заниматься только неориентированными графа­ми. Вершины графа можно раскрасить в разные цвета, которые обычно обозначаются целыми числами. Нас интересуют такие раскраски, в ко­торых концы каждого ребра окрашены разными цветами. Очевидно, что в графе с N вершинами можно покрасить вершины в N различных цветов, но можно ли обойтись меньшим количеством цветов? В задаче оптимизации нас интересует минимальное число цветов, необходимых для раскраски вершин графа. В задаче принятия решения нас интере­сует, можно ли раскрасить вершины в С или менее цветов.

У задачи о раскраске графа есть практические приложения. Если каждая вершина графа обозначает читаемый в колледже курс, и вер­шины соединяются ребром, если есть студент, слушающий оба курса, то получается весьма сложный граф. Если предположить, что каждый студент слушает 5 курсов, то на студента приходится 10 ребер. Пред­положим, что на 3500 студентов приходится 500 курсов. Тогда у полу­чившегося графа будет 500 вершин и 35 000 ребер. Если на экзамены отведено 20 дней, то это означает, что вершины графа нужно раскра­сить в 20 цветов, чтобы ни у одного студента не приходилось по два экзамена в день.

Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, поэтому разработка бесконфликтного расписания за разум­ное время невозможна. Кроме того при планировании экзаменов обыч­но требуется, чтобы у студента было не больше двух экзаменов в день, а экзамены по различным частям курсам назначаются в один день. Оче­видно, что разработка «совершенного» плана экзаменов невозможна, и поэтому необходима другая техника для получения по крайней мере неплохих планов.

Раскладка по ящикам

Пусть у нас есть несколько ящиков единичной емкости и набор объ­ектов различных размеров . В задаче оптимизации нас ин­тересует наименьшее количество ящиков, необходимое для раскладки всех объектов, а в задаче принятия решения — можно ли упаковать все объекты в В или менее ящиков.

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

Упаковка рюкзака

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

Эта задача возникает при выборе стратегии вложения денег: объемом здесь является объем различных вложений стоимостью - предполагаемая величина дохода, а объем рюкзака определяется размером планируемых капиталовложений.

Задача о суммах элементов подмножеств

Пусть у нас есть множество объектов различных размеров и некоторая положительная верхняя граница L. В задаче оптимиза­ции нам необходимо найти набор объектов, сумма размеров которых наиболее близка к L и не превышает этой верхней границы. В задаче принятия решения нужно установить, существует ли набор объектов с суммой размеров L. Это упрощенная версия задачи об упаковке рюк­зака.

Задача об истинности КНФ-выражения

Конъюнктивная нормальная форма (КНФ) представляет собой по­следовательность булевских выражений, связанных между собой опера­торами AND (обозначаемыми ), причем каждое выражение является мономом от булевских переменных или их отрицаний, связанных опе­раторами OR (которые обозначаются через ). Вот пример булевского выражения в конъюнктивной нормальной форме (отрицание обознача­ется чертой над именем переменной):

.

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

Задача планирования работ

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

8.8 Вопросы для самопроверки.

  1. Что такое алгоритм?

  2. Перечислите основные свойства алгоритмов.

  3. Назовите универсальные алгоритмические модели.

  4. Дайте определение примитивно-рекурсивных функций.

  5. Дайте определение частично рекурсивных и общерекурсивных функций.

  6. Дайте определение машины Тьюринга.

  7. Дайте определение и приведите примеры полиномиальных алгоритмов.

  8. В чем выражается вычислительная сложность алгоритмов?

  9. Какая задача считается труднорешаемой?

  10. Что означает термин NP- полная задача?

9. ЗАДАЧИ И УПРАЖНЕНИЯ.

  1. Доказать, что числовых булевых функций от n аргументов равно .

  2. Проверить справедливость равенства .

  3. Доказать справедливость равенства .

  4. Доказать справедливость равенства .

  5. Установить, является ли самодвойственной функция эквивалентности.

  6. Привести пример монотонной функции, которая бы была линейной.

  7. Привести пример самодвойственной функции, которая бы одновременно была линейной.

  8. Доказать, что функция Шеффера и Вебба не являются ни линейными, ни монотонными, ни самодвойственными.

  9. Определить число самодвойственных функций, зависящих от n аргументов.

  10. Доказать полноту системы булевых функций, состоящей из дизъюнкции, константы 0 и эквивалентности. Образует ли эта система базис.

  11. Образует ли базис система булевых функций, состоящая из импликации и константы 0?

  12. Установить является ли полной система, состоящая из дизъюнкции, импликации и конъюнкции.

  13. Какая система из одной 2-местной функции является полной? Найти все такие системы.

  14. Построить формулу от трех переменных, которая принимает такое же значение как большинство переменных.

  15. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~ .

  1. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

  1. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

~

~

  1. Доказать эквивалентности и указать законы алгебры логики, соответствующие им:

~

Характеристики

Тип файла
Документ
Размер
481 Kb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6375
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее