Графічне представлення команд машини Поста

n.→m	Крок вправо
n.←m	Крок вліво
n V m	Записати мітку
n X m	Стерти мітку
n? a: b	Переглянути комірку: якщо в комірці знаходиться 0, тоді перейти на команду з номером а, інакше на команду з номером b.
n.!	Зупинка

Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m, де n - порядковий номер команди, K − дія, яка виконується кареткою, m - номер наступної команди, яку необхідно виконати.

З погляду властивостей алгоритмів, найбільший інтерес представляють причини зупинки машини під час виконання програми:

· зупинка за командою «стоп». Така зупинка називається результативною і вказує на коректність алгоритму;

· зупинка при виконанні неприпустимої команди. У цьому випадку зупинка називається безрезультатною;

· машина не зупиняється ніколи. У цьому і у попередньому випадку ми маємо справу з некоректним алгоритмом.

Під початковим станом каретки розумітимемо її положення навпроти порожньої комірки лівіше за найлівішу мітку на стрічці.

Машина Тюрінга

У 1936 році Аланом Тюрінгом було запропоновано новий підхід до формалізації поняття алгоритму. Цей підхід було реалізовано у вигляді моделі обчислювальної машини, яка стала носити назву машини Тюрінга.

Машина Тюрінга складалась з таких елементів:

• Стрічка(нескінченна в одному напрямі)

• Каретка для читання запису

• Пристрій керування із скінченною кількістю станів

Машиною Тюрінга будемо називати формальну систему, яка завжди задається четвіркою об’єктів T={A, Q, P, I}

А- множина символів алфавіту (порожнє місце і скінченна кількість інших символів)

Q={q₀, q₁…- скінченна кількість} - множина станів

q₀ – зупинка

q₁ – стан запуску

A Q=

P- програма для машини

I=q₁a_i – початковий стан для символу

Для машини Тюрінга командою будемо називати слово з 3 можливих:

1) q_ia_z -> q_ka_y Стан q_i і символ a_z на стан q_k і символ a_y

2) q_ia_z -> q_kL При спостереженні q_i і символу a_z змінуємо на стан q_k і рух вліво

3) q_ia_z -> q_kR -||- рух вправо

Правила побудови:

1. За жодних умов команда не повинна починатись з стану q0

2. Будь-яка команда, що присутня в команді для машини Тюрінга не може містити двох команд з однаковими рівними частинами

Для машини Тюрінга існує один єдиний аварійний стан – відсутність стану зупинки або до виконання команд із цим станом команда жодного разу не доходить.

Для машини Тюрінга програму можна записувати одним із трьох способів:

1. У вигляді послідовності команд

2. У вигляді направлених графів

3. У вигляді автоматної таблиці

 

50. Клод Елвуд Шеннон - американський інженер і математик, його роботи є синтезом математичних ідей з конкретним аналізом надзвичайно складних проблем їх технічної реалізації.

Є засновником теорії інформації, що знайшла застосування в сучасних високотехнологічних системах зв'язку. Шеннон зробив величезний внесок в теорію ймовірнісних схем, теорію автоматів і теорію систем управління - області наук, що входять в поняття " кібернетика.

Робота Шеннона "Теорія зв'язку в секретних системах" (1945) з грифом "секретно", яку розсекретили й опублікували тільки лише в 1949 році, послужила початком великих досліджень в теорії кодування та передачі інформації, і, на загальну думку, надала криптографії статус науки. Саме Клод Шеннон вперше почав вивчати криптографію, застосовуючи науковий підхід. У цій статті Шеннон визначив основоположні поняття теорії криптографії, без яких криптографія вже немислима. Важливою заслугою Шеннона є дослідження абсолютно стійких систем і доказ їх існування, а також існування криптостійкий шифрів, і необхідні для цього умови. Шеннон також сформулював основні вимоги, що пред'являються до надійних шифрів.

Теореми Шеннона

· Пряма і зворотна теореми Шеннона для джерела загального вигляду - про зв'язок ентропії джерела та середньої довжини повідомлень.

· Пряма і зворотна теореми Шеннона для джерела без пам'яті - про зв'язок ентропії джерела і досяжною ступені стиснення за допомогою кодування з втратами і подальшого неоднозначного декодування.

· Пряма і зворотна теореми Шеннона для каналу з шумами - про зв'язок пропускної здатності каналу та існування коду, який можливо використовувати для передачі з помилкою, яка прагне до нуля (при збільшенні довжини блоку).

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

 

51. Aрхітекту́ра фон Неймана — архітектура електронних обчислювальних машин, основною відмінністю якої від інших подібних архітектур є спільне зберігання даних та машинних команд в комірках однієї й тієї ж пам'яті, що унеможливлює їх розрізнення за способом представлення або кодування. Названа так на честь відомого математика та теоретика обчислювальної техніки Джона фон Неймана (John von Neumann), та по сьогодні залишається домінуючою схемою організації ЕОМ загального призначення.

Передумови створення та першоджерела

Авторство концепції, покладеної в основу фон-нейманівської архітектури, насправді належить колективу авторів (фон Нейман, Дж. Екерт, Дж. Маклі), які працювали над створенням однієї з перших ЕОМ загального призначення з можливістю перепрограмування — ENIAC (1943, зокрема фон Нейман був консультантом в цьому проекті), а потім вже глибше реалізована в машині EDVAC (1952). Самі принципи були сформульовані в декількох публікаціях, серед яких слід виділити таку як Burks, A. W., Goldstine, H. H., and von Neumann, J., 1945 («Попередня дискусія про логічний устрій електронного обчислювального інструмента») та Von Neumann, J., 1946 («Перший варіант доповіді про EDVAC»).

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

Фон Нейман в своїй «Попередній дискусії» запропонував натомість зберігати алгоритм разом з даними для обчислень в пам'яті обчислювальної машини, що б давало можливість по-перше оперативно перепрограмувати систему, а по-друге поводитись з командами як з даними, проводити над ними такі ж обчислювальні операції, тобто фактично відкривало можливість для написання програм, які самі себе модифікують (і це було зовсім не екзотикою на той час, а практичною необхідністю). Таким чином пропонувалась організація обчислень, яка дійсно робила обчислювальну машину універсальним інструментом.

Така структура унеможливлювала розрізнення команд від даних в пам'яті машини за структурою представлення, але фон Нейманом було вказано, що таке розміщення можливе «за умови, якщо машина якимось чином зможе розрізнити їх». Для того, щоби вказати машині на те, де є команди, а де є дані, була згодом запропонована концепція лічильника команд (program counter), в якому зберігалась адреса поточної команди, а після її виконання замінювалась адресою наступної. Адреси ж самих операндів (даних) зберігались безпосередньо в команді.

Також в «Попередній дискусії» була досить докладно розглянута чотирикомпонентна структура обчислювального інструмента, яка зараз вважається класичною структурою фон-нейманівської машини, а саме: арифметичний пристрій, пристрій управління, пам'ять та пульт оператора.

Формальне визначення

Обчислювальна машина є машиною з архітектурою фон Неймана, якщо:

Програма та дані зберігаються в одній загальній пам'яті.

Кожна комірка пам'яті машини ідентифікується унікальним номером, який називається адресою.

Різні слова інформації (команди та дані) розрізняються за способом використання, але не за способом кодування та структурою представлення в пам'яті.

Кожна програма виконується послідовно, починаючи з першої команди, якщо немає спеціальних вказівок. Для зміни цієї послідовності використовуються команди передачі управління.

Класична структура машини фон Неймана

Машина фон Неймана, як і практично кожна сучасна ЕОМ загального призначення, складається з чотирьох основних компонентів:

Операційний пристрій (ОП), який виконує команди з визначеного набору, який називається системою (набором) команд, над порціями інформації, яка зберігається відокремленій від операційного пристрою пам'яті (хоча сучасні архітектури мають в складі операційного пристрою додаткову пам'ять (зазвичай банк регістрів), в якій операнди зберігаються порівняно короткий час безпосередньо в процесі проведення обчислень.

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

Запам'ятовуючий пристрій (ЗП) — масив комірок з унікальними ідентифікаторами (адресами), в яких зберігаються команди та дані.

Пристрій вводу-виводу (ПВВ), який забезпечує зв'язок ЕОМ з зовнішнім світом, різними пристроями, які передають інформацію на переробку в ЕОМ та приймають результати.

Принцип функціонування

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

Перед початком виконання програми в лічильник записується адреса її першої команди. Визначення адреси наступної команди відбувається за одним з наступних сценаріїв:

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

Якщо поточна команда — команда передачі управління (команда умовного або безумовного переходу), яка змінює послідовний хід виконання програми, то в лічильник примусово записується адреса тої команди, яка була замовлена при виконанні переходу, де б вона не знаходилась.

 

Створення першої ЕОМ ENIAC.

Машина ЕНІАК (Electronic Numerical Integrator and Computer) була створена в кінці 1945 р. Джоном Еккертом і Джоном Моклі. Машина була створена для військових цілей. Перш за все призначалася для вирішення завдань балістики. Але в підсумку вона виявилася здатною вирішувати завдання із самих різних областей.

В ЕНІАКу в якості основи компонентної бази застосовувалися вакуумні лампи. Загалом комплекс містив 17468 ламп, 7200 кремнієвих діодів, 1500 реле, 70000 резисторів і 10000 конденсаторів. Споживана потужність — 150 кВт. Обчислювальна потужність — 300 операцій множення або 5000 операцій додавання на секунду. Вага — 27 тонн. Обчислення відбувалось у десятковій системі. Така велика кількість ламп почасти пояснювалося тим, що ЕНІАК мав працювати з десятковими числами.

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

ENIAC працював до 2 жовтня 1955 року, коли його вимкнули назавжди. Невдовзі комп'ютер був розібраний, окремі його панелі вдалося зберегти в музеях США та Великобританії, зокрема таких як Лондонський науковий музей, Музеї американської історії, Музеї комп'ютерної історії, Смітсонський інститут та інших.

 

53. ВІНЕР, Норберт (Wiener, Norbert) (1894-1964), американський математик. Народився 26 листопада 1894 в г.Колумбія Домашнім освітою Норберта займався батько. у віці трьох років він почав читати і писати, в одинадцять закінчив середню школу, в чотирнадцять - Тафтс-коледж. Навчався у Гарвардському університеті, в 17 років став магістром мистецтв, в 18 - доктором філософії по спеціальності "математична логіка". По закінченні університету отримав стипендію для поїздки в Європу. Першу математичну роботу Вінер опублікував в 1913. У 1915 отримав місце асистента на кафедрі філософії в Гарварді. Займався журналістикою, писав статті для енциклопедії, намагався викладати. У 1919 нарешті отримав місце на кафедрі математики в Массачусетському технологічному інституті. У 1932 отримав звання професора МТІ.

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

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

У 1945-1947 Вінер зацікавився системами зі зворотним зв'язком і проблемами передачі, зберігання і переробки інформації. Нову науку - загальну теорію управління і зв'язку - він назвав кібернетикою. Вперше слово "кібернетика" як термін, що відноситься до управління в широкому сенсі, застосував Платон в 4 в. до н.е., а в 19 в. Ампер запропонував називати цим ім'ям науку про управління людським суспільством. У 1948 вийшла книга Вінера "Кібернетика", жваво сприйнята світовим науковим співтовариством. Під впливом висловлених у ній ідей виникло чимало наукових напрямків і з'явилася маса наукових робіт.

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

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

Ці рекомендації разом з пропозиціями щодо їх практичного використання були спрямовані доктору Ванноверу Бушу (на той момент провідний розробник аналогових машин для американських військових) Так, швидкодія електронної лампи зараз вже нікого не влаштовує, але поступова відмова від використання механічних частин, навіть в жорстких дисках, спостерігається і понині. Складно переоцінити внесок Норберта Вінера і його колег в it. Вже в 40х роках минулого століття ці люди були здатні не тільки провести теоретичні дослідження загальної теорії управління, але й отримати цікаві практичні результати:

Система який пророкує управління артилерійським вогнем. Прилад, що дозволяє читати книги сліпим. Машина для гри в шашки, яка дозволяє обігравати свого програміста через 20-30 годин гри з ним. Конструювання протезів рук, що дозволяє інвалідам отримувати зворотний зв'язок і виконувати такі прості дії як підняття склянки з водою.

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

Вінеру належать роботи але теорії ймовірностей і статистиці, по рядах і інтегралах Фур'є, по лінійним просторам Банаха, за теорією потенціалів, теорії чисел, теоремам Таубера, квазіаналітіческім функціям, інтегралу Лебега та інші. Він багато займався прикладними проблемами - прицільно зенітної артилерії, телефонним зв'язком та радіо, радаром, обчислювальними і аналітичними машинами, автоматичними заводами, електроенцефалографія, вивченням патологічних судом (клонуса) і т. д. Вінер, нині професор математики Массачусетського технологічного інституту, широкій публіці став відомий як автор книг "Кібернетика" (1948),

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

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

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

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

Серед тих, хто збирався в ті дні в МТІ поспілкуватися з Вінером і один з одним, були і майбутні творці перших проектів Мережі, реалізованих вже після його смерті.

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

 

54. Покоління ЕОМ. Перша повністю електронна обчислювальна машина Ениак була побудовано в США в 1946 році. Її розміри були величезні: більш 30 м у довжину й 85 м по займаному обсягу. Вага машини рівнялася вазі чотирьох африканські слонів — приблизно 30 тоннам. Зберігання й обробка даних уній здійснювалися за допомогою 18 тисяч електронних ламп. У нашій країні перша ЕОМ була побудована в 1951році.

В 1953 році наша промисловість стала випускати електронну обчислювальну машину «Стріла». Вона складалася з десятків великих металевих шаф, у яких перебували сотні ламп. Поруч стояли потужні трансформатори, що забезпечували потрібну напругу для ламп. Електричні лампи при роботі сильно нагріваються. Щоб охолоджувати тисячі ламп перших комп'ютерів, були потрібні потужні вентиляційні установки. Обчислювальна машина «Стріла» разом з допоміжним устаткуванням займала площу в 500 квадратних метрів. Цього вистачило б на 10 квартир.

Гігантські комп'ютери на електронних лампах 50-х років XX століття склали перше покоління обчислювальних машин.

Через десятиліття, на початку 60-х років на зміну електронним лампам прийшли транзистори. З ними зв'язана поява другого покоління ЕОМ.

Метали — срібло, мідь, алюміній — проводять електричний струм. Їх називають провідниками. Стекло, порцеляна, пластмаса струм не проводять. Це ізолятори. А от деякі рідкі речовини — кремній, германій, селенів — то проводять електричний струм, то не проводять, залежно від його напрямку. Ці речовини наполовину ізолятори, наполовину провідники. Їх називають напівпровідниками. Вони й стали основою для транзисторів — маленьких кристаликів напівпровідника із двома металевими вусиками-проводками. Транзистор був значно менше лампи, важив кілька грамів і практично не грівся. До того ж один транзистор був здатний замінити 40 ламп. Машини стали значно менше, надійніше, їхня швидкодія зросла.

В Україні першою малою ЕОМ стала машина «Днепр-1», серійне виробництво якої було налагоджено на заводі «Арсенал» (м. Київ). ЕОМ «Днепр-1» передувала унікальній за своєю архітектурою машині «Мир-1», розробленій в 1965 р. в Інституті кібернетики (керівник В.М. Глушков). Машина «Мир-1» та її наступна модифікація «Мир-2» передбачались для інженерних розрахунків, які виконував на ЕОМ сам користувач без допомоги оператора.

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

З розвитком мікроелектроніки з'явилася можливість розміщати на кристалі не одну, а тисячі інтегральних схем. В 1980 році на кристалі площею близько 1,5 см² удалося розмістити центральний процесор невеликої ЕОМ. Почалася епоха мікрокомп'ютерів.

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