Виконавці алгоритмів. Формальне виконання алгоритму. Комп'ютер як формальний виконавець алгоритмів (програм).

Тип уроку: комбінований.

Цілі уроку:

Ввести поняття «об'єкт-виконавець»;

Ознайомити учнів із третьою стадією розробки алгоритму;

Запровадити поняття «Програма»;

Ознайомити з правилами оформлення та виклику програми;

Навчити вирішувати завдання складання програм з лінійним алгоритмом.

Завдання уроку:

Пізнавальні :

Організувати роботу учнів з вивчення та первинного закріплення знань шляхомколективної та самостійної практичної діяльності.

Розвиваючі:

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

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

Виховні:

Формування інформаційної культури, уміння та навичок колективного та самостійного оволодіння знаннями;

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

Хід уроку

Організаційний етап

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

Оголошення теми та цілей уроку. Повторення матеріалу

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

Фронтальне опитування:

Перерахуйте етапи розв'язання задачі за допомогою ПК (постановка задачі, визначення умов, побудова моделі задачі, опис алгоритму розв'язання задачі, вибір оптимального середовища для розв'язання, опис алгоритму за допомогою вибраних програмних засобів, тестування розв'язання задачі, при необхідності – корекція розв'язання задачі)

Перерахуйте основні властивості алгоритму (дискретність, точність, зрозумілість, масовість, результативність)

Перерахуйте основні форми представлення алгоритмів (словесний, графічний, програмний, табличний)

Пояснення нового матеріалу:

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

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

Розрізняють формальних та неформальних виконавців. Формальний виконавець одну й ту ж саму команду виконує однаково. Неформальний виконавець може виконувати команду.

Формальні виконавці надзвичайно різноманітні, але кожного з них можна зазначити такі характеристики: коло розв'язуваних завдань (призначення), середу, систему команд і режим роботи.

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

Середовище виконавця - Умови, за яких можливе виконання алгоритму.

Система команд виконавця (СКІ) – перелік дій, який здатний зрозуміти та виконати виконавець.

Система відмов виконавців – перелік відмов, що виникає, при неможливості виконання алгоритму в конкретних умовах.

Режими роботи виконавця – режим безпосереднього та програмного управління. Безпосереднє управління – виконавець чекає на команди від людини і кожну команду виконує негайно. Програмне керування - виконавцю задається послідовність команд (програма), а потім виконує команди в автоматичному режимі. Деякі виконавці працюють лише в одному з режимів.

Виконавці, що зустрічаються в завданнях - Коник, Калькулятор, Маятник, Черепашка, Стрілка, Красильник, Стрілочка, Черепаха, Водолей і. ін.

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

Впередn(деn– ціле число) – викликає пересування наnкроків у напрямку руху – у тому напрямку, куди розгорнуто її голову та корпус.

Праворучm(деm– ціле число) – викликає зміну напрямку руху наmградусів за годинниковою стрілкою.

Запис ПовториK [<Команда1> <Команда2> … <Команда n>] – означає, що послідовність команд у дужках повторитьсяkразів.

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

Повтори 12[ Направо 45 Наперед 20 Направо 45]

Відповідь:

Приклад: Система команд Обчислювач складається із двох команд, яким присвоєно номери:

1 – віднімай 1

2 – помножити на 3

При записі алгоритму для стислості вказуються лише номери команд. Наприклад, алгоритм 21212 означає наступне

Помножити на 3

Віднімай 1

Помножити на 3

Віднімай 1

Помножити на 3

За допомогою цього алгоритму число 1 перетворено на 15: ((1*3-1)*3-1)*3=15

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

Під час виконання кожної такої команди Робот переміщається до сусідньої клітини у вказаному напрямку. Якщо ж у цьому напрямку між клітинами стоїть стіна, то робот руйнується.

Що станеться з Роботом якщо він виконає послідовність команд: праворуч, вниз, праворуч, вниз, праворуч. Почавши рух із клітини А. Яку послідовність команд треба виконати Роботу, щоб переміститися із клітини А у клітину В, не зруйнувавшись від зустрічі зі стінами?

Алгоритм, представлений зрозумілою Виконавцю мовою, називаютьпрограмою .

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

Основна складність розробки програм для комп'ютера полягає у створенні чи знаходженні алгоритму. Складання програми за відомим алгоритмом називають кодуванням.

Програмування (кодування) – процес складання програми для комп'ютера.

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

Підсумок уроку:

Діалог:

Що нового Ви дізналися на уроці?

Яка практична значимість досліджуваного питання?

Які позитивні моменти уроку?

Побажання

Дякую за роботу на уроці!

Виділяють два типи виконавців: формальні та неформальні.

Формальний виконавець ту саму команду завжди виконує однаково.

Неформальний виконавець може виконувати команду по-різному.

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

Як правило, людина виступає у ролі неформального виконавця.

Формальними виконавцями є технічні пристрої.

Людина у ролі неформального виконавця сама відповідає за свої дії.

За дії формального виконавця відповідає керуючий ним об'єкт.

Розглянемо докладніше безліч формальних виконавців. Формальні виконавці надзвичайно різноманітні, але кожного з них можна вказати коло розв'язуваних завдань, середу, систему команд, систему відмов та режими роботи.

1. Коло розв'язуваних завдань. Кожен виконавець створюється на вирішення певного класу завдань.
2. Середовище виконавця. Область, обстановку, умови, у яких діє виконавець, прийнято називати середовищем цього виконавця.
3. Система команд виконавця. Припис виконання окремої закінченої дії виконавця називається командою. Сукупність всіх команд, які можуть бути виконані деяким виконавцем, утворює СКІ – систему команд виконавця.
4. Система відмов виконавця. Відмова «не розумію» виникає тоді, коли виконавцю подається команда, яка не входить до його СКІ. Відмова «не можу» виникає тоді, коли команда зі СКІ не може бути виконана в конкретних умовах середовища.
5. Режими роботи виконавця. Для більшості виконавців передбачено режими безпосереднього та програмного управління. У першому випадку виконавець очікує команд від людини і кожну команду негайно виконує. У другому випадку виконавцю спочатку задається повна послідовність команд (програма), а потім виконує всі ці команди в автоматичному режимі. Ряд виконавців працює лише в одному із названих режимів.

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

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

Додаток №1

АЛГОРИТМ І ВИКОНАВЦІ

Мета вивчення: освоїти поняття алгоритм, виконавець, мати уявлення про алгоритм як модель діяльності виконавця.

Алгоритм

Визначення алгоритму

Алгоритмом називається точне опис послідовності дій, спрямованих рішення поставленої завдання.

Алгоритм – це модель діяльності виконавця алгоритму.

Ціль

Алгоритм розробляється на вирішення конкретної завдання чи класу задач.

Форма запису алгоритму

Алгоритми можуть бути записані як таблиці, нумерованого списку, програми, блок-схеми.

Складається алгоритм для конкретного виконавця, зрозумілою йому мовою.

Виконавці алгоритмів

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

Рис.1 Виконавець – технічний пристрій

Рис.2. Виконавець – тварина

Рис.3. Виконавець – людина

Команда

Припис виконання окремої закінченої дії виконавцем називається командою. Команди, які має виконати конкретний виконавець, утворюють систему команд виконавця.

Формальні та неформальні виконавці алгоритму

Виконавці алгоритму можуть бути формальними та неформальними.

Неформальний виконавець може виконувати одну й ту саму команду по-різному. У ролі неформального виконавця виступає людина, тварина. Неформальний виконавець сам відповідає за свої дії.

Мал. 4. Неформальний виконавець

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

Рис.5. Формальний виконавець

Середовищем виконавця прийнято називати область, обстановку, умови, у якій діє виконавець. Наприклад, середовищем виконавця Креслярє координатна площина.

Мал. 6. Середовище виконавця Чортежник.

Відмови

Розглядаючи середу та систему команд виконавця, можна скласти систему відмов: «не розумію», «не можу». Якщо виконавцю подається команда, яка не входить до його системи команд виконавця, виникає відмова «не розумію».

Команда: «Підігріти бутерброд»

Мал. 7. Відмова «не розумію»

Якщо виконавцю подається команда із системи команд виконавця, що він неспроможна виконати у умовах середовища, виникає відмова «не можу».

Команда: «Йти вперед"

Мал. 8. Відмова «не можу»

Управління виконавцем

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

Виконавці – це об'єкти управління. Керувати ними можна, склавши їм алгоритм.

Два режими керування

Для більшості виконавців передбачено два режими - безпосереднього та програмного управління.

Режим, в якому об'єкт, що управляє, управляє виконавцем в даний момент часу, називається режимом безпосереднього управління.

Мал. 7. Режим безпосереднього управління

Режим, у якому людина керує виконавцем з допомогою підготовленої програми, називається режимом програмного управління.

Мал. 8. Режим програмного управління

Для досягнення мети вивчення параграфа виконай тренінг та перевір себе за допомогою модуля домашнє завдання .

Виконавець – людина, група людей, тварина чи технічний пристрій, здатні виконувати певний набір команд. Приклади: Об'єкт – виконавець!! Кнопка вкл/викл електроживлення на корпусі комп'ютера Перехід на початок Пауза СтопПерехід у кінець Відтворення Система команд виконавця – CD-плеєра

Більш складний виконавець. Працює за програмами, створеними людиною. Програми обирає людина. Машина працює автоматично. Більш складний виконавець. Працює за програмами, створеними людиною. Програми обирає людина. Машина працює автоматично. Виконавець - пральна машина

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

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

Система відмов виконавця Відмова «Не розумію» виникає, якщо подається команда, яка не входить до СКІ. Відмова «Не можу» виникає, якщо команда зі СКІ не може бути виконана у конкретних умовах середовища. ? Пральна машина не може виконати команду «полоскання», якщо до машини не підведено воду. ?

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

Найголовніше Виконавець – це людина, група людей, тварина чи технічний пристрій, здатні виконувати задані команди. Формальний виконавець ту саму команду завжди виконує однаково. До кожного формального виконавця можна зазначити: –коло вирішуваних завдань; -Середовище; -Систему команд; -Систему відмов; -режими роботи.

Математичні засади інформатики

А.Г. Гейн

Навчальний план

№_ГАЗЕТИ	Лекція
	лекція 1.Що таке “математичні засади інформатики”.Чому інформатику нерідко вважають близькою род- ня модницею математики? Чи це правильно? Чи можлива інформатика без математики? Яка математика потрібна для освоєння інформатики? Чи шкільна математика може дати основу для інформатики? Інформація та її кодування.
	Математика кодів. Коди, які виправляють помилки..Економне кодування.Лекція 2 ні автомати. Що первинне: мова чи виконавець? Граматика мови. Розпізнавані мови.
	Універсальні вико-.тели (машина Тьюринга, машина Поста).
	Лекція 3
	Алгоритм та його властивості. Алгоритмічна нерозв'язність. Обчислюваність.Складність. Контрольна робота №1.
	лекція 4.. Графи. Графи та орграфи. У яких цілях вони виникають? Різні властивості графів (ейлеровість, гамільто- новина, планарність, дводольність). Мережі. Потоки у мережах. Подання графів. Основні алгоритми на графах.
	Лекція 5
	Логічні моделі у інформатиці.. Алгебра висловлювань. Булеві функції.Нормальні форми. Повні класи булевих функцій. Релейноконтактні схеми. Вентилі. Математичні моделі процесора та пам'яті комп'ютера. Предикати та стосунки. Реляційна алгебра. Теоретичні засади реляційних СУБД. Мови логічного програмування та його математичну основу. Контрольна робота №2.
23/2007	Лекція 6. Комп'ютерна теорія чисел та обчислювальна геометрія.Навіщо потрібна теорія чисел у комп'ютерних науках? Перегони за простими числами. Як розкласти число на множники? Чим відрізняється теоретична геометрія від
24/2007	обчислювальної? Чому гладко на папері, але коряво на комп'ютері? Основні правила та алгоритми обчислювальної. геометрії.
	Лекція 7

Захист інформації
. Захист символьної інформації. Що потрібно захищати?

Електронний підпис. Системи

верифікації. Криптосистеми із відкритим ключем.

Але чи завжди погано бути формальним виконавцем? Чи буде радий господар вівчарки, коли за командою "Фас!" його чотирилапий друг задумається, чи варто зв'язуватися з бандитом. Або коли літак у відповідь на рух пілотом штурвала продовжить летіти колишнім курсом, бо робити розворот не хочеться. А оператор ядерного реактора, закинувши інструкцію, керуватиме ним по наїті. Погодьтеся, що навіть людині час від часу бути формальним виконавцем просто потрібно. Що стосується пристроїв для автоматичного оброблення інформації, для них неформальний шлях просто неможливий. Нагадаємо, що, як зазначалося в лекції 1, інформатика займається вивченням саме процесів автоматизованої обробки інформації.

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

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

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

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

Отже, під обробкою інформації зручно розуміти будь-яке перетворення її змісту чи форми подання.

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

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

Які математичні моделі застосовують для дослідження формальних виконавців, ми розповімо в цій лекції.

§ 3. Формальний виконавець: автомат Людина дуже досягла успіху у створенні різноманітних пристроїв, виконують ту чи іншу роботу відповідно до чіткої інструкції. При цьому він не повинен постійно перебувати біля цього пристрою, щоб керувати ним. У цьому випадку кажуть, що пристрій виконує роботу автоматично, а такий пристрій називають.

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

Автомати останнього виду часто називають промисловими роботамиЗ погляду інформатики абсолютно байдуже, із чого зроблено автомат. Важливо лише те, що він сприймає деякі сигнали як команди і з кожної команді виконує певну дію, переходячи з одного стану до іншого. Тому вважатимуться, кожен автомат описується набором можливих станів, списком допустимих команд і перерахуванням те, з якого стану який переходить автомат під впливом кожної команди. Наприклад, якщо команд лише дві, їх можна позначити літерами, скажімо, a і 1, і 2, ..., b, або цифрами, стани автомата - буквами

q

qm

Автомат можна описати й іншою інформаційною моделлю – орграфом*. Вершинами орграф є стани автомата, дугами - переходи з одного стану в інший. На кожній дузі є позначка, що показує, якою командою здійснюється перехід. Тоді автомат описаний табл. 2, зобразиться так, як показано на Мал. 1.

Таблиця 2

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

2 (К). Зрозуміло, що метою управління автоматом є видача йому такої послідовності команд, яка переводить його з початкового стану в якийсь кінцевий. Оскільки кожна команда позначена літерою, то набір команд, які розуміє цей автомат, можна вважати деяким алфавітомА . Тоді послідовність команд, тобто. програма буде записуватися як слово в цьому алфавіті. Наприклад, слово abа переводить автомат, описаний в табл. 2, з початкового стану q і 1 у стан . Тоді послідовність команд, тобто. програма буде записуватися як слово в цьому алфавіті. Наприклад, слово 4 . іМожна сказати, що слово і 4 .

задає на орграфі даного автомата деякий маршрут зі стану 1 у станБезліч всіх тих слів, які переводять автомат з початкового стану в один із кінцевих станів, утворює формальну мову. Ця мова називається мовою, що розпізнається даним автоматом.

. Якщо для деякої мови існує хоча б один автомат, який цю мову розпізнає, то таку мову називають Мал.розпізнаваним іна і 2 - і розуміє дві команди, які позначені цифрами 0 і 1. Легко збагнути, що мову, що розпізнається цим автоматом, складається з тих і тільки тих слів, які містять парну кількість одиниць і будь-яку кількість нулів.

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

було для нього мовою, що розпізнається? Відповідь негативна. Зрозуміло, що метою управління автоматом є видача йому такої послідовності команд, яка переводить його з початкового стану в якийсь кінцевий. Оскільки кожна команда позначена літерою, то набір команд, які розуміє цей автомат, можна вважати деяким алфавітом = {промисловими роботами, Тому вважатимуться, кожен автомат описується набором можливих станів, списком допустимих команд і перерахуванням те, з якого стану який переходить автомат під впливом кожної команди. Наприклад, якщо команд лише дві, їх можна позначити літерами, скажімо,}, , і = {Теорема. Нехай a n b n , де n , іпробігає багато всіх натуральних чисел). Безліч

не є мовою, що розпізнається. Запис a n , що фігурує у формулюванні цієї теореми, означає, що літераа , деповторена

разів. , іДоказ теореми використовує одне із найважливіших математичних методів - від неприємного. Отже, припустимо, що - Розпізнаваний мову. Отже, існує такий автомат, який будь-яким словом цієї мови перекладається деякий кінцевий стан.Нехай цей автомат має kстанів. , іРозглянемо слово і a k b k і. Воно належить мові , що фігурує у формулюванні цієї теореми, означає, що літераі, отже, перекладає цей автомат із початкового стану і 1 в деякий кінцевий стан - Розпізнаваний мову. Отже, існує такий автомат, який будь-яким словом цієї мови перекладається деякий кінцевий стан. s. , що фігурує у формулюванні цієї теореми, означає, що літераОскільки буква Мал.повторюється не менше разів, ніж кількість станів автомата, знайдеться такий стан і t , яке за перші застосувань літерибуде пройдено двічі (див. застосувань літери + 3). Нехай перший раз автомат перейде в стан t внаслідок застосування a u + 3). Нехай перший раз автомат перейде в стан , а наступного разу опиниться в тому ж стані після застосування v і. Розглянемо слово і a k , і b k , і.

Зрозуміло, що застосування цього слова до початкового стану і 1 переведе його в той же кінцевий стан і s. Це означає, що це слово також розпізнається даним автоматом і, отже, має належати мові і. , що фігурує у формулюванні цієї теореми, означає, що літераАле в безлічі такого слова немає. Отримана суперечність показує, що зроблене припущення не так, тобто. автомата, для якого ця безліч служила б мовою, що розпізнається, не існує.Мал. 3. Маршрут на орграфі автомата від початкового стану 3). Нехай перший раз автомат перейде в стан 1 до кінцевого стану

s (до стану

t літера

1. Якими двома інформаційними моделями може бути представлений автомат?

2. Що таке мова, що розпізнається цим автоматом?

3. Яка мова називається розпізнаваною?

4. Для автомата, зображеного на Мал. 1, визначте, в якому стані він перебуватиме після виконання послідовності команд

а) abba; в) babaabaaa;

б) ababbabbb; г)* Теорема. Нехай.

5. Для автомата, зображеного на Мал. 2, складіть опис у формі таблиці.

6. Побудуйте як графа інформаційну модель автомата, заданого табл.

3.

Таблиця 3 Мал. 4?

7. Яка мова над двосимвольним алфавітом (0, 1) розпізнається автоматом, зображеним на

Мал. 4 промисловими роботами, Тому вважатимуться, кожен автомат описується набором можливих станів, списком допустимих команд і перерахуванням те, з якого стану який переходить автомат під впливом кожної команди. Наприклад, якщо команд лише дві, їх можна позначити літерами, скажімо, 8. Яка мова над двосимвольним алфавітом (

) Розпізнається автоматично, заданим табл. 3?

9. Зобразіть у вигляді графа інформаційну модель автомата, який би розпізнавав мову над алфавітом (0, 1), що складається з усіх слів, що містять рівно 5 одиниць, що йдуть поспіль.

10. Зобразіть у вигляді графа інформаційну модель автомата, який розпізнавав би мову над алфавітом (0, 1), що складається з усіх слів, що містять рівно 5 одиниць.

11. Зобразіть у вигляді графа інформаційну модель автомата, який розпізнавав би мову над алфавітом (0, 1), що складається з усіх слів, що починаються з одиниці (тобто цей автомат відрізняє натуральні числа, записані в двійковій системі числення, від довільних послідовностей символів 0 та 1). , і 1 , , і 2 , , і 3 , , і 12. Серед наведених нижче мов

4 , визначених над двосимвольним алфавітом (1; 2), вкажіть розпізнавані. Для кожної з мов, що розпізнаються, побудуйте автомат, що його розпізнає, для кожної з мов, що не розпізнаються, доведіть, що він не розпізнається. а) L

1 складається з усіх слів, які є парними натуральними числами, що починаються з цифри 1; а)б)

2 складається з усіх слів, кількість одиниць у яких - це натуральне число, що закінчується цифрою 3; , ів)

3 складається з усіх слів, у яких кількість двійок є простим числом; , іг)

4 складається з усіх слів, які є натуральні числа, що діляться на 3.

13. У чому з погляду інформатики полягає різниця "у житті за законами" і "в житті за поняттями"?

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

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

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

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

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

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

Одне з найважливіших питань теоретичної інформатики звучить так: існує такий формальний виконавець, за допомогою якого можна імітувати будь-якого формального виконавця? Такого виконавця природно назвати універсальним. Легко зрозуміти, що як фізичний пристрій універсальний виконавець не існує - адже інформація може кодуватися як завгодно довгими повідомленнями, а будь-який фізичний носій є кінцевим. Якщо ж вести мову про універсального виконавця як ідеальний об'єкт, то виявляється, що відповідь на дане питання позитивна. І отриманий він був майже одночасно і незалежно двома видатними вченими - А. Т'юрінгом (1936 р.) та Е. Постом (1937 р.).

Запропоновані ними виконавці відрізнялися один від одного, але виявилося, що вони можуть імітувати один одного, а головне – імітувати взагалі будь-якого формального виконавця.

Універсального виконавця прийнято називати машиною. Також прийнято надавати машинам імена їх винахідників. Так що універсального виконавця, придуманого А. Т'юрінгом, називають машиною Тьюринга; виконавця, описаного Е. Постом, - машиною Поста. Пізніше з'явилися інші універсальні виконавці, наприклад, машина Мінського.

Отже, можна вважати, що ми маємо повідомлення, записане в деякому алфавіті, і його потрібно перетворити на інше повідомлення. , що фігурує у формулюванні цієї теореми, означає, що літераЗвичайно, написати інструкцію формальному виконавцю для обробки конкретної пари повідомлень – справа нехитра. Але вже знаєте, що реальний інтерес представляють інструкції (тобто. алгоритми), дозволяють вирішувати цілий клас однотипних завдань, - так зване “властивість масовості алгоритму”. Наприклад, таке завдання: до будь-якого повідомлення приписати праворуч ще один заздалегідь заданий символ. Якщо, скажімо, послідовність однакових символів виступає кодом натурального числа - кількість символів у послідовності і є натуральне число, що кодується, - то фактично йдеться про створення алгоритму збільшення числа на 1. , що фігурує у формулюванні цієї теореми, означає, що літера 1 , , що фігурує у формулюванні цієї теореми, означає, що літера 2 , ..., , що фігурує у формулюванні цієї теореми, означає, що літераПриродно вважати, повідомлення записано на стрічку. Більш того, зручно уявляти собі цю стрічку розділеної на однакові клітини, і в кожній клітині записано рівно один символ повідомлення. Оскільки повідомлення можуть бути як завгодно довгими, то стрічку домовимося уявляти собі нескінченною. , що фігурує у формулюванні цієї теореми, означає, що літера 0; Мал. 5.

1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. Для конкретної пари даних (тобто двох чисел) запис на стрічці може виглядати, наприклад, як показано на

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

4 вона відзначена Ї. Цю клітинку називатимемо початковою.

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

0 і розташовується навпроти початкової клітини. Зрозуміло, що метою управління автоматом є видача йому такої послідовності команд, яка переводить його з початкового стану в якийсь кінцевий. Оскільки кожна команда позначена літерою, то набір команд, які розуміє цей автомат, можна вважати деяким алфавітом = {, що фігурує у формулюванні цієї теореми, означає, що літера 1 , , що фігурує у формулюванні цієї теореми, означає, що літера 2 , ..., , що фігурує у формулюванні цієї теореми, означає, що літераТаким чином, машина Тьюринга формально описується набором двох алфавітів: ) та = {і 0 , і 1 , і 2 , ..., і Q Зрозуміло, що метою управління автоматом є видача йому такої послідовності команд, яка переводить його з початкового стану в якийсь кінцевий. Оскільки кожна команда позначена літерою, то набір команд, які розуміє цей автомат, можна вважати деяким алфавітом m). Алфавіт називаєтьсязовнішнім та служить для запису вихідних повідомлень, алфавіт Q називаєтьсявнутрішнім і описує набір станів зчитувально-друкуючого пристрою. Зображати машину Т'юрінга будемо так, як показано на. 6.

Мал

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

q k

Отже, допустимі дії машини Тьюринга такі:

Записати будь-який символ зовнішнього алфавіту в секцію стрічки (символ, що був там доти, затирається);

Зміститися у сусідню секцію;

Змінити стан на один із позначених символом внутрішнього алфавіту;

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

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

Фактично команди виглядають так:

a i переводить автомат, описаний в табл. 2, з початкового стану j - в секцію, що оглядається, записати промисловими роботами i , змістити праворуч (до наступної секції) і перейти в стан і j;

a i q j - в секцію, що оглядається, записати промисловими роботами i , зміститися вліво і перейти в стан і j;

a i S і j - в секцію, що оглядається, записати aiзупинитися і перейти в стан і j.

Для дій машина Тьюринга має операційно-логічний блок. У цього блоку є два входи: через один з них надходить інформація про те, який символ стоїть в осередку, через інший - інформація про те, в якому стані знаходиться машина на даному кроці своєї роботи. Ця інформація однозначно визначає, яку саме команду потрібно виконати машині. Оскільки команда може містити вказівку на виконання трьох дій – запису символу на стрічку, зміщення та зміни стану – операційно-логічний блок має три виходи: запис символу A, зміщення Mта зміна стану ) та(Див. Мал. 7).

Мал. 7. Операційно-логічний блок машини Тьюринга

Оскільки у цього блоку всього лише два входи, його реакцію на символи, що подаються на них, зручно представляти у вигляді прямокутної таблиці, в якій рядки та стовпці позначені символами зовнішнього та внутрішнього алфавітів відповідно (див. табл. 4). У клітини таблиці записуються команди. Якщо машина знаходиться навпроти клітки, де написано a i, а її стан при цьому є q j, то виконується команда, що стоїть на перетині рядка, позначеного символом ai, і стовпця, позначеного символом q j.

Таблиця 4

Цю таблицю називають функціональною схемоюданої машини; вона і грає роль інструкції (програми) для машини Тьюринга. З неї, зокрема, видно, якими є зовнішній і внутрішній алфавіти машини.

Нехай, наприклад, на стрічці записана послідовність із певної кількості однієї й тієї ж символу “*”. Тоді функціональна схема, наведена у табл. 5, змушує машину Тьюринга збільшити на одну кількість зірочок у цій послідовності.

Таблиця 5

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

Запитання та завдання

1. Якого формального виконавця називають універсальним?

2. Що таке машина Тьюринга?

3. Чим одна машина Тьюринга відрізняється від іншої?

4. Що називають функціональною схемою машини Тьюринга?

5. Чи правильно, що машина Тьюринга з написаною нею функціональною схемою є кінцевим автоматом?

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

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

8. Робота машини Тьюринга описана наступною функціональною схемою:

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

Мал. 8

Мал. 9

9. На стрічці машини Тьюринга записано рядок, що складається з кількох поспіль символів “*”, за ними слідує кілька символів “#”, а в кінці рядка стоїть символ “е” (один з можливих варіантів такого рядка наведено на Мал. 5).

Мал. 10

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

10. Нехай зовнішній алфавіт складається із символу “ промисловими роботами 0 ” та цифр 0, 1, 2, ..., 9. На стрічку записується натуральне число. Придумайте машину Тьюринга і складіть для неї функціональну схему, згідно з якою це число буде збільшено на 1.

11. Нехай зовнішній алфавіт складається із символу “ промисловими роботами 0 ” та цифр 0, 1, 2, ..., 9. На стрічку записано натуральне число. Складіть функціональну схему для машини Тьюринга, за допомогою якої на стрічці буде записано суму цифр цього числа. Відповідь потрібно записати правіше вихідного числа, відокремивши від нього пропуском.

Мал. 11

P.S.Відчути себе в ролі машини Тьюринга недаремно, але втомлює. Ми рекомендуємо завдання 8 та 9 виконати вручну. Що стосується завдань 10 та 11, то ручне тестування складених вами функціональних схем може виявитися неефективним. У зв'язку з цим ми пропонуємо скористатися комп'ютерною реалізацією машини Тьюринга, створеної Р.Зартдінова. Її можна отримати на сайті газети "Інформатика" ( inf.1september.ru). промисловими роботамиОсь як, наприклад, виглядає на цій машині функціональна схема із завдання 8 в) - відмінності полягають у тому, що замість букви S зображено дорожній знак, а замість символу “

0 ” пишеться “_” (при занесенні команди у клітину таблиці натискати, проте, треба клавішу “пробіл”, а чи не “_”). Програма має докладну довідку про те, як з нею працювати. Інтерфейс цієї програми дуже простий. Крім того, опис цієї реалізації машини Тьюринга ви можете знайти в газеті "Інформатика" № 8, 2006. Там же ви знайдете розбір ще кількох завдань на програмування машини Тьюринга; Треба лише пам'ятати, що у них використовується дещо інша (що зовсім неважливо) система команд. * Нагадаємо, що граф - це сукупність точок, званихвершинами , і ліній, що з'єднують деякі вершини. Якщо лініях, що з'єднують вершини, зазначено напрям, то граф називаєтьсяорієнтованим (скороченоорграфом ), а лінії називаються йогодугами .У звичайному графі, тобто. неорієнтованому, лінії, що з'єднують вершини, називаються