Аналітична машина Беббіджа.Перші програми Ади Лавлейс.

Аналітична машина, спроектована видатним англійським математиком і винахідником Чарльзом Беббіджем в 1833р. Аналітична машина повинна була мати такі функціональні вузли: 1. «Склад» для зберігання чисел (пам'ять); 2. «Млин», арифметичний пристрій (процесор); 3. Пристрій, що управляє послідовністю операцій в машині (пристрій управління); 4. Пристрої введення і виведення даних. Пам'ять машини вміщала до 100 40-ка розрядних чисел. Ці числа повинні були зберігатися в пам'яті, поки до них не дійде черга в арифметичному пристрої. Результат операції або відправлялися в пам'ять, або роздруковувалися. Інструкції, команди, вводилися в Аналітичну машину за допомогою перфокарт. На вхід машини повинні були надходити два потоки перфокарт, які Беббідж назвав операційними картами і картами змінних: перші управляли процесом обробки даних, які були записані на других. Інформація заносилася на перфокарти шляхом пробивки отворів. З операційних карт можна було скласти бібліотеку функцій. Крім цього машина за задумом автора, повинна була містити пристрій друку і пристрій виводу результатів на перфокарти для подальшого використання. Можна сміливо сказати, що Беббідж першим використовував перфокарти для введення-виведення інформації в машину. Перші програми для аналітичної машини були розроблені леді Адою Лавлейс, дочкою відомого англійського поета Чарльза Байрона. Її вважають першою у світі програмісткою. Ада Лавлейс є автором першої теоретичної роботи в теорії обчислювальних машин, уведені нею поняття і терміни дотепер застосовуються у програмуванні. Аналітична машина так і не була побудована. Створення аналітичної машини стало справою життя Беббіджа, проте реалізувати цей проект йому не вдалося.

 

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

Склад машини Поста

Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру. Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп’ютерах.

Каретка може пересуватися вздовж стрічки вліво і вправо. Коли вона нерухома — вона перебуває навпроти однієї комірки стрічки. У такому випадку говорять, що каретка оглядає одну комірку. За одиницю часу каретка може зробити одну із трьох дій: стерти мітку, поставити мітку, зробити рух до сусідньої комірки. Стан машини Поста складається із стану стрічки і розташування каретки. Дії каретки підпорядковані програмі, яка складається з пронумерованого набору команд (команди можна представляти як рядки програми). Команди бувають шести типів: 1. записати 1 (мітку), перейти до i-го рядка програми;

2. записати 0 (стерти мітку), перейти до i-го рядка програми;

3. переміститися вліво, перейти до i-го рядка програми;

4. переміститися вправо, перейти до i-го рядка програми;

5. зупинка;

6. якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми.

Наведемо перелік неприпустимих дій, які ведуть до аварійної зупинки машини:

· спроба записати 1 (мітку) в заповнену комірку;

· спроба стерти мітку в порожній комірці;

· нескінченне виконання (зациклення).

Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: 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), та по сьогодні залишається домінуючою схемою організації ЕОМ загального призначення.

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

Авторство концепції, покладеної в основу фон-нейманівської архітектури, насправді належить колективу авторів (фон Нейман, Дж. Екерт, Дж. Маклі), які працювали над створенням однієї з перших ЕОМ загального призначення з можливістю перепрограмування —, а потім вже глибше реалізована в машині EDVAC (1952). Самі принципи були сформульовані в декількох публікаціях. Власне, головною проблемою, яка поставала перед «піонерами» обчислювальної техніки була надзвичайна складність введення алгоритму обчислень в ЕОМ, для чого доводилось мати справу з численними перемикачами, тумблерами, роз'ємами та іншими комутуючими елементами. Це ускладнювало процес, призводило до величезної кількості помилок та аж ніяк не додавало цим машинам універсальності.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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