|
Реферат: Цифровые ЭВМ (Компьютеры)
Міністерство освіти України
Дніпропетровський Національний Університет
Радіофізичний факультет
Кафедра ЭОМ
Курсовий проект
по курсу «Цифрові ЭОМ»
Виконав:
ст. гр. РІ-97-1
Орлов С.А.
Перевірив:
Істушкін В. Ф.
Дніпропетровськ
2000
ЗМІСТ
1. Вступ
2. Завдання
3. Структура мікро-ЕОМ
4. Функціональна схема микро-ЕОМ
4.1 Арифметико-логічний пристрій
4.2 Блок мікропрограмного управління
4.3 Блок обробки запитів переривань
4.4 Блок внутрішньої синхронізації
4.5 Оперативна пам'ять
5. Розробка мікропрограми
5.1 Команда HER
5.2 Команда SE
6. Розрахункова частина
7. Висновок
Додатки:
1. Структурна схема
2. Таблиці мікрокоманд
3. Схема БОД
4. Схема БПП
5. Схема БМУ
6. Схема ОЗП
7. Схема БВС
Прийняті у проєкті скорочення та терміни
Список літератури
1. ВСТУП
У курсовому проекті необхідно розробити ЕОМ, що складається з
процесора (П), оперативного запам'ятовуючого пристрою (ОЗП), постійного
запам'ятовуючого пристрою (ПЗП), зовнішніх пристроїв (ЗП). ОЗП і ПЗП
зтворюють основну пам'ять (ОП). У кожен момент часу можливе звертання
тільки до однієї комірки пам'яті. В ОП адресується кожен байт. ЗП можуть
бути активні і пасивні. Активні ЗП на відміну від пасивних можуть формувати
запит, що вказує на необхідність обміну інформацією з ОП. Обмін інформацією
здійснюється під керуванням БПП с використанням системи переривань.
Розроблена ЕОМ повинна моделювати систему команд ЕС ЕОМ.
Детальна розробка команд припускає складання алгоритму виконання
команди в точності і відповідності з її реалізацією в ЕС ЕОМ, і складання
по йому мікропрограми виконання команди як у символічної, так і в цифровій
формі з вказівкою комірок ПЗП в який розміщені окремі мікрокоманди. При
проектуванні мікропрограмного пристрою управління вважати, що всі команди
по складності реалізації рівноцінні, а їхня мікропрограма складається з
такої ж кількості мікрокоманд, як і мікропрограма окремо розробленої
команди. З цих даних визначається ємність ЗП мікропрограми і розміщення в
йому мікропрограм окремих мікрокоманд.
2. Вибір завдання
Номер залікової книжки 971694, що в 16-річному виді представлено як
ED3AE. У двійковой формі номер заліковки представляється так:
0011 1010 1110
a b c
Звідси всі необхідні числа для вибору завдання представлені в таблиці
1.
Таблиця 1.
|a1 |a2 |a3 |a4 |b1 |b2 |b3 |b4 |c1 |c2 |c3 |C4 |
|0 |0 |1 |1 |1 |0 |1 |0 |1 |1 |1 |0 |
Требуеться розробити мікроЭОМ зі слідуючими характеристиками :
серія мікросхем 1804;
довжина ячейки пам`яти й разрядность МП - 64 біт;
ємність ОП 256 Кбайт;
число зовнішніх пристроїв 63;
мікросхеми ОЗП 541РУ2;
мікросхеми ППЗП 556РТ6;
реалізація машинних команд SE, HER.
3. Cтруктурна схема мікро-ЕОМ
Структурна схема приведена на рисунку в додатку 1. Мікро_ЕОМ складається
із слідуючих елементів:
. операційоний пристрій (ОП);
. блок микропрограмного управління (БМУ);
. блок приоритетів переривань (БПП);
. блок синхронізації (БС);
. схема обміну інформації (СОІ);
. оперативний запам`ятовуючий пристрій (ОЗП);
. зовнішні пристрої ([pic]-[pic]).
Структурна схема мікро-ЕОМ представляє загальний принцип роботи всієї
мікро-ЕОМ.
ОП виповнює обробку данних, поступаючих до нього, забезпечує зберігання
та видачу признаків результатів, отриманих в ОП, формування слова стану.
БМУ забеспечує прийняття виконуваної команди із ОЗП, преобразування кода
команди для подальшого обчислювання, виробка адреси мікрокоманди для
пам`яті мікропрограм, формування необхідного формату мікрокоманди для
керування БІСами ЕОМ, а також забеспечує перехід на мікропрограму-відробник
вектору переривання, адреса якого надходить з блоку БПП.
БПП забеспечує прийняття запросів від зовнішніх пристроїв, керування
приоритетами ліній переривань, формування вектора переривання та по цьому
вектору формування адреси відробнику переривання для БМУ.
В ОЗП зберігаються команди, які необхідно виконувати на даній мікро-ЕОМ,
причому записані у системі ЕС ЕОМ, систему команд якої емулює розроблена
мікро-ЕОМ.
БС забеспечує усі схеми ЕОМ стабільними тактовими послідовностями,
формірує машинні цикли для БІС.
В загальному виді мікро ЕОМ функціонує слідуючим образом: Виконувана
команда зчитується з ОЗП та попадає на БМУ. БМУ преобразує код команди та
починає виконання мікропрограми обробки поданої мікрокоманди. Під час
виконування мвкрокоманд БМУ програмує мікропроцесорний комплект на
виконання конкретних операцій згідно алгоритму. Якщо у час виконання
програми надходить переривання від зовнішнього пристрою, БПП формує запит
на переривання та адресу обробника переривання, та БМУ починає обробку
переривання.
4. Функціональна схема микро-ЕОМ
4.1 Арифметико логічний пристрій
Арифметико-логічний пристрій (АЛП) призначено для виконання
арифметичних і логічних операцій, операнди для яких або безпосередньо
надходять із шини даних (ШД), або читаються з внутрішнього реєстрового
запам'ятовуючого пристрою (РЗП) АЛП, адреса для який надходить зі ШД. АЛП
містить:
шістнадцять центральних процесорних елемента (ЦПЕ) К1804ВР2;
контролер станів К1804ВР2;
схема прискореного переносу К1804ВР1;
БІС К1804ВР2 являє собою 4-розрядну нарощувану мікропроцесорну секцію
(МПС) з підвищеними алгоритмічними можливостями й орієнтована на обробку
складних арифметичних алгоритмів. Володіючи секционированной структурою,
даний ЦПЕ дозволяє за рахунок об'єднання декількох БІС будувати процесори
(чи АЛП) довільної розрядності, кратної 4.
Дана МПС керується кодом мікрокоманди, поданим на входи I0-I8, у
залежності від значення якого БІС вибирає джерела операндв, виконувану над
ними операцію і приймач результату цієї операції.
БІС К1804ВР2 призначена для замикання даних навколо МПС К1804ВР2 при
побудові АЛП мікро-ЕОМ, забезпечуючи також функції регістра стану і
формірователя сигналу переносу.
Під впливом зовнішніх сигналів управління дана БІС формує сигнали для
організації зрушень і переносів в АЛП, а також, обробляючи ознаки стану, що
надходять з АЛП блоку обробки даних:
перенос (C);
нульовий результат (Z);
знак результату (N);
переповнення (OVR),
формує сигнал умови для організації розгалужень як у програмах, так і в
мікропрограмах.
Для порівняння двох чисел необхідно подать ці числа на АЛП,
організувати їхнє вирахування, а на шину управління БІС К1804ВР2 подать
команду порівняння по необхідній умові. Після чого КС за значенням C, Z, N,
OVR сформує на виході CT сигнал низького рівня, якщо задана умова
виконується, чи сигнал високого рівня, якщо воно не виконується.
4.2 Блок мікропрограмного управління
Блок мікропрограмного управління використовується для управління
послідовністю мікрокоманд та містить в собі:
регістр команд (РгК) на К1804ИР2;
дешифратор начальної адреси мікропрограми на базі двох БІС ПЗУ К556РТ6;
формувач адреси мікропрограми К1804ВУ4;
пам`ять мікропрограм (ПМП) на базі семи БІС К556РТ6;
регістр мікрокоманд (РгМК) на базі 7 БІС К1804ИР2;
мультиплексор для вибору істочнику переривання.
БІС К1804ВУ4 представля з себе 12-розрядну схему
Керування адресом мікрокоманди та призначена для формуванняадреси ПЗП
мікрокоманд ємністю до 4Кслів в составі пристроїв мікропрограмного
управління. Крім того, подана БІС забеспечує:
отримування наступної адреси шляхом нарощування лічильника адресів на 1;
многократний півтор одного й того ж адреса;
умовний чи безумовний перехід до адреси, поданому чи з внутрішніх
істочників, чи з вхідної шини БІС.
Умовний чи безумовний перехід до подпрограми;
Організація циклів.
Під впливом зовнішніх сигналів керування БІС формує послідовність
адресів, які поступають на пам`ять микропрограм. Послідовності адресів
кожного разу будуть отвічати послідовності мікрокоманд, вібраній з пам`яті
мікропрограм.
БІС К1804ВУ4 керується кодом мікрокоманди, що подається на входи І0-
І3, а також сигналами на входах СС (дозвіл переходу) та ССЕ (дозвіл аналізу
сигналу на СС). Крім адреси на вихідній шині, БІС формірує три керуючих
сигнали (VE, PE, PE), за допомогою яких здійснюється підключення до вхідної
шини БІС одного з трьох зовнішніх істочників адреси – чи регистру
мікрокоманд (РгМК) (РЕ), либо дешифратору начальних адресів (МЕ), чи з
блоку обробки переривань (VE). Для кожної мікрокоманди виробляється тільки
один сигнал дозвілу зовнішнього істочнику.
4.3.Блок обробки запитів переривань
Блок обробки запитів переривань (БОЗП) призначений для фіксування
запитів на переривання, формування адреси початку мікропрограми
обслуговування запиту на переривання, що має найвищий пріоритет серед усіх
що прийшли, а також для вироблення сигналу запиту на обслуговування
переривання, що разом з адресою надходить на БМУ. БОЗП містить у собі:
БІС узгодження БІС К1804ВН1 з К1804ВР3;
вісім БІС пріоритетного переривання К1804ВН1;
БІС К1804ВН1 являє собою 8-розрядну мікропрограмувальну схему
пріоритетного векторного переривання і призначена для обробки запитів на
переривання, що надходять по 8 вхідних шинах від різних пристроїв,
відповідно до їхнього рівня пріоритету. БІС може реєструвати як рівневих,
так і імпульсні запити, що надходять на входи INR7-INR0. Якщо на керуючий
вхід СОМО поданий низький рівень, то БІС реєструє імпульсні запити.
Пріоритет отриманого запиту порівнюється з тим, що міститься у внутрішньому
регістрі стану, і якщо він не нижче останнього, то БІС фіксує його і
виставляє його номер на вихідну шину V3-V0.
БІС К1804ВР3 являє собою керований пріоритетний шифратор 8х3 і
призначена для спільної роботи з БІС К1804ВН1 у складі БОЗП із кількістю
рівнів пріоритетів, великим 7. Один такий шифратор обслуговує до 8 БІС
К1804ВН1 (БОЗП на 31 рівня пріоритетів).
4.4. БЛОК ВНУТРІШНЬОЇ СИНХРОНІЗАЦІЇ
Блок внутрішньої синхронізації (БВС) являє собою системний тактовий
генератор і призначений для синхронізації внутрішніх блоків процесора. Він
зібраний на єдиній БІС К1804ГГ1, що має стабілізований (за допомогою
зовнішнього кварцевого резонатора) генератор опорної частоти від 1 до 30
МГц, мікропрограмувальну тривалість циклу тактових імпульсів від 3 до 10
періодів опорної частоти і стану «робота», «останов», «чекання», «кроковий
режим».
4.5 Блок основної пам`яті
Згідно завданню ОП составляє 256 Кбайт пам`яті ОЗП. Одне слово займає
64 біт. В кожний момент часу може бути звертання тільки до однієї ячейки
пам`яти. У схемі використовуються статичні ОЗП К541РУ2.
Використані в роботі мікросхеми ОЗП мають ємність 4 Кбіт з
організацією 1*4Кбіт, тому наш модуль ОЗП буде організований у 32 банки по
16 мікросхеми в одному. Один банк має ємність 4*16=64Кбіт=8Кбайт з
розрядністю слова 64 біт.
Для адресації банків розроблена схема дешифрації старших розрядів
адреси. Цей дешифратор побудований на п`яти дешифраторах (типу 3 в 8),
включених у каскадному включенні. Це дозволяє адресувати 32 банки,
використовуючи старші 5 адресні розряди А10-А14. З виходів дешифраторів
сигнали виборки поступають на входи CS мікросхем ОЗП.
Пам`ять має двунаправлену шину даних, тому для правильного керування
буферними регистрами розроблена схема на елементах АБО та НІ, яка керує
входами дозвілу роботи регистрів. Регистр читання відкривається тільки коли
активні сигнали CS та RD, регистр запису – коли активні CS та WR.
5. Розробка мікропрограми
Під створенням мікропрограми мається в виду запис прошивки ПЗП
мікропрограм, тобто запрограмувати значення усіх бітів при виконанні
кожної команди.
Розряди мікрокоманди керують работой усіх узлів мікропроцесорного
приладу: керування блоком обробки даних, блоком виконання команд, приладом
приоритетного переривання, трактом даних та усіма остальними приладами.
Мікропрограми розрізняються по длині в залежності від типу команди:
для команд типу регистр-регистр достатньо чотирьох тактів, але для команд
типу регистр-пам`ять необхідно вже не менше семи мікрокоманд, тому що треба
додатково обчислювати адреси операнду та загрузка його із пам`яті.
При виконуванні команд загальними у всіх є мікрокоманди, які
реалізують слідуючі функції: формування адреси команди, вибірка команди,
декодування команди. Подальші шаги мікропрограм залежать від конкретної
команди.
5.1 Команда HER
Ця команда виконує аріфметичний здвиг вліво з нормалізацієй. Вона має
формат “регистр-пам`ять” та зписується так:
HER b1, r2, d1
де r2 - адреса ОЗП, де зберігається здвигаєме число й куди буде записан
результат операції;
b1 - адреса ЗП, в якому зберігається базове значення кількості здвигаємих
розрядів;
d1 - кількість розрядів, на яку буде здвигатись число r1.
Сумарна кількість здвигів визначається підсумовуванням змісту ОЗП b1 і
значення d1.
Алгоритм виконування команди представлений на рисунку
[pic]
5.2 Команда SE
Команда SE - віднімання з нормалізацієй.
Формат команди:
SE r1, s2
Алгорітм виконування: по команді SE другий операнд, який знаходится у
пам`яті за адресою s2 (адреса повинна знаходитисьна границі слова),
віднімається з першого операнду, й нормалізована разность розміщається на
месті першого операнду в регистр r1.
Блок-схема виконання команди:
ПОЧАТОК
Формування адреси команди
Вибірка
команди
Декодування
Вибірка зміщення
Формування адреси операнду
Выбірка операнду
Виконання команди
КІНЕЦЬ
6. РОЗРАХУНКОВА ЧАСТИНА
Для спроектованої мікро-ЕОМ необхідно провести деякі оцінні розрахунки
технічних характеристик. Потрібно визначити споживану потужність усієї
мікро-ЕОМ, період проходження тактових імпульсів і час виконання команд
описаних раніше.
Розрахуємо приблизну споживану потужність мікро-ЕОМ. Для цього
просумуємо потужності всіх пристроїв, що входять до складу даної мікро-ЕОМ,
що у свою чергу одержуємо підсумовуванням потужностей мікросхем, що входять
до складу цих пристроїв.
|Прилад |ІМС |потужність, |Кол-во,|Сум. |Сум. |
| | |Вт |шт. |потужність |потужність|
| | | | |для |для ЕОМ, |
| | | | |приладів,Вт |Вт |
|БОД |К1804ВС2 |1,75 |16 |32,45 |319,07 |
| |К1804ВР1 |0,57 |5 | | |
| |К1804ВР2 |1,6 |1 | | |
|БОП |К1804ВН1 |1,525 |8 |13,325 | |
| |К1804ВРЗ |0,12 |1 | | |
| |К1533ИД7 |0,005 |1 | | |
| |К556РТ6 |0,95 |2 | | |
|ОЗП |К541РУ2 |0,5 |512 |259,445 | |
| |К1804ИР2 |0,19 |18 | | |
| |К555ИД7 |0,005 |5 | | |
|БС |К1804ГГ1 |0,48 |1 |0,48 | |
|БМУ |К1804ВУ4 |1,72 |1 |12,37 | |
| |К1804ИР2 |0,19 |11 | | |
| |К556РТ6 |0,95 |9 | | |
| |К555КП6 |0,005 |1 | | |
| |К555ЛП6 |0,005 |1 | | |
Виберемо тактову частоту. Максимальні значення часу затримки поширення
сигналів будуть для модуля БОД и ОЗП.
Тзд.р.Бод= Тзд.р.вс2+ 2 * Тзд.р. bp1 + Тзд.р. вр2 = (120 + 2 * 15 +
60) * 10-9 = 210 нс.
Тзд.р. озу=2Тзд.р. ид7 + Тзд.р. ир2 + Тзд.р. РУ2 =(20 + 45 + 140) * 10-
9 = 205 нс.
Тзд.р. max = mах(Тзд.р. озу, Тзд.р. Бод) == 210 нс. Максимальна тактова
частота з урахуванням додаткових затримок :
F = |1 / Тзд.р. mах| = 1 / (210 * 10-9) | = 4 МГц. Тоді період
проходження тактових імпульсів складе :
Т=1/F=1/(4* 106) =250 нс.
Знайдемо время виконання команд. Тому що команда SE виконується 16+1
циклів, то час ее виконання складе :
tDD = Т * 16 = 4 мкс.
Команда HER виконується за 1+1+16+1=19циклів. Таким чином, час
виконання команди HER складає :
ТhER=Т* 19 =4,75 мкс
7. ВИСНОВОК
У ході виконання курсової роботи була спроектована ЕОМ, що по своїх
параметрах є абсурдною з технічної точки зору. Причиною цього є не коректно
поставлені технічні вимоги:
Завищена розрядність пристрою(64-х розрядна шина даних, це занадто багато
4-х розрядних секційних БІС).
Великий обсяг основної пам'яті, при малій розрядності складових її
елементів, що привело до необхідності використання декількох сотен
мікросхем.
Висока споживана потужність ( близько 60 А, при напрузі питання 5 В
виходить 350 Вт )
Не узгодження параметрів за коефіцієнтом розгалуження ( до одного виходу
навантажується під несколько сотень входів).
У такий спосіб такая ЕОМ фізично не може функціонувати..
Додаток 2
Мікропрограма для команди HER
|K1804BC2 |K1804BУ4 |K1804BP2 |K1804 |RAM |
| | | |BH1 | |
|MI[8..5] |MI[4..1] |MI0 |EA |OE|IE|OEB|MI[3..0]|RLD |I[12..6] |MI |EI |CS |WR |
| | | | |Y |N | | | | |[3..0] | | |/ |
| | | | | | | | | | | | | |RD |
|xxxx |xxxx |x |1 |1 |1 |1 |1110 |1 |xxxxxxx |1101 |x |0 |1 |
|xxxx |xxxx |x |1 |1 |1 |1 |1110 |1 |xxxxxxx |1101 |x |1 |x |
|xxxx |xxxx |x |1 |1 |1 |1 |1110 |1 |xxxxxxx |1101 |x |0 |1 |
|0100 |0011 |0 |1 |0 |0 |0 |1110 |1 |00xxxxx |1101 |x |1 |x |
|xxxx |xxxx |x |1 |1 |1 |1 |0100 |0 |xxxxxxx |1101 |x |0 |1 |
|1000 |0100 |x |x |0 |0 |0 |1000 |1 |0010000 |1101 |x |1 |x |
|xxxx |xxxx |x |1 |1 |1 |1 |1110 |1 |xxxxxxx |1101 |x |1 |x |
|xxxx |xxxx |x |1 |1 |1 |1 |1110 |1 |xxxxxxx |1101 |x |1 |x |
|xxxx |xxxx |x |x |x |x |x |0010 |1 |xxxxxxx |1101 |x |1 |x |
Мікропрограма для команди SE
|K1804BC2 |K1804BУ4 |K1804BP2 |K1804BH1 |RAM |
|IEN[16-1] |MI[8..5]|MI[4..1]|MI0 |EA|OE|IE|OE|MI[3..0] |RL|I[12..0] |MI |EI |CS |WR |
| | | | | |Y |N |B | |D | |[3..0| | |/ |
| | | | | | | | | | | |] | | |RD |
|111110000001111 |0100 |0001 |0 |1 |0 |0 |0 |1110 |1 |01xxxxx001011 |1101 |0 |0 |1 |
|111111111111111 |xxxx |xxxx |x |1 |1 |1 |1 |1011 |1 |00xxxxx001010 |1101 |0 |1 |x |
|111110000001111 |0011 |0000 |0 |0 |0 |1 |0 |1110 |1 |01xxxxx001010 |1101 |0 |1 |x |
|111111111110000 |1111 |0100 |0 |0 |0 |1 |0 |1110 |1 |00xxxxx001011 |1101 |0 |1 |x |
|111110000000000 |xxxx |xxxx |x |0 |0 |1 |0 |0010 |1 |xxxxxxxxxxxxx |1101 |0 |1 |x |
Скорочення і позначення.
. ОЗП – оперативний запам'ятовуючий пристрій;
. ЕОМ – електронна обчислювальна машина;
. ПЗП – постійний запам'ятовуючий пристрій;
. П – процесор;
. МС – мікросхема;
. ЗП – зовнішній пристрій;
. МП – мікропрограма;
. МПУ – мікропрограмний пристрій управління;
. БПП – блок переривань;
. xx - р – xx- розрядний;
. ПУ – пристрій управління;
. БОД – блок обробки даних
. СЗВО - схема збереження і видачі ознак
. ОП - операційний пристрій
. ППА - перетворювач початкової адреси
. ПА – перетворювач адреси
. СУАМ - схема управління адр. мікрокоманд
. ПЗП МК - ПЗП мікрокоманд
. СУА ОЗП - схема управління адресою ОЗП
Література
1. Балашов Е. П., Пузанков Д. В. Микропроцессоры и микропроцессорные
системы : Учеб. пособие для вузов
2. Комплект БИС К1804 в процессорах и контроллерах /В. М. Мещеряков, И. Е.
Лобов, С. С. Глебов и др.; Под ред. В. Б. Смолова. - М.: Радио и
связь, 1990.
3. Хвощ С. Т. И др. Микропроцессоры и микро-ЭВМ в системах автоматического
управления : Справочник
4. Применение интегральных микросхем памяти : Справочник /А. А. Дерюгин,
В. В. Цыркин, В. Е. Красовский и др.;
5. О.Н. Лебедев Микросхемы памяти и их применение. Радио и связь, МРБ,
выпуск 1152.
-----------------------
Нормализація
Додаток 1
Структурна схема
ШУ
ОЗП
Схема формування адреси ОЗП
Рг. мікрокоманд
ПЗП мікрокоманд
Схема управління адресами мікрокоманд
Пам`ять початкових адрес
Рг КОП
Пам`ять початкових адрес
обробників переривань
Блок переривань
Рг. А
Рг. D
Операційне устройство
Схема збереження й видачі признаків
БОД
ШД
ША
Додаток 3. БОД
Додаток 4. БПП
Додаток 5. БМУ
Додаток 6. ОЗП
Додаток 7. БВС
Реферат на тему: Чего не может компьютер, или Труднорешаемые задачи
Липецкий государственный педагогический институт
РЕФЕРАТ
Тема: Чего не может компьютер, или
труднорешаемые задачи
Студентки группы Л-2-2
Осадчей Ольги
Липецк, 1998
СОДЕРЖАНИЕ
О задачах и алгоритмах 3
Эвристические алгоритмы 5
Электронный подход к искусственному интеллекту 5
Другие подходы к искусственному интеллекту 7
Заключение 9
ЛИТЕРАТУРА 10
Машина должна работать,
человек – думать.
Принцип 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гг.
ЛИТЕРАТУРА
1) Дрейфус Х. Чего не могут вычислительные машины.- М.: Прогресс, 1979.
2) Винер Н. Кибернетика и общество.-М: ИЛ, 1979
3) Компьютер обретает разум. М., Мир., 1990 В сборнике: Психологические
исследования интеллектуальной деятельности. Под.ред. О.К.Тихомирова.- М.,
МГУ, 1979
4) Пекелис В. Кибернетика от А до Я. М.,1990.
Липский В. Комбинаторика для программиста. М.,Мир, 1990.
| |
