ПРОГРЕСС В ИССЛЕДОВАНИИ АЛГОРИТМОВ
Electronic Volodymyr Dahl East Ukrainian National University Institutional Repository
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
ПРОГРЕСС В ИССЛЕДОВАНИИ АЛГОРИТМОВ
|
|
| Creator |
Плотников, А. Д.
|
|
| Subject |
алгоритм
машина Тьюринга класс P класс NP односторонняя функция 519.161 |
|
| Description |
В докладе прослеживается последовательное развитие понятия алгоритма и необходимость выбора в качестве модели вычислений абстрактной математической машины машины Тьюринга. Показывается необходимость оценки сложности алгоритмов. Формулируются свойства массовых задач, принадлежащих классу NP. Вводится понятие класса P, содержащего задачи, для которых существуют полиномиально-временные решающие алгоритмы. Поясняется важность проблемы ”P vs NP”. Определяется класс UF задач, для которых промежуточные и конечные результаты могут быть проверены за полиномиальное время от размерности задачи. Устанавливается, что класс UF строго входит в класс NP и не равен ему. Показывается, что класс P входит в класс UF. Откуда следует, что классы P и NP не совпадают. На основе полученных результатов устанавливается существование односторонних функций, играющих важную роль в криптологии. |
|
| Publisher |
СНУ ім. в. Даля
|
|
| Date |
2013-03-20T09:05:01Z
2013-03-20T09:05:01Z 2012 |
|
| Type |
Article
|
|
| Identifier |
Плотников А. Д. ПРОГРЕСС В ИССЛЕДОВАНИИ АЛГОРИТМОВ [Електронний ресурс] / А. Д. Плотников // Вісник Східноукраїнського національного університету імені Володимира Даля : наук. журнал. – Луганськ, 2012. - № 8 (179), ч. 2. - С. 179-183.
http://dspace.snu.edu.ua:8080/jspui/handle/123456789/2171 |
|
| Language |
ru
|
|