Редактирование: Методы оптимизации, определения

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

== [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] ==
<div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Униыерситета», это значит написать программу решения определённого класса задач.</div>

<div class="definition">'''Массовая задача''' — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.</div>

<div class="definition">'''Алгоритм (А)''' — программа для машины Тьюринга.</div>

<div class="definition">П — '''задача распознавания свойств''', если в качестве требования к решению является ответ «да» или «нет».</div>

<div class="definition">'''Алфавит &Sigma;''' — множество, состоящее из конечного числа символов <math>{|\sigma_i}|_{i=1}^k, k < \infin</math></div>

<div class="definition">'''Слово''' — конечный набор букв, слово будем обозначать &sigma = {&sigma;<sub>i</sub>, &sigma;<sub>j</sub>, &sigma;<sub>k</sub>, …}</div>

<div class="definition">'''Схема кодирования (кодировка)''' — e: П &rarr; &Sigma;<sup>*</sup>, &forall;I &rArr; e(I) = &sigma; &isin; &Sigma;<sup>*</sup> — отображение массовой задачи в множество слов, индивидуальная задача отображается в слово.</div>

<div class="definition">'''Язык''' — множество слов, соответствующих правильным решениям: L(&Pi;, e) = у(Н) = {&sigma; &isin; &Sigma;* | &Sigma; — алфавит e, &sigma; = e(I), I &isin; Y}</div>

<div class="definition">'''Определение 1.''' A решает задачу П с кодировкой e, если язык алгоритма совпадает с задачей П в кодировке E: L(A) = L(&Pi;, e), и для любого слова из их множества алгоритм останавливается: &forall; &sigma; &isin; &Sigma;* A(&sigma;) останавливается</div>

<div class="definition">'''Определение 2.''' Временна'я сложность алгоритма A решения задчи П — функция T<sub>A</sub>(.): T<sub>A</sub> = <math>max_{\sigma \isin \Sigma^*: |\sigma| \le n} t_A(\sigma), n \in \mathbb{Z}_+</math></div>

<div class="definition">'''Определение 3.''' Класс полиномиально разрешимых задач <math>\mathbb{P}</math> = {L(&Pi;, e) | &exist; A решающий &Pi; с кодировкой e, &exist;p(.) — полином: <math>T_{A(n)} \le p(n) \forall n \in \mathbb{Z}_+</math></div>

<div class="definition">'''Труднорешаемые задачи''' — задачи, для которых нет полиномиального алгоритма.</div>

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Шаблон:Курс Методы оптимизации

Получено с http://esyr.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F

Редактирование: Методы оптимизации, определения

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
 == [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] ==
-<div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Университета», это значит написать программу решения определённого класса задач.</div>
+<div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Униыерситета», это значит написать программу решения определённого класса задач.</div>
 <div class="definition">'''Массовая задача''' — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.</div>