🗊Презентация АиФП 6. Ограничение мощи алгориитмов

Нажмите для полного просмотра!
АиФП 6. Ограничение мощи алгориитмов, слайд №1АиФП 6. Ограничение мощи алгориитмов, слайд №2АиФП 6. Ограничение мощи алгориитмов, слайд №3АиФП 6. Ограничение мощи алгориитмов, слайд №4АиФП 6. Ограничение мощи алгориитмов, слайд №5АиФП 6. Ограничение мощи алгориитмов, слайд №6АиФП 6. Ограничение мощи алгориитмов, слайд №7АиФП 6. Ограничение мощи алгориитмов, слайд №8АиФП 6. Ограничение мощи алгориитмов, слайд №9АиФП 6. Ограничение мощи алгориитмов, слайд №10АиФП 6. Ограничение мощи алгориитмов, слайд №11АиФП 6. Ограничение мощи алгориитмов, слайд №12АиФП 6. Ограничение мощи алгориитмов, слайд №13АиФП 6. Ограничение мощи алгориитмов, слайд №14АиФП 6. Ограничение мощи алгориитмов, слайд №15АиФП 6. Ограничение мощи алгориитмов, слайд №16АиФП 6. Ограничение мощи алгориитмов, слайд №17АиФП 6. Ограничение мощи алгориитмов, слайд №18АиФП 6. Ограничение мощи алгориитмов, слайд №19АиФП 6. Ограничение мощи алгориитмов, слайд №20АиФП 6. Ограничение мощи алгориитмов, слайд №21АиФП 6. Ограничение мощи алгориитмов, слайд №22АиФП 6. Ограничение мощи алгориитмов, слайд №23АиФП 6. Ограничение мощи алгориитмов, слайд №24АиФП 6. Ограничение мощи алгориитмов, слайд №25АиФП 6. Ограничение мощи алгориитмов, слайд №26АиФП 6. Ограничение мощи алгориитмов, слайд №27АиФП 6. Ограничение мощи алгориитмов, слайд №28АиФП 6. Ограничение мощи алгориитмов, слайд №29АиФП 6. Ограничение мощи алгориитмов, слайд №30АиФП 6. Ограничение мощи алгориитмов, слайд №31

Содержание

Вы можете ознакомиться и скачать презентацию на тему АиФП 6. Ограничение мощи алгориитмов. Доклад-сообщение содержит 31 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 1





6. Нижние границы эффективности алгоритмов
			Разум различает 				возможное 
			и невозможное; 
			рассудок различает 				осмысленное и 
			бессмысленное. Однако 
			возможное может 
			оказаться 						бессмысленным.
Макс Борн
Описание слайда:
6. Нижние границы эффективности алгоритмов Разум различает возможное и невозможное; рассудок различает осмысленное и бессмысленное. Однако возможное может оказаться бессмысленным. Макс Борн

Слайд 2





6.1. Доказательство нижних границ
	Пути оценки эффективности алгоритмов:
Установить класс асcимптотической эффективности и посмотреть, где он находится в иерархии классов эффективности.
Ответить на вопрос о том, как соотносится эффективность конкретного алгоритма с другими алгоритмами для решения той же задачи.
Описание слайда:
6.1. Доказательство нижних границ Пути оценки эффективности алгоритмов: Установить класс асcимптотической эффективности и посмотреть, где он находится в иерархии классов эффективности. Ответить на вопрос о том, как соотносится эффективность конкретного алгоритма с другими алгоритмами для решения той же задачи.

Слайд 3





6.1.1 Тривиальные нижние границы
	Простейший метод получения нижних границ (НГ) основан на подсчете количества элементов входных данных, которые следует обработать.
	Граница называется плотной, если уже существуют алгоритм, удовлетворяющий этой нижней границе.
	Пример: вычисление полинома 
	P(x)=Anxn+ An-1xn-1+…+A0  для заданных коэффициентов. 
	Размер входных данных: n. 
	Любой алгоритм вычисления полинома должен иметь эффективность Ω(n).
	Эта граница является плотной, т.к. существует схема Горнера с линейным временем работы.
Описание слайда:
6.1.1 Тривиальные нижние границы Простейший метод получения нижних границ (НГ) основан на подсчете количества элементов входных данных, которые следует обработать. Граница называется плотной, если уже существуют алгоритм, удовлетворяющий этой нижней границе. Пример: вычисление полинома P(x)=Anxn+ An-1xn-1+…+A0 для заданных коэффициентов. Размер входных данных: n. Любой алгоритм вычисления полинома должен иметь эффективность Ω(n). Эта граница является плотной, т.к. существует схема Горнера с линейным временем работы.

Слайд 4





6.1.2 Информационно-теоретические доказательства
	Информационно-теоретический подход пытается установить нижнюю границу эффективности алгоритма на основе количества информации, которую он производит.
Описание слайда:
6.1.2 Информационно-теоретические доказательства Информационно-теоретический подход пытается установить нижнюю границу эффективности алгоритма на основе количества информации, которую он производит.

Слайд 5





Приведение задачи
	
Для поиска нижней границы:
Описание слайда:
Приведение задачи Для поиска нижней границы:

Слайд 6


АиФП 6. Ограничение мощи алгориитмов, слайд №6
Описание слайда:

Слайд 7





Поиск евклидова минимального остовного дерева
Требуется: построить дерево минимальной длины, узлами которого являются n точек на декартовой плоскости.
Задача с известной нижней границей: задача единственности элементов.
Приведение: множество из n действительных чисел x1, x2  …, xn прелобразуется в множество точек на плоскости (x1,0),  (x2 ,0),…, (xn,0).
Нижняя граница: Ω(n log n)
Описание слайда:
Поиск евклидова минимального остовного дерева Требуется: построить дерево минимальной длины, узлами которого являются n точек на декартовой плоскости. Задача с известной нижней границей: задача единственности элементов. Приведение: множество из n действительных чисел x1, x2 …, xn прелобразуется в множество точек на плоскости (x1,0), (x2 ,0),…, (xn,0). Нижняя граница: Ω(n log n)

Слайд 8





Деревья принятия решения
	Высота дерева принятия решения с l листьями:  h>= log2l 		(1)
	Наибольшее количество листьев в таком дереве равно 2h .
Описание слайда:
Деревья принятия решения Высота дерева принятия решения с l листьями: h>= log2l (1) Наибольшее количество листьев в таком дереве равно 2h .

Слайд 9





Деревья принятия решения для алгоритма сортировки
	Высота дерева принятия решения для произвольного алгоритма сортировки:  
			Сworst>= log2 n! .
Описание слайда:
Деревья принятия решения для алгоритма сортировки Высота дерева принятия решения для произвольного алгоритма сортировки: Сworst>= log2 n! .

Слайд 10





	Используя формулу Стирлинга для n! получим:
	Используя формулу Стирлинга для n! получим:
	log2 n!  log22πn (n/e)n= 
=n log2 n - n log2 e + (log2 n)/2 + (log22π)/2 
n log2 n .
Вывод: необходимо примерно n log2 n сравнений для сортировки n–элементного списка любым алгоритмом сортировки, который основан на сравнениях.
Описание слайда:
Используя формулу Стирлинга для n! получим: Используя формулу Стирлинга для n! получим: log2 n!  log22πn (n/e)n= =n log2 n - n log2 e + (log2 n)/2 + (log22π)/2  n log2 n . Вывод: необходимо примерно n log2 n сравнений для сортировки n–элементного списка любым алгоритмом сортировки, который основан на сравнениях.

Слайд 11





6.2. P,  NP и  NP-полные задачи
Определение 1. Алгоритм решает задачу за полиномиальное время, если его временная эффективность в наихудшем случае принадлежит классу O( p(n)), 
где p(n) – полином от размера задачи n.
	Задача, решаемая за полиномиальное время называется легкой, в противном случае- трудной.
Описание слайда:
6.2. P, NP и NP-полные задачи Определение 1. Алгоритм решает задачу за полиномиальное время, если его временная эффективность в наихудшем случае принадлежит классу O( p(n)), где p(n) – полином от размера задачи n. Задача, решаемая за полиномиальное время называется легкой, в противном случае- трудной.

Слайд 12


АиФП 6. Ограничение мощи алгориитмов, слайд №12
Описание слайда:

Слайд 13





6.2.1. P и NP-задачи
6.2.1. P и NP-задачи
	Большинство ранее рассмотренных  задач могли быть решены с применением некоторого алгоритма за полиномиальное время. 
	Эти задачи можно рассматривать как множество, которое называют классом Р.
	Более формальное определение включает в Р только задачи принятия решения, представляющие собой задачи, выходом которых могут быть только ответы : «да» и «нет».
Описание слайда:
6.2.1. P и NP-задачи 6.2.1. P и NP-задачи Большинство ранее рассмотренных задач могли быть решены с применением некоторого алгоритма за полиномиальное время. Эти задачи можно рассматривать как множество, которое называют классом Р. Более формальное определение включает в Р только задачи принятия решения, представляющие собой задачи, выходом которых могут быть только ответы : «да» и «нет».

Слайд 14





Определении 2.
Определении 2.
	Класс Р представляет собой класс задач принятия решения, которые могут быть решены (детерминистическим алгоритмом) за полиномиальное время. 
	Этот класс задач называется полиномиальным.
Описание слайда:
Определении 2. Определении 2. Класс Р представляет собой класс задач принятия решения, которые могут быть решены (детерминистическим алгоритмом) за полиномиальное время. Этот класс задач называется полиномиальным.

Слайд 15





	Ограничение класса Р только задачами принятия решения можно объяснить следующими причинами.
	Ограничение класса Р только задачами принятия решения можно объяснить следующими причинами.
Во-первых, разумно сразу же исключить задачи, не разрешимые за полиномиальное время из-за экспоненциально большого размера входных данных. Например, задачу генерации всех подмножеств данного множества или всех перестановок n  различных элементов и т.п.
Во-вторых, многие важные задачи не являются задачами принятия решения в своей естественной постановке, но могут быть приведены к ряду проблем принятия решения, которые проще изучать.
Описание слайда:
Ограничение класса Р только задачами принятия решения можно объяснить следующими причинами. Ограничение класса Р только задачами принятия решения можно объяснить следующими причинами. Во-первых, разумно сразу же исключить задачи, не разрешимые за полиномиальное время из-за экспоненциально большого размера входных данных. Например, задачу генерации всех подмножеств данного множества или всех перестановок n различных элементов и т.п. Во-вторых, многие важные задачи не являются задачами принятия решения в своей естественной постановке, но могут быть приведены к ряду проблем принятия решения, которые проще изучать.

Слайд 16





		Для решения некоторых задач принятия решения невозможно применение вообще никаких алгоритмов. Такие задачи называются алгоритмически неразрешимыми.
		Для решения некоторых задач принятия решения невозможно применение вообще никаких алгоритмов. Такие задачи называются алгоритмически неразрешимыми.

	Задача останова (Алан Тьюринг, 1936 г.) Суть её состоит в следующем: 
		для данной компьютерной программы необходимо определить, завершится ли выполнение программы или она будет выполняться бесконечно.
Описание слайда:
Для решения некоторых задач принятия решения невозможно применение вообще никаких алгоритмов. Такие задачи называются алгоритмически неразрешимыми. Для решения некоторых задач принятия решения невозможно применение вообще никаких алгоритмов. Такие задачи называются алгоритмически неразрешимыми. Задача останова (Алан Тьюринг, 1936 г.) Суть её состоит в следующем: для данной компьютерной программы необходимо определить, завершится ли выполнение программы или она будет выполняться бесконечно.

Слайд 17





Доказательство неразрешимости этой проблемы от противного. 
Доказательство неразрешимости этой проблемы от противного. 
Предположим, что А – алгоритм, который решает задачу останова, то есть для любой программы Р и входных данных I. 
Функция преобразования входных данных в выходные может быть описана следующим образом:
Описание слайда:
Доказательство неразрешимости этой проблемы от противного. Доказательство неразрешимости этой проблемы от противного. Предположим, что А – алгоритм, который решает задачу останова, то есть для любой программы Р и входных данных I. Функция преобразования входных данных в выходные может быть описана следующим образом:

Слайд 18





	Будем рассматривать программу Р как входные данные для неё самой и использовать выход алгоритма А для пары (Р, Р) для построения программы Q следующим образом:
	Будем рассматривать программу Р как входные данные для неё самой и использовать выход алгоритма А для пары (Р, Р) для построения программы Q следующим образом:
			Завершается, если А(Р,Р)=0, т.е. 			программа Р не завершается 
			при входных данных Р;
Q(P)=	          Не завершается, если А(Р,Р)=1, т.е. 			программа Р завершается 
			при входных данных Р.
Описание слайда:
Будем рассматривать программу Р как входные данные для неё самой и использовать выход алгоритма А для пары (Р, Р) для построения программы Q следующим образом: Будем рассматривать программу Р как входные данные для неё самой и использовать выход алгоритма А для пары (Р, Р) для построения программы Q следующим образом: Завершается, если А(Р,Р)=0, т.е. программа Р не завершается при входных данных Р; Q(P)= Не завершается, если А(Р,Р)=1, т.е. программа Р завершается при входных данных Р.

Слайд 19





Подставляя вместо Р программу Q, получим:
Подставляя вместо Р программу Q, получим:
			Завершается, если А(Q,Q)=0, т.е. 			программа Q не завершается 
			при входных данных Q;
Q(Q)=	Не завершается, если А(Q,Q)=1, т.е. 		программа Q завершается 
	 		при входных данных Q.
	Мы пришли к противоречию, поскольку ни один из выходов программы Q невозможен, что и завершает доказательство.
Описание слайда:
Подставляя вместо Р программу Q, получим: Подставляя вместо Р программу Q, получим: Завершается, если А(Q,Q)=0, т.е. программа Q не завершается при входных данных Q; Q(Q)= Не завершается, если А(Q,Q)=1, т.е. программа Q завершается при входных данных Q. Мы пришли к противоречию, поскольку ни один из выходов программы Q невозможен, что и завершает доказательство.

Слайд 20





	Важные задачи, для которых не найден алгоритм с полиномиальным временем работы, но не доказана невозможность его существования:
	Важные задачи, для которых не найден алгоритм с полиномиальным временем работы, но не доказана невозможность его существования:
Задача построения гамильтонова цикла;
Задача о коммивояжере. Требуется найти кратчайший маршрут по n городам с известными целочисленными расстояниями между ними;
Задача о рюкзаке. Обсуждалась в разделе 5;
Задача о разделении. Даны n положительных целых числа. Требуется определить, можно ли разделить их на два непересекающихся подмножества с  одинаковыми суммами;
Задача об упаковке корзин. Даны n предметов, размеры которых представляют собой положительные рациональные числа, не превышающие единицу. Их необходимо разместить в наименьшем количестве корзин ёмкостью единица;
Задача о раскраске графа. Обсуждалась в разделе 5;
Задачи целочисленного линейного программирования. Требуется найти максимальное (минимальное) значение линейной функции нескольких целочисленных переменных при условии выполнения конечного множества ограничений в виде линейных равенств и (или) неравенств.
Описание слайда:
Важные задачи, для которых не найден алгоритм с полиномиальным временем работы, но не доказана невозможность его существования: Важные задачи, для которых не найден алгоритм с полиномиальным временем работы, но не доказана невозможность его существования: Задача построения гамильтонова цикла; Задача о коммивояжере. Требуется найти кратчайший маршрут по n городам с известными целочисленными расстояниями между ними; Задача о рюкзаке. Обсуждалась в разделе 5; Задача о разделении. Даны n положительных целых числа. Требуется определить, можно ли разделить их на два непересекающихся подмножества с одинаковыми суммами; Задача об упаковке корзин. Даны n предметов, размеры которых представляют собой положительные рациональные числа, не превышающие единицу. Их необходимо разместить в наименьшем количестве корзин ёмкостью единица; Задача о раскраске графа. Обсуждалась в разделе 5; Задачи целочисленного линейного программирования. Требуется найти максимальное (минимальное) значение линейной функции нескольких целочисленных переменных при условии выполнения конечного множества ограничений в виде линейных равенств и (или) неравенств.

Слайд 21





Определение 3.
Определение 3.
Недетерминистическим алгоритмом (НДА) называется двухэтапная процедура, которая получает в качестве входа экземпляр I задачи принятия решения и делает следующее:
недетерминистический этап («угадывание»): генерируется строка S, которая рассматривается в качестве кандидата на решение I;
детерминистический этап («проверка»): детерминистический алгоритм получает I и S в качестве входных данных и выдает «да», если S – решение задачи I и «нет» – в противном случае.
	НДА является недетерминистическим полиномиальным (НДП), если временная эффективность этапа проверки полиномиальная.
Описание слайда:
Определение 3. Определение 3. Недетерминистическим алгоритмом (НДА) называется двухэтапная процедура, которая получает в качестве входа экземпляр I задачи принятия решения и делает следующее: недетерминистический этап («угадывание»): генерируется строка S, которая рассматривается в качестве кандидата на решение I; детерминистический этап («проверка»): детерминистический алгоритм получает I и S в качестве входных данных и выдает «да», если S – решение задачи I и «нет» – в противном случае. НДА является недетерминистическим полиномиальным (НДП), если временная эффективность этапа проверки полиномиальная.

Слайд 22





Определение 4.
Определение 4.
Класс NP  это класс задач принятия решения, которые могут быть решены НДП алгоритмом.
Этот класс задач называется недетерминистическим полиномиальным. Большинство задач принятия решения принадлежит классу NP.
Прежде всего этот класс включает все задачи класса Р: РNP. 
Это соотношение истинно, так как если задача принадлежит классу Р, мы можем использовать ДПА, который решает её на этапе проверки НДА, просто проигнорировав строку S, генерируемую на этапе «угадывания».
Описание слайда:
Определение 4. Определение 4. Класс NP  это класс задач принятия решения, которые могут быть решены НДП алгоритмом. Этот класс задач называется недетерминистическим полиномиальным. Большинство задач принятия решения принадлежит классу NP. Прежде всего этот класс включает все задачи класса Р: РNP. Это соотношение истинно, так как если задача принадлежит классу Р, мы можем использовать ДПА, который решает её на этапе проверки НДА, просто проигнорировав строку S, генерируемую на этапе «угадывания».

Слайд 23





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

Слайд 24





	Истинность утверждения РNP должна приводить к тому, что каждая из многих сотен задач принятия решения может быть решена с использованием алгоритма с полиномиальным временем работы, хотя для многих подобных задач такие алгоритмы не найдены несмотря на многолетние усилия. 
	Истинность утверждения РNP должна приводить к тому, что каждая из многих сотен задач принятия решения может быть решена с использованием алгоритма с полиномиальным временем работы, хотя для многих подобных задач такие алгоритмы не найдены несмотря на многолетние усилия. 
	Кроме того, многие хорошо известные задачи принятия решения являются NP-полными.
Описание слайда:
Истинность утверждения РNP должна приводить к тому, что каждая из многих сотен задач принятия решения может быть решена с использованием алгоритма с полиномиальным временем работы, хотя для многих подобных задач такие алгоритмы не найдены несмотря на многолетние усилия. Истинность утверждения РNP должна приводить к тому, что каждая из многих сотен задач принятия решения может быть решена с использованием алгоритма с полиномиальным временем работы, хотя для многих подобных задач такие алгоритмы не найдены несмотря на многолетние усилия. Кроме того, многие хорошо известные задачи принятия решения являются NP-полными.

Слайд 25





Приведение NP-задач к NP-полным задачам
Описание слайда:
Приведение NP-задач к NP-полным задачам

Слайд 26





6.2.2 NP-полные задачи
Определение 5.
Задача принятия решения З1 называется полиномиально приводимой к задаче принятия решения З2, если имеется функция t, которая преобразует экземпляры З1 в экземпляры З2 так, что
t отображает все экземпляры З1 с положительным ответом на экземпляры З2 с положительным ответом, и все экземпляры З1 с отрицательным ответом на экземпляры З2 с отрицательным ответом;
t вычислима при помощи алгоритма с полиномиальным временем работы.
Описание слайда:
6.2.2 NP-полные задачи Определение 5. Задача принятия решения З1 называется полиномиально приводимой к задаче принятия решения З2, если имеется функция t, которая преобразует экземпляры З1 в экземпляры З2 так, что t отображает все экземпляры З1 с положительным ответом на экземпляры З2 с положительным ответом, и все экземпляры З1 с отрицательным ответом на экземпляры З2 с отрицательным ответом; t вычислима при помощи алгоритма с полиномиальным временем работы.

Слайд 27





Определение 6.
Определение 6.
Задача принятия решения D является NP-полной, если
она принадлежит классу NP и 
любая задача NP полиномиально приводима к D.
	Понятие NP-полноты требует полиномиальной приводимости всех задач в NP, как известных, так и неизвестных, к рассматриваемой задаче
Описание слайда:
Определение 6. Определение 6. Задача принятия решения D является NP-полной, если она принадлежит классу NP и любая задача NP полиномиально приводима к D. Понятие NP-полноты требует полиномиальной приводимости всех задач в NP, как известных, так и неизвестных, к рассматриваемой задаче

Слайд 28





Показать, что задача является NP-полной, можно в два этапа:
Показать, что задача является NP-полной, можно в два этапа:
Показать, что рассматриваемая задача является NP-задачей, т.е. случайным образом сгенерированная строка может быть проверена на пригодность в качестве решения задачи за полиномиальное время;
Показать, что любая задача из множества NP приводима к рассматриваемой задаче за полиномиальное время. Для выполнения этого этапа достаточно показать, что известная NP-полная задача может быть приведена к рассматриваемой задаче за полиномиальное время.
Описание слайда:
Показать, что задача является NP-полной, можно в два этапа: Показать, что задача является NP-полной, можно в два этапа: Показать, что рассматриваемая задача является NP-задачей, т.е. случайным образом сгенерированная строка может быть проверена на пригодность в качестве решения задачи за полиномиальное время; Показать, что любая задача из множества NP приводима к рассматриваемой задаче за полиномиальное время. Для выполнения этого этапа достаточно показать, что известная NP-полная задача может быть приведена к рассматриваемой задаче за полиномиальное время.

Слайд 29


АиФП 6. Ограничение мощи алгориитмов, слайд №29
Описание слайда:

Слайд 30





6.3. Выводы
6.3. Выводы
Непосредственно из определения NP-полноты следует, что если будет найден детерминистический алгоритм решения одной из NP-полных задач, то все задачи в NP могут быть решены за полиномиальное время при помощи детерминистического алгоритма, следовательно, РNP.
Нахождение алгоритма с полиномиальным временем работы для одной NP-полной задачи будет означать, что не существует качественного различия между сложностью проверки предлагаемого решения и поиска его за полиномиальное время для подавляющего большинства задач принятия решения всех видов.
Описание слайда:
6.3. Выводы 6.3. Выводы Непосредственно из определения NP-полноты следует, что если будет найден детерминистический алгоритм решения одной из NP-полных задач, то все задачи в NP могут быть решены за полиномиальное время при помощи детерминистического алгоритма, следовательно, РNP. Нахождение алгоритма с полиномиальным временем работы для одной NP-полной задачи будет означать, что не существует качественного различия между сложностью проверки предлагаемого решения и поиска его за полиномиальное время для подавляющего большинства задач принятия решения всех видов.

Слайд 31





Каким бы ни был окончательный ответ на вопрос P   NP, на сегодняшний день знание того, что задача является NP-полной, имеет важные практические следствия. Это означает, что, столкнувшись с NP-полной задачей, не стоит тратить массу усилий для разработки полиномиального алгоритма для всех её экземпляров. Вместо этого следует сконцентрироваться на поиске уменьшения сложности поставленной задачи.
Каким бы ни был окончательный ответ на вопрос P   NP, на сегодняшний день знание того, что задача является NP-полной, имеет важные практические следствия. Это означает, что, столкнувшись с NP-полной задачей, не стоит тратить массу усилий для разработки полиномиального алгоритма для всех её экземпляров. Вместо этого следует сконцентрироваться на поиске уменьшения сложности поставленной задачи.
Описание слайда:
Каким бы ни был окончательный ответ на вопрос P NP, на сегодняшний день знание того, что задача является NP-полной, имеет важные практические следствия. Это означает, что, столкнувшись с NP-полной задачей, не стоит тратить массу усилий для разработки полиномиального алгоритма для всех её экземпляров. Вместо этого следует сконцентрироваться на поиске уменьшения сложности поставленной задачи. Каким бы ни был окончательный ответ на вопрос P NP, на сегодняшний день знание того, что задача является NP-полной, имеет важные практические следствия. Это означает, что, столкнувшись с NP-полной задачей, не стоит тратить массу усилий для разработки полиномиального алгоритма для всех её экземпляров. Вместо этого следует сконцентрироваться на поиске уменьшения сложности поставленной задачи.



Похожие презентации
Mypresentation.ru
Загрузить презентацию