Машина Тюрінга як універсальний виконавець алгоритмів та її застосування в процесі поглибленого вивчення алгоритмізації і основ програмування старшокласниками

Размещено на http://www.allbest.ru/

Машина Тюрінга як універсальний виконавець алгоритмів та її застосування в процесі поглибленого вивчення алгоритмізації і основ програмування старшокласниками

Ящик Олександр Богданович

асистент кафедри комп'ютерних технологій

Тернопільський національний педагогічний університет імені Володимира Гнатюка, м. Тернопіль, Україна

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

Ключові слова: алгоритмізація та основи програмування; поглиблене вивчення; виконавець алгоритму; програмні засоби; машина Тюрінга.

алгоритм тюрінг математичний логічний

1. ВСТУП

Постановка проблеми. Інформатика наразі є одним із засобів формування не тільки освітнього, а й розвивального й інтелектуального потенціалу особистості учнів, а однією з найперспективніших сфер сучасної діяльності - алгоритмізація та програмування. Застосування знань і вмінь у цій сфері відкривають для учнів широкі можливості в навчанні й майбутній професійній діяльності. Загальноосвітня мета сучасного вивчення шкільного курсу інформатики полягає в освоєнні учнями її фундаментальних понять. Зокрема, у процесі поглибленого вивчення алгоритмізації та основ програмування, значну увагу варто приділяти розвитку системно-логічного мислення учнів і формуванню складових системи інформатичних компетентностей [3, с. 4; 10; 9, с. 16-25].

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

Створюючи алгоритм чи програму, учень повинен передбачати їх виконання. Проте часто, через певні помилки, неточності результат не відповідає очікуванням учня. Протиріччя, яке виникло, змушує його аналізувати свою роботу і знаходити помилки. Для розвитку мислення поява «протиріччя» - це сигнал появи проблеми, нерозв'язної за допомогою вже відомих інтелектуальних дій, сигнал для включення мислення як самостійного осмислення предмета [2, с. 21-30.]. Відповідно, це сприяє стимулюванню мислення учнів і систематизації вже наявних знань з метою досягнення чогось нового. Попри це, різноманітність виконавців алгоритмів і мов програмування спонукає учня чітко формулювати свою думку рідною мовою, а тоді вже записувати її з допомогою мови конкретного виконавця.

Аналіз останніх досліджень і публікацій. Дослідженню машини Тюрінга і проблемі її використання у вивченні інформатики присвячено праці відомих вітчизняних і зарубіжних учених (М. І. Жалдак, Ю. С. Рамський, М. В. Рафальська [3], В. Н. Пільщіков, В. Г. Абрамов, А. А. Виліток, І. В. Горячая [7], А. В. Сідоров [8], М. А. Умрик [9], Ю. В. Триус, А. Ю. Дяченко[12], М. М. Фаліна [13] та ін.).

Описуючи різноманітні алгоритми для машин Тюрінга і стверджуючи реалізованість усіляких композицій алгоритмів, А. Тюрінг переконливо показав розмаїтість можливостей використання запропонованої ним конструкції, що дало змогу йому виступити з такою тезою: «Всякий алгоритм може бути реалізований відповідною машиною Тюрінга» [13, с. 12-15]. Це основна гіпотеза теорії алгоритмів у формі Тюрінга. Одночасно ця теза є формальним визначенням алгоритму. Завдяки їй можна доводити існування або не існування алгоритмів, створюючи відповідні машини Тюрінга або доводячи неможливість їх побудови. Завдяки цьому з'являється загальний підхід до пошуку алгоритмічних рішень.

Досвід показує, що для формування складових компетентностей з алгоритмізації та програмування за поглибленого вивчення інформатики в старших класах доцільно розглянути на уроках машину Тюрінга. У багатьох підручниках з інформатики під чпс вивчення поняття і властивостей алгоритму використовують фрази такого змісту: «... існує багато різних способів для запису одного і того ж алгоритму, наприклад, запис у вигляді тексту, запис у вигляді блок-схеми, запис якою-небудь алгоритмічною мовою, подання алгоритму у вигляді машини Тюрінга або машини Поста ...» [4]. На жаль, фрази, де згадується машина Тюрінга, не є поширеними в загальноосвітній школі. Без сумніву, обсяг годин, що відводяться на вивчення алгоритмів, не завжди дає змогу включати в цю тему ще й вивчення способів запису алгоритму у вигляді машини Тюрінга. Однак ця тема вкрай цікава, важлива і корисна для школярів, які особливо захоплюються інформатикою. Тема «Машина Тюрінга» може вивчатися в 10-11-х класах у рамках теми «Алгоритм. Виконавці алгоритму», також на гуртковій роботі з обдарованими дітьми, у профільному навчанні інформатики та бути безпосереднім продовженням вивчення формальних виконавців. Складання програм для машини Тюрінга для розв'язування доцільно дібраних задач сприяє розвитку системно-логічного мислення, дає змогу реалізовувати міжпредметні зв'язки (особливо інформатики і математики), формувати складові алгоритмічної культури учнів.

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

У процесі навчання учнями набуваються і закріпляються такі знання, вміння і навички:

знання про склад машини Тюрінга, принципи її роботи;

реалізація базових алгоритмічних структур на машині Тюрінга;

навички побудови машин Тюрінга для розв'язування навчальних задач;

закріплення і вдосконалення знань і вмінь з алгоритмізації;

ознайомлення з поняттям алгоритмічно нерозв'язної проблеми.

2. МЕТОДИ ДОСЛІДЖЕННЯ

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

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

Інша справа, якщо треба довести, що алгоритму розв'язування певного класу задач не існує. Саме тут і потрібне строге математичне уточнення поняття алгоритму. Поняття алгоритму в його загальному вигляді належить до числа основних, невизначених понять, тому всілякі уточнення поняття алгоритму призводять, взагалі кажучи, до деякого звуження цього поняття. Отже, на роль уточнення може претендувати таке уточнення, коли у нас буде переконання в тому, що для кожного алгоритму в інтуїтивному сенсі може бути вказаний еквівалентний йому уточнений алгоритм [8, с. 12].

3. РЕЗУЛЬТАТИ ДОСЛІДЖЕННЯ

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

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

Машина Тюрінга - абстрактний виконавець (абстрактна обчислювальна машина), яка була запропонована Аланом Тюрінгом у 1936 р. для формалізації поняття алгоритму. Машина Тюрінга є розширенням скінченого автомата і, згідно з тезою Черча-Тюрінга, здатна імітувати всіх інших виконавців (за допомогою задання правил переходу), що будь-яким чином реалізують процес покрокового обчислення, в якому кожен крок обчислення достатньо елементарний [5].

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

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

До складу машини Тюрінга входить нескінченна в обидві сторони стрічка (можливі машини Тюрінга, які мають кілька нескінченних стрічок), поділена на комірки, й управляючий пристрій, здатний перебувати в одному з безлічі станів - автомат (читаючий елемент для зчитування / запису, керований програмою). Число можливих станів управляючого пристрою точно задане. Управляючий пристрій може переміщатися вліво і вправо по стрічці, читати і записувати в комірки стрічки символи деякого скінченого алфавіту. Виокремлюється особливий порожній символ, що заповнює всі комірки стрічки, крім тих з них (скінченого числа), у яких записані вхідні дані. Управляючий пристрій працює згідно з правилами переходу, які представляють алгоритм, реалізований даною машиною Тюрінга. Кожне правило переходу скеровує машину, залежно від поточного стану і спостережуваного в поточній комірці символу: записати в цю комірку новий символ, перейти в новий стан та переміститися на одну комірку вліво або вправо, або залишитися на місці. Деякі стани машини Тюрінга можуть бути помічені як термінальні, і перехід у будь-який з них означає кінець роботи, зупинку алгоритму.

З кожною машиною Тюрінга пов'язані два скінчені алфавіти: алфавіт вхідних сигналів A = {a₀, a₁, ..., a_m} і алфавіт Q = {q₀, q₁, ..., q_p). (З різними машинами Тюрінга можуть бути пов'язані різні алфавіти A і Q). Стан q₀ називається пасивним. Вважається, що якщо машина потрапила в цей стан, то вона закінчила свою роботу. Стан q₁ називається початковим. Перебуваючи в цьому стані, машина починає свою роботу. Вхідне слово розміщується на стрічці по одній букві в розташованих підряд комірках. Ліворуч і праворуч від вхідного слова знаходяться тільки порожні комірки (в алфавіт А завжди входить «порожня» буква а0 - ознака того, що комірка порожня.

Конкретна машина Тюрінга задається перерахуванням елементів множини букв алфавіту A, станів Q і набором правил, за якими працює машина. Вони мають вигляд: q;aj ^ quapdk (якщо читаючий елемент знаходиться в стані q_;, а в комірці записана буква aj, то читаючий елемент переходить у стан q_;1, у комірку замість aj записується aj₁, читаючий елемент робить рух dk, який має три варіанти: на клітинку вліво (L), на клітинку вправо (R), залишитися на місці (N)). Для кожної можливої конфігурації <q;, aj> є тільки одне правило. Правил немає тільки для заключного стану, потрапивши в який, машина зупиняється. Попри це, необхідно вказати кінцевий і початковий стан, початкову конфігурацію на стрічці і розташування читаючого елемента.

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

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

Багатство можливостей машини Тюрінга проявляється в тому, що якщо якісь алгоритми А і В реалізуються машинами Тюрінга, то можна побудувати машини Тюрінга, що реалізують різні композиції алгоритмів А і В. Наприклад, «Виконати А, потім виконати В» або «Виконати А. Якщо в результаті вийшло слово «так», виконати В. В іншому випадку не виконувати В »або« Виконувати по черзі А, В, поки виконується певна умова».

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

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

Під керівництвом учителя учні формулюють, як можна реалізувати основні алгоритмічні структури на машині Тюрінга. Зокрема, для реалізації повного розгалуження достатньо ввести два стани q1 і q2, перебуваючи в яких читаючий елемент розглядає комірку з деяким символом S. Команда Sв стані q1 повинна забезпечити перехід на виконання <серії 1>, а S в стані q2 - на виконання <серії 2>. Аналогічно розглядається команда вибору, циклу.

Таблиця 1

Команда розгалуження - оператор вибору

Таблиця 2

Команда вибору - «case»

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

ВИСНОВКИ ТА ПЕРСПЕКТИВИ ПОДАЛЬШИХ ДОСЛІДЖЕНЬ

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

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

Варпаховский Ф. Л. Элементы теории алгоритмов : учебное пособие / Ф. Л. Варпаховский. - М. : Просвещение, 1970. -- 25 с.

Гетманова А. Д. Логика : для пед. учеб. заведений / А. Д. Гетманова. -- М. : Новая школа, 1995. -- 415 с.

Жалдак М. І. Модель системи соціально-професійних компетентностей вчителя інформатики / М. І. Жалдак, Ю. С. Рамський, М. В. Рафальська// Науковий часопис НПУ імені М. П. Драгоманова. Серія № 2. Комп'ютерно-орієнтовані системи навчання : Зб.наук. праць / Редрада. -- 2009 -- № 7(14). -- С. 3--18.

Как проектировать универсальные учебные действия в начальной школе : от действия к мысли : пособие для учителя / [А. Г. Асмолов [и др.] ; под ред. А. Г. Асмолова. -- М. : Просвещение, 2008. -- 152 с.

Машина Тюрінга [Електронний ресурс] // Навчальні матеріали з інформатики. Основні поняття інформатики. -- Режим доступу : http://www.ua5.org/osnovi/158-mashina-tjuringa.html.

Основи програмування [Електронний ресурс] // Електронна бібліотека Libr.Org.Ua. -- Режим доступу : http://libr.org.ua/books/74.html.

Пильщиков В. Н. Машина Тьюринга и алгоритмы Маркова. Решение задач : учебно-методическое пособие. // В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В. Горячая. -- М. : МГУ, 2006. -- 47 с.

Сидоров А. В. Теория алгоритмов : машины Тьюринга : учеб.-метод. пособие / А. В. Сидоров. -- Кострома : КГУ им. Н. А. Некрасова, 2010. -- 26 с.

Складові інформаційної культури майбутнього вчителя математики / Ю. С. Рамський, М. А. Умрик // Науковий часопис НПУ імені М. П. Драгоманова. Серія № 2 : Комп'ютерно- орієнтовані системи навчання: Зб.наук. праць / Редрада. -- 2011. --№ 11. -- С. 16--25.

Спірін О. М. Інформаційно-комунікаційні та інформатичні компетентності як компоненти системи професійно-спеціалізованих компетентностей вчителя інформатики[Електронний ресурс] // Інформаційні технології і засоби навчання. -- 2009. -- № 5 (13). -- Режим доступу до журн. : http://www.ime.edu.ua.net/em.html.

Техніка обчислень і алгоритмізація : навчальний посібник / І. Ф. Следзінський, А. М. Ломакович, Ю. С. Рамський, Р. І. Зароський. -- К. : Вища школа, 1991 -- 199 с.

Триус Ю. В. Програма-інтерпретатор алгоритмічних систем Маркова, Тюрінга, Поста / Ю. В. Триус, А. Ю. Дяченко // Науковий часопис НПУ імені М. П. Драгоманова. Серія № 2. Комп'ютерно-орієнтовані системи навчання : зб. наук. праць / Редкол. -- К. : НПУ ім. М. П. Драгоманова. -- № 4 (11). -- 2006. -- С. 28--41.

Фаліна М. М. Машина Тьюрінга / М. М. Фаліна // Інформатика. -- № 26. -- 2005. -- С. 12--15.

Ящик О. Б. Компетентнісний підхід у навчанні об'єктно-орієнтованого програмування як основа підготовки учнів старших класів / О. Б. Ящик // Наукові записки ТНПУ ім. В. Гнатюка - Серія «Педагогіка». - 2011. - № 1. - С. 103-108.

Размещено на Allbest.ru