МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Класи P та NPОзначення. P-задачею називається задача, яка може бути розв'язана на детермінованій машині Тюрінга за поліноміальний час O (nm), де n - розмір задачі. Іншими словами, P-задача - це задача, для розв'язку якої існує поліноміальний алгоритм. Під детермінованою машиною Тюрінга мається на увазі машина Тюрінга у вищенаведеному розумінні. "Детермінованість" означає, що в будь-який момент дія машини є чітко визначеною. На відміну від цього, не детермінована машина Тюрінга у будь-який момент часу може одночасно реалізовувати декілька можливих варіантів дій. Така машина є теоретичною абстракцією і не може бути реалізована на основі фон-нейманівських принципів. Вона могла б бути реалізована лише на багатопроцесорній машині за умови наявності необмеженої кількості процесорів. Формально інструкцію не детермінованої машини Тюрінга можна записати у вигляді: aisk→SAI, це означає, що, якщо машина перебуває у стані sk і читає символ ai, вона породжує певну кількість нових машин, кожна з яких записує деякий символ з S, переходить до деякого стану з A і зсувається вправо, вліво, або залишається на місці. Можна вважати, що всі породжені машини продовжують перебір варіантів. Означення. NP-задачею називається задача, яка може бути розв'язана на детермінованій машині Тюрінга за поліноміальний час O (nm), де n - розмір задачі. Якщо ж обмежитися детермінованими алгоритмами, то для вирішення будь-якої NP-задачі можна використовувати схему перебору з поверненням або подібні до неї перебірні схеми. Як зазначалося раніше, подібні алгоритми є експоненційними по своїй суті, і задачі, які вимагають застосування таких алгоритмів, відносяться до класу важко вирішуваних. Втім, це не виключає існування поліноміальних алгоритмів, і для ряду задач, які мають характер пошуку на дереві, такі алгоритми дійсно були знайдені. Позначимо через P клас P-задач, а через NP - клас NP-задач Ясно, що P - підмножина NP. Але питання про те, чи є це включення строгим, залишається відкритим. Як визначається алгоритм? Яким вимогам має задовольняти алгоритм? Яка функція є обчислювальною? Що таке часова складність алгоритму? Що таке ємнісна складність алгоритму? Як описується складність алгоритму? Які ви знаєте класи алгоритмів? Що називається P - задачею?
|
||||||||
|