Важко вирішити

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Чого не може комп'ютер, або

Машина повинна працювати, людина - думати.

Принцип IBM

Про завдання та алгоритмах

У середовищі математиків відома така притча. У давні часи, коли ніхто й гадки не мав про комп'ютери та їхні можливості, один індійський мудрець зробив велику послугу своєму правителю. Правитель вирішив віддячити йому і запропонував йому самому вибрати нагороду. На що мудрець відповів, що побажав би бачити шахову дошку, на кожній клітині якої були б розкладені зернятка пшона в наступному порядку: на першій - 2, на другий - 2х2 = 4, на третій - 2х2х2 = 8, на четвертій 24 = 16, і так далі на всіх клітинах.

Спочатку правитель зрадів легкості розплати. Але ось виконати обіцянку не зміг, так як він і його слуги навряд чи коли-небудь змогли б відрахувати 264 зерен на останню клітку, що відповідає приблизно 18,4 мільярдів мільярдів (!).

Завдання, сформульована у цій притчі, відноситься до розряду тих, при вирішенні яких найсучасніший комп'ютер безсилий так само, як в давнину слуги правителя. Знаючи продуктивність сучасних ЕОМ, не становить труднощів переконатися в тому, що користувачеві не вистачить всього його життя для відліку зерен, але в даному випадку це навіть не саме головне. Суть проблеми в тому, що досить незначно змінити вхідні дані, щоб перейти від розв'язуваної задачі до нерозв'язною. Кожна людина в залежності від своїх рахункових здібностей може визначити, починаючи з якої клітини (п'ятнадцятого чи допустимо, вісімнадцятої) продовжувати відраховувати зерна для нього не має сенсу. Те ж саме можна визначити і для ЕОМ, для якої подібні характеристики написані в технічній документації.

У випадках, коли незначне збільшення вхідних даних задачі веде до зростання кількості повторюваних дій у статечної залежності, то фахівці з алгоритмізації можуть сказати, що ми маємо справу з неполіноміальним алгоритмом, тобто кількість операцій зростає в залежності від кількості входів за законом, близьким до експоненті ех (е ≈ 2,72; інша назва - експоненціальні алгоритми).

Подібні алгоритми рішення має надзвичайно велике коло завдань, особливо комбінаторних проблем, пов'язаних з перебуванням поєднань, перестановок, розміщень будь-яких об'єктів. Завжди є спокуса багато завдань вирішувати вичерпання, тобто перевіркою всіх можливих комбінацій. Наприклад, так вирішується завдання безпомилкової гри в шахи. Ця задача відноситься до класичних нерозв'язним! Жодна сучасна ЕОМ не зможе згенерувати всі прості перестановки більш ніж 12 різних предметів (більше 479 млн.), не кажучи вже про всі можливі розкладках колоди з 36 гральних карт.

Тому труднорешаемой (нездійсненним) завданням можна називати таку задачу, для якої не існує ефективного алгоритму рішення. Показникові алгоритми виконання, в тому числі і вичерпні, абсолютно неефективні для випадків, коли вхідні дані змінюються в досить широкому діапазоні значень, отже, в загальному випадку вважати їх ефективними не можна. Ефективний алгоритм має не настільки різко зростаючу залежність кількості обчислень від вхідних даних, наприклад обмежено поліноміальну, тобто х знаходиться в основі, а не в показнику ступеня. Такі алгоритми називаються поліноміальними, і, як правило, якщо завдання має поліноміальний алгоритм рішення, то вона може бути вирішена на ЕОМ з великою ефективністю. До них можна віднести задачі сортування даних, багато завдань математичного програмування і т.п.

Чого ж не може і, швидше за все, ніколи не зможе комп'ютер в його сучасному (цифрова обчислювальна машина) розумінні? Відповідь очевидна: виконати рішення повністю аналітично. Постановка завдання полягає в заміні аналітичного рішення чисельним алгоритмом, який Ітеративний (тобто циклічно повторюючи операції) або рекурсивно (викликаючи процедуру розрахунку з самої себе) виконує операції, крок за кроком наближаючись до рішення. Якщо число цих операцій зростає, час виконання, а можливо, і витрата інших ресурсів (наприклад, обмеженою машинної пам'яті), також зростає, прагнучи до нескінченності. Завдання, своїми алгоритмами рішення створюють передумови для різкого зростання використання ресурсів, у загальному вигляді не можуть бути вирішені на цифрових обчислювальних машинах, тому що ресурси завжди обмежені.

Евристичні алгоритми

Інше можливе рішення описаної проблеми - в написанні чисельних алгоритмів, що моделюють технологічні особливості творчої діяльності і сам підхід до аналітичного розв'язання. Методи, використовувані в пошуках відкриття нового, засновані на досвіді вирішення родинних завдань в умовах вибору варіантів, називаються евристичними. На основі таких методів і виконується машинна гра в шахи. У евристики шахи розглядаються як лабіринт, де кожна позиція являє собою майданчик лабіринту. Чому ж саме така модель?

У психології мислення існує т.з. лабіринтова гіпотеза, теоретично представляє рішення творчого завдання як пошук шляху в лабіринті, який веде з початкової майданчика до кінцевої. Звичайно, можна перевірити всі можливі шляхи, але чи має часом потрапив у лабіринт? Абсолютно нереально вичерпування шахового лабіринту з 2х10116 майданчиків! Займаючись пошуком відповіді, людина користується іншими способами, щоб скоротити шлях до вирішення. Можливо скорочення числа варіантів перебору і для машини, досить "повідомити" їй правила, які для людини - досвід, здоровий глузд. Такі правила призупинять завідомо даремні дії.

Електронний підхід до штучного інтелекту

Історично спроби моделювання процесів мислення для досягнення аналітичних рішень робилися досить давно (з 50-х рр. ХХ ст.), І відповідна галузь інформатики була названа штучним інтелектом. Дослідження в цій області, спочатку зосереджені в декількох університетських центрах США - Массачусетському технологічному інституті, Технологічному інституті Карнегі в Піттсбурзі, Стенфордському університеті, - нині ведуться в багатьох інших університетах та корпораціях США та інших країн. Загалом дослідників штучного інтелекту, що працюють над створенням мислячих машин, можна розділити на дві групи. Одних цікавить чиста наука і для них комп'ютер-лише інструмент, що забезпечує можливість експериментальної перевірки теорій процесів мислення. Інтереси іншої групи лежать у області техніки: вони прагнуть розширити сферу застосування комп'ютерів і полегшити користування ними. Багато представників другої групи мало дбають про з'ясуванні механізму мислення - вони вважають, що для їх роботи це чи більш корисно, ніж вивчення польоту птахів у літакобудуванні.

В даний час, однак, виявилося, що як наукові, так і технічні пошуки зіштовхнулися з незрівнянно серйознішими труднощами, ніж уявлялося першим ентузіастам. На перших порах багато піонери штучного інтелекту вірили, що через якийсь десяток років машин знайде найвищі людські таланти. Передбачалося, що подолавши період "електронного дитинства" та навчившись в бібліотеках всього світу, хитромудрі комп'ютери, завдяки швидкодії, точності і безвідмовної пам'яті поступово перевершать своїх творців-людей. Зараз, відповідно до того, що було сказано вище, мало хто говорить про це, а якщо й говорить, то аж ніяк не вважає, що подібні чудеса не за горами.

Протягом усієї своєї короткої історії дослідники в галузі штучного інтелекту завжди перебували на передньому краї інформатики. Багато нині звичайні розробки, в тому числі вдосконалені системи програмування, текстові редактори і програми розпізнавання образів, значною мірою розглядаються на роботах з штучного інтелекту. Коротше кажучи, теорії, нові ідеї, і розробки штучного інтелекту незмінно привертають увагу тих, хто прагне розширити області застосування і можливості комп'ютерів, зробити їх більш "доброзичливими" тобто більш схожими на розумних помічників і активних порадників, ніж ті педантичні і тупуваті електронні раби , якими вони завжди були.

Незважаючи на багатообіцяючі перспективи, жодної з розроблених до цих пір програм штучного інтелекту не можна назвати "розумної" у звичайному розумінні цього слова. Це пояснюється тим, що всі вони вузько спеціалізовані; найскладніші експертні системи за своїми можливостями швидше нагадують дресированих або механічних ляльок, ніж людину з його гнучким розумом і широким кругозором. Навіть серед дослідників штучного інтелекту тепер багато хто сумнівається, що більшість подібних виробів принесе суттєву користь. Чимало критиків штучного інтелекту вважають, що такого роду обмеження взагалі нездоланні.

До числа таких скептиків належить і Х'юберт Дрейфус, професор філософії Каліфорнійського університету в Берклі. З його точки зору, істинний розум неможливо відокремити від його людської основи, закладеною у людському організмі. "Цифровий комп'ютер - не людина, - говорить Дрейфус. - У комп'ютера немає ні тіла, ні емоцій, ні потреб. Він позбавлений соціальної орієнтації, яка купується життям у суспільстві, а саме вона робить поведінку розумним. Я не хочу сказати, що комп'ютери не можуть бути розумними. Але цифрові комп'ютери, запрограмовані фактами і правилами з нашої, людської, життя, дійсно не можуть стати розумними. Тому штучний інтелект в тому вигляді, як ми його представляємо, неможливий ".

Інші підходи до штучного інтелекту

У цей же час вчені стали розуміти, що творцям обчислювальних машин є чому повчитися у біології. Серед них був нейрофізіолог і поет-аматор Уоррен Маккалох, що володів філософським складом розуму і широким колом інтересів. У 1942 р. Маккалох, беручи участь у науковій конференції в Нью-Йорку, почув доповідь одного зі співробітників Вінера про механізми зворотного зв'язку в біології. Висловлені в доповіді ідеї перегукувалися з власними ідеями Маккалоха щодо роботи головного мозку. Протягом наступного року Маккалох у співавторстві зі своїм 18-річним протеже, блискучим математиком Уолтером Піттс, розробив теорію діяльності головного мозку. Ця теорія і була тією основою, на якій сформувалося широко поширена думка, що функції комп'ютера та мозку значною мірою подібні.

Виходячи почасти з попередніх досліджень нейронів (основних активних клітин, складових нервову систему тварин), проведених Маккаллох, вони з Питтсом висунули гіпотезу, що нейрони можна спрощено розглядати як пристрої, які оперують двійковими числами. У 30-ті роки XX ст. піонери інформатики, особливо американський вчений Клод Шеннон, збагнули, що виконавчі одиниця і нуль цілком відповідають двом станам електричної ланцюга (включено-виключено), тому двійкова система ідеально підходить для електронно-обчислювальних пристроїв. Маккалох і Піттс запропонували конструкцію мережі з електронних "нейронів" і показали, що подібна мережа може виконувати практично будь-які вообразімие числові або логічні операції. Далі вони припустили, що така мережа в стані також навчатися, розпізнавати образи, узагальнювати, тобто вона має усіма рисами інтелекту.

Теорії Маккаллох-Піттса у поєднанні з книгами Вінера викликали величезний інтерес до розумних машин. У 40-60-ті роки все більше кібернетиків з університетів і приватних фірм закривалися в лабораторіях і майстернях, напружено працюючи над теорією функціонування мозку і методично Припаюючи електронні компоненти моделей нейронів.

З цього кібернетичного, або нейромодельного, підходу до машинного розуму скоро сформувався так званий "висхідний метод" - рух від простих аналогів нервової системи примітивних істот, що володіють малим числом нейронів, до найскладнішої нервової системи людини і навіть вище. Кінцева мета бачилася у створенні "адаптивної мережі", "самоорганізується системи" або "студіюючої машини" - всі ці назви різні дослідники використовували для позначення пристроїв, здатних стежити за навколишнім оточенням і з допомогою зворотного зв'язку змінювати свою поведінку, тобто вести себе так само як живі організми. Природно, аж ніяк не у всіх випадках можлива аналогія з живими організмами. Як одного разу помітили Уоррен Маккаллох і його співробітник Майкл Арбіб, "якщо по весні вам захотілося обзавестися коханої, не варто брати амебу і чекати поки вона еволюціонує".

Але справа тут не тільки в часі. Основною трудністю, з якою зіткнувся "висхідний метод" на зорі свого існування, була висока вартість електронних елементів. Занадто дорогою опинялася навіть модель нервової системи мурашки, що складається з 20 тис. нейронів, не кажучи вже про нервову систему людини, що включає близько 100 млрд. нейронів. Навіть найдосконаліші кібернетичні моделі містили лише неколько сотень нейронів. Настільки обмежені можливості збентежили багатьох дослідників того періоду.

Висновок

В даний час наявність надпродуктивних мікропропроцессоров і дешевизна електронних компонентів дозволяють робити значні успіхи в алгоритмічному моделюванні штучного інтелекту. Такий підхід дає певні результати на цифрових ЕОМ загального призначення і полягає в моделюванні процесів життєдіяльності і мислення з використанням чисельних алгоритмів, що реалізують штучний інтелект. Тут можна навести багато прикладів, починаючи від простої програми іграшки "тамагочі" і закінчуючи моделями колонії живих організмів і шаховими програмами, здатними обіграти відомих гросмейстерів. Сьогодні цей підхід підтримується практично всіма найбільшими розробниками апаратного та програмного забезпечення, оскільки досягнення при створенні евристичних алгоритмів використовуються і в вузькоспеціальних, прикладних областях при вирішенні складних завдань, приносячи значний прибуток розробникам.

Інші підходи зводяться до створення апаратури, спеціально орієнтованій на ті чи інші завдання, як правило, ці пристрої не загального призначення (аналогові обчислювальні ланцюга і машини, що самоорганізуються, перцептрони і т.п.). З урахуванням подальшого розвитку обчислювальної техніки цей підхід може виявитися більш перспективним, ніж передбачалося в 50-80гг.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
28.6кб. | скачати


Схожі роботи:
Внутрішній PR здатний вирішити комунікативні проблеми в компанії
Ах обдурити мене не важко
Записати задачу двоїсту до даної вирішити одну з пари завдань і відшукати оптимальне рішення
Текст-роздум на тему Чому птахам важко взимку
Проблеми російських винахідників Чому їм так важко реалізувати свої ідеї
Про велику вітчизняному війні «людям пам`ять потрібна як би важко їм не було з нею. .. »
Про велику вітчизняному війні - людям пам`ять потрібна як би важко їм не було з нею. ..
Твори на вільну тему - Важко чи легко робити добро притча про милосердного самарянина
© Усі права захищені
написати до нас