ОСТАННІЙ ПОДКАСТ
Підписуйся на найнауковішу розсилку!
І отримуй щотижневі новини науки і технологій

    Ми під'їдаємо крихти cookies за вами. Навіщо це нам?

    Читати

    Пардон за відволікалочку. Допоможи Куншт бути незалежним!

    Пардон за відволікалочку. Допоможи Куншт бути незалежним!

    Повідомлення успішно надіслано

    Для пошуку
    введіть назву запису
    Математика — 05.02.20
    ТЕКСТ: Іван Кудін
    Ілюстрації: Каталіна Маєвська
    Ми любимо тексти без помилок. Якщо ви все ж таки щось знайшли, виділіть фрагмент і натисніть
    Ctrl+Enter.
    Розв’яжи мені

    Якби в Ілона Маска запитали, що складніше: полетіти на Марс чи виграти у Сапер, він би без сумнівів відповів: «Виграти у Сапер». Жартуємо? Аж ніяк!

    Тюрінґ та його машина

    Мабуть, кожен школяр стикався з так званими «задачами із зірочкою». Вони зазвичай дуже «складні». Всі знають, як розв’язувати квадратне рівняння, адже зовсім нескладно підставити значення у готову формулу. Але навіть відмінники не завжди можуть розв’язати задачу «із зірочкою». Схожі проблеми турбують математиків, але, на відміну від школярів, вони навчилися розв’язувати ці задачі та навіть використовувати їхню «складність» собі на користь.


    Але що саме ми розуміємо під словом «складність»? Насамперед – кількість витраченого часу на розв’язання задачі, незалежно від того, пише людина роман чи забиває цвях. Якщо один цвях ми забиваємо п’ять хвилин, а другий – десять, простіше забити перший цвях. Звичайно, швидкість залежить від виконавця. Двадцятирічний юнак впорається із завданням швидше, ніж десятирічний хлопчик. У нього сильніші руки. Залежить швидкість і від способу, у який ви забиваєте цвях. Можна робити це молотком, а можна палицею.


    Так само швидкість вирішення будь-якої математичної задачі залежить від потужності виконавця (зазвичай комп’ютера) і способу (алгоритму) роботи. На жаль, не завжди перевага одного алгоритму над іншим очевидна, як у прикладі про палицю та молоток. Обчислювальні пристрої – це і персональні комп’ютери, і смартфони, і пральні машини. Всі вони побудовані по-різному, відрізняються виробниками, операційними системами та роком випуску. Часто потрібно порівняти швидкість роботи одного й того самого алгоритму, наприклад, на смартфоні та на комп’ютері. Для цього потрібен універсальний інструмент на кшталт лінійки.


    У нашому випадку лінійка – це так звана машина Тюрінґа. На відміну від звичних нам вимірювальних приладів, її не помацати рукою, проте можна намалювати у зошиті в клітинку. Отже, малюємо стрічку з комірками. Умовно вона нескінченна в обидві сторони. Над однією з комірок малюємо кружечок чи трикутничок.

    Приблизно такий вигляд має імпровізована машина Тюрінґа

    Це абстрактний зчитувальний пристрій. Він записує у комірку нуль чи одиницю або стирає їх звідти. Тепер «накажіть» вашому пристрою записати щось у комірку і перейти вправо чи вліво. Вітання, ваша машина Тюрінґа розпочала роботу! У такому вигляді можна уявити собі роботу смартфона у вашій кишені або роботу одного з перших комп’ютерів «Київ–1», що був розміром із кімнату.

     

    На жаль, алгоритми для деяких задач працюють так довго, що виконувати їх просто немає сенсу. Згадаймо задачу про комівояжера (з франц. commis voyageur – бродячий торговець). Щоб розпродати свій товар, торговцю необхідно об’їхати певну кількість міст і повернутися додому. Який маршрут буде для нього найшвидшим? На перший погляд, це звичайна шкільна задача «із зірочкою»,  проте вона є основною проблемою сучасної транспортної галузі. Вирішивши її, можна було б завжди вибирати найкращі маршрути для потягів, машин і літаків, перевозити пасажирів і товари значно швидше, ніж зараз.

     

    Найочевидніший спосіб – просто перебрати всі можливі варіанти, але їх дуже багато. Навіть для 100 населених пунктів комп’ютер, здатний перебирати мільйон комбінацій на секунду, буде працювати приблизно 3*10144 років. Є лише два варіанти: перший – скористатися швидким алгоритмом (який для цієї задачі досі не знайдений), другий – трохи змінити машину Тюрінґа.


    Для цього додаємо одну маленьку деталь – скаженого єнота. Чи будь-яку іншу істоту, яка вам подобається. Це «чарівне звірятко» пише символи зліва від комірки, де ви починаєте роботу, що хоче, але найчастіше – правильну відповідь. Символи, які він записав, – це «підказки» для виконання задачі. Єнот дає часткові випадкиНаприклад, загальний випадок – смажити будь-що на пательні. Часткові випадки – смажити яєчню, смажити м’ясо. розв’язку задачі, правильність яких можна швидко перевірити.

     

    До речі, саме через це виграти у Сапер може бути складніше, ніж полетіти на Марс. Коли ми говоримо про Сапер, розуміємо, що задля перемоги потрібно розв’язати не одну, а багато задач. Адже поле може бути таким великим, що підрахувати розв’язки не вдасться навіть на найпотужніших суперкомп’ютерах. До того ж швидкого алгоритму для Сапера не існує, тож пошук виграшної стратегії на малому полі також може виявитися складним завданням. Тоді як задача «полетіти на Марс» цілком чітка, для неї знадобиться конкретна кількість людей і ресурсів.

     

    Гра у Сапер за допомогою нової машини Тюрінґа матиме такий вигляд: єнот вказує, куди потрібно клікати, а гравець швидко перевіряє відповідь, клікаючи на вказану клітинку. Це та сама машина Тюрінґа, але побудувати її в реальному житті неможливо, бо немає «скаженого звірятка». Воно є таким собі «читом», що необхідний, аби отримати правильну відповідь. Тим часом машина перевіряє, чи справді ця відповідь правильна.


    Більшість задач, які виникають на практиці, наразі ділять на дві групи: ті, які можна вирішити швидко, і ті, розв’язок яких можна швидко перевірити. Першу групу позначають P, другу – NP. Задача про комівояжера і Сапер належать до другого типу. До P-задач належать, наприклад, арифметичні операції: додавання, віднімання, множення, ділення. Відповідь на них швидко дає будь-який калькулятор. NP-задачі не розв’яжуть навіть суперкомп’ютери, але наш «скажений єнот» чудово впорається з цим завданням, а машина Тюрінґа швидко перевірить, чи правильна його відповідь.

     

    До проблем на зразок задачі комівояжера належить, наприклад, пошук виграшної стратегії для гри у шахи. До речі, тут проявляється одна з позитивних сторін складності задач. Якби перемогти суперника було просто, гра не стала б такою популярною. Трохи інша ситуація з класичними шашками. Який би сильний суперник не сидів навпроти, завжди існує безпрограшна стратегія. Тобто будь-який хід суперника можна звести до нічиєї. Тож, задача «не програти у шашки» належить до класу P.


    Та чи знайдуть колись алгоритми для всіх складних задач? Це одне з найголовніших запитань сучасної математики. Чи рівні класи P та NP? Чи існують справді складні задачі? А раптом ні?

     

    Ідеальний світ

    Якщо вже братися за ці непрості запитання, у нас є два варіанти. Перший – побудувати «звірятко» на практиці (але поки що це неможливо). Другий – згадати жарт про математика та чайник. (Вирішувати завдання «закип’ятити чайник» фізик і математик будуть однаково: наллють воду, ввімкнуть плиту, поставлять на неї чайник і почекають, доки вода закипить. А от задачу «закип’ятити повний чайник» по-різному. Фізик, як нормальна людина, ввімкне газ і нагріє воду. Математик зведе задачу до тієї, що він уже вміє вирішувати: він виллє воду з чайника, чим зведе задачу до відомої йому задачі «закип’ятити чайник».)

     

    Існують так звані NP-повні задачі, до яких швидко зводяться всі задачі класу NP. Тобто якщо хоча б для однієї з цих задач знайти швидкий алгоритм, це автоматично означало б рівність P і NP. Щоправда, у вас буде багато конкурентів. Проблема дуже популярна у масах, насамперед через винагороду у мільйон доларів за її вирішення. За кількістю «геніїв», що надсилають науковцям свої проєкти, її можна порівняти хіба що з вічним двигуном.

     

    Та все-таки більшість фахівців сподіваються, що легко вирішити складні задачі неможливо. Адже тоді наш світ зміниться разюче та зовсім необов’язково на краще. Надто вже багато аналогій з романом-антиутопією «Ми» Євгена Замятіна спадає на думку.

     

    Мабуть, штучний інтелект – це галузь, що розвинулася б найбільше. Роботи змогли би значно краще та швидше за людей писати книжки та музику, створювати картини. Адже навіть написання цієї статті – NP-задача, для неї немає чіткого алгоритму. Можливо, з’явилися б музичні та літературні фабрики, подібні до тих, які описані у «Ми». Люди, як і головний герой, змогли б жити за оптимальним розпорядком дня, ніколи не запізнюючись навіть на хвилину, адже громадський транспорт і взагалі всі структури працювали б без помилок. Видається фантастичним, чи не так? 

     

    Це песимістичний, але не єдиний варіант розвитку подій. «Ми» – доволі похмура пародія на Радянський Союз. Є інший бік медалі. Всі, навіть дуже великі, обчислення проводилися б миттєво. Важко уявити, наскільки швидко розвивалася б наука. А відтак, більшість глобальних проблем, як перенаселення та голод, скоріш за все залишилися б у минулому. Ба більше, ресурсів вистачало б на всіх. Став би можливим головний утопічний принцип комунізму «від кожного за здібностями, кожному за потребами». Люди змогли б займатися тільки творчою діяльністю, адже всю монотонну роботу можна було б доручити штучному інтелекту.


    Міфічний пристрій, який математики називають «недетермінована машина Тюрінґа», – лише потужний інструмент. Якщо він коли-небудь буде створений, то тільки від людей залежить, як ним скористаються. Це питання не математики, а етики. Адже навіть коли людина зможе все, етичні питання залишаться складнішими, ніж NP-задачі.

    ТЕКСТ: Іван Кудін
    Ілюстрації: Каталіна Маєвська
    Статті
    Наука
    Екологічно чиста отрута: уривок з книжки «Зоологічна екскурсія супермаркетом»

    Чому краще утриматися від «дикого» промислу морепродуктів, особливо у водоймах, де цвіте вода?

    Наука
    Передумови приходу диктаторів до влади: Італія, Німеччина, РФ

    Що стало передумовами приходу диктаторів до влади на прикладі фашистської Італії, нацистської Німеччини та путінської росії? Розповідає співавтор і ведучий каналу «Історія Без Міфів» Владлен Мараєв.

    Людина
    Як кожен з нас може подякувати військовим і допомогти їм з адаптацією

    Як змінюється світосприйняття військових і що ми можемо зробити, аби висловити їм вдячність і допомогти в адаптації до мирного життя?

    Біологія
    Не тільки в історії. Який слід залишить війна в наших генах

    Як війни, голод та важкі психологічні травми залишають слід у геномі людини й чи можемо ми на це якось повпливати?

    Космос
    Що таке сонячні плями і чи впливають вони на людей

    Чи можуть спалахи на Сонці та магнітні бурі провокувати погане самопочуття в людей?

    Ідеї
    Пропаганда у російському кіно

    Як кіно стало частиною пропагандистської та політичної ідеології росії та чи можна якось дати цьому раду?

    Повідомити про помилку

    Текст, який буде надіслано нашим редакторам: