Ефективний метод або ефективна процедура у логіці, математиці та інформатиці, особливо у металогіці та теорії обчислюваності — це процедура вирішення проблеми з певного класу. Ефективний метод іноді також називають «механічним» методом або процедурою.
Визначення
Визначення ефективного методу передбачає більше, ніж сам метод. Для того, щоб метод називався ефективним, він повинен розглядатися відповідно до класу проблем. Через це один метод може бути ефективним стосовно одного класу проблем і «не бути» ефективним щодо іншого класу. Метод формально називається ефективним для класу задач, якщо він відповідає наступним критеріям:
- Він складається з кінцевого числа точних, кінцевих інструкцій;
- Коли він застосовується до проблеми свого класу:
- Він завжди закінчується (завершується) після кінцевого числа кроків;
- Він завжди дає правильну відповідь;
- В принципі, він може бути використаний людиною без будь-яких засобів, крім написання матеріалів.
- Для досягнення успіху слід лише [en]дотримуватися його інструкцій. Іншими словами, це не вимагає [en].
Іноді також необхідно, щоб метод ніколи не приймав результат за відповідь, коли він застосовується до проблем, що не належать до його класу. Додавання цієї вимоги зменшує набір класів, для яких існує ефективний метод.
Алгоритми
Алгоритм — це ефективний методом для обчислення значень функції. Функції, для яких існує ефективний метод, іноді називають ефективно обчислюваними.
Обчислювальні функції
Кілька незалежних зусиль, щоб дати офіційну характеристику ефективного обчислення, призвели до різноманіття запропонованих визначень (зазальна рекурсія, машини Тюрінга, лямбда-числення), які раніше були еквівалентними. Отже, рекурсивна або ефективна обчислюваність — поняття, що зафіксоване цими визначеннями.
У тезі Черча сказано, що ці два поняття збігаються. Обчислювана функція — це будь-яка арифметична функція, яка ефективно піддається підрахунку. Оскільки це не математичне твердження, його неможливо довести за допомогою математичного доказу.
Див. також
Список літератури
- , Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
- ; Copeland, Jack; Proudfoot, Diane (June 2000). . AlanTuring.net. Turing Archive for the History of Computing. Архів оригіналу за 27 березня 2013. Процитовано 23 березня 2013.
- The Cambridge Dictionary of Philosophy, effective procedure
- S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, , pp. 233 ff., esp. p. 231.
Це незавершена стаття з логіки. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Efektivnij metod abo efektivna procedura u logici matematici ta informatici osoblivo u metalogici ta teoriyi obchislyuvanosti ce procedura virishennya problemi z pevnogo klasu Efektivnij metod inodi takozh nazivayut mehanichnim metodom abo proceduroyu ViznachennyaViznachennya efektivnogo metodu peredbachaye bilshe nizh sam metod Dlya togo shob metod nazivavsya efektivnim vin povinen rozglyadatisya vidpovidno do klasu problem Cherez ce odin metod mozhe buti efektivnim stosovno odnogo klasu problem i ne buti efektivnim shodo inshogo klasu Metod formalno nazivayetsya efektivnim dlya klasu zadach yaksho vin vidpovidaye nastupnim kriteriyam Vin skladayetsya z kincevogo chisla tochnih kincevih instrukcij Koli vin zastosovuyetsya do problemi svogo klasu Vin zavzhdi zakinchuyetsya zavershuyetsya pislya kincevogo chisla krokiv Vin zavzhdi daye pravilnu vidpovid V principi vin mozhe buti vikoristanij lyudinoyu bez bud yakih zasobiv krim napisannya materialiv Dlya dosyagnennya uspihu slid lishe en dotrimuvatisya jogo instrukcij Inshimi slovami ce ne vimagaye en Inodi takozh neobhidno shob metod nikoli ne prijmav rezultat za vidpovid koli vin zastosovuyetsya do problem sho ne nalezhat do jogo klasu Dodavannya ciyeyi vimogi zmenshuye nabir klasiv dlya yakih isnuye efektivnij metod AlgoritmiAlgoritm ce efektivnij metodom dlya obchislennya znachen funkciyi Funkciyi dlya yakih isnuye efektivnij metod inodi nazivayut efektivno obchislyuvanimi Obchislyuvalni funkciyiKilka nezalezhnih zusil shob dati oficijnu harakteristiku efektivnogo obchislennya prizveli do riznomanittya zaproponovanih viznachen zazalna rekursiya mashini Tyuringa lyambda chislennya yaki ranishe buli ekvivalentnimi Otzhe rekursivna abo efektivna obchislyuvanist ponyattya sho zafiksovane cimi viznachennyami U tezi Chercha skazano sho ci dva ponyattya zbigayutsya Obchislyuvana funkciya ce bud yaka arifmetichna funkciya yaka efektivno piddayetsya pidrahunku Oskilki ce ne matematichne tverdzhennya jogo nemozhlivo dovesti za dopomogoyu matematichnogo dokazu Div takozhAlgoritmichna rozv yaznist Problema viboru Funkcionalna problema en Rekursivnij nabir Algoritmichno nerozv yazna zadachaSpisok literaturi Metalogic An Introduction to the Metatheory of Standard First Order Logic University of California Press 1971 Copeland Jack Proudfoot Diane June 2000 AlanTuring net Turing Archive for the History of Computing Arhiv originalu za 27 bereznya 2013 Procitovano 23 bereznya 2013 The Cambridge Dictionary of Philosophy effective procedure S C Kleene 1967 Mathematical logic Reprinted Dover 2002 ISBN 0 486 42533 9 pp 233 ff esp p 231 Ce nezavershena stattya z logiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi