Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Конспект лекцій Основи дискретної математики

Конспект лекцій Основи дискретної математики




Сторінка1/11
Дата конвертації03.04.2017
Розмір1.66 Mb.
ТипКонспект
  1   2   3   4   5   6   7   8   9   10   11


Конспект лекцій
Основи дискретної математики
Розділ 5

Тема 1



Оглавление


Розділ 5. ТЕОРІЯ АВТОМАТІВ 2

Тема 1. Скінчені автомати, їх аналіз і синтез 4

Лекція 5.1. Скінчені автомати: визначення і загальна арактеристика 5

Лекція 5.2. Задача аналізу функціонування скінченних автоматів і формальні засоби її вирішення 10

Лекція 5.3.

Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.
Тео́рія автома́тів - логіко-математична теорія, об'єктом дослідження якої є абстрактні дискретні автомати - покрокові перетворювачі інформації; розділ теоретичної кібернетики.
Скінче́нний автома́т - особливий різновид автомату - абстракції, що використовується для описання шляху зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Його особливістю є скінченність множини станів автомату.
Еквівалентність станів скінчених автоматів 20

Лекція 5.4.

Логічна еквівалентність (еквіваленція) - двомісна логічна операція, що має значення «істина» тоді і тільки тоді, коли обидва операнди мають однакове значення. В інших випадках еквіваленція буде хибною.
Еквівалентне розбиття і мінімальна форма автомата 28

28

Лекція 5.5. Абстрактний синтез скінчених автоматів 40



Лекція 5.6. Структурний синтез скінчених автоматів 52

Лекція 5.7. Експерименти з розпізнавання станів і автоматів 57




Розділ 5. ТЕОРІЯ АВТОМАТІВ



Поява і швидке поширення інформаційних технологій і комп’ютеризованих систем, насамперед керування, проектування і навчання, безпосередньо зобов’язане комп’ютерам. Теорія автоматів виникла як реакція на проблеми аналізу і синтезу дискретних систем і пристроїв переробки інформації. Її результати традиційно використовуються при проектуванні компонентів компютерної техніки.
Компонент (англ. component, нім. Komponente f) - різновид, складова частина чогось.
Тради́ція - досвід, звичаї, погляди, смаки, норми поведінки і т. ін., що склалися історично і передаються з покоління в покоління; звичайна, прийнята норма, манера поведінки, усталені погляди, переконання когось; узвичаєння, узвичаєність, неписаний закон.
В історії розвитку компютерної техніки виділяють чотири визначальних періоди:

  1. домеханічний;

  2. механічний;

  3. електромеханічний;

  4. електронний.

Основна проблема, яку розв’язують творці комп’ютерної техніки, полягає в автоматизації обчислень. Уже в 17 столітті була запропонована низка механічних лічильних машин, що спочатку виконували операції додавання, віднімання, а потім – ще й множення і ділення.
Пері́од (грец. περίοδος - кружний шлях, обертання, чергування) може означати: Проміжок часу, протягом якого повторюється якийсь циклічний процес: Період коливання Період обертання Горизонтальний ряд хімічних елементів, розміщених у порядку зростання їх атомних мас, що розпочинається лужним металічним елементом, та закінчується інертним газом.
Ді́лення (також діління́)- в математиці, бінарна операція, що обернена множенню.
Проблема - складне теоретичне або практичне питання, що потребує розв'язання, вивчення, дослідження. Проблема - об'єкт (питання, недолік чи потреба чогось,завада від надлишку чи наявності чогось, процес) явище збуджуючого характеру як стимул діяльності спонукаючого характеру - незадоволений попит чи нереалізовані потреби (нестача або відсутність, надлишок або наявність чого-небудь), дефект, вада, чи загроза що змушує цілеспрямовано ліквідувати проблему шляхом уникнення взаємодії чи зміни стану об'єкту, себе чи свого ставлення до подій.
Столíття або сторіччя - проміжок часу, дорівнює ста рокам. Згідно з сучасним літочисленням (від «Різдва Христового»), століття починається «першим» роком, а закінчується кратним сотні. Наприклад, двадцяте сторіччя почалося 1 січня 1901 року, а закінчилося 31 грудня 2000 року.
Додавання - бінарна арифметична операція, суть якої полягає в об'єднанні математичних об'єктів.
Меха (англ. mecha, mechs, mech) – літературний і кінематографічний піджанр наукової фантастики, в якому широко поширені транспортні чи бойові засоби, що зазвичай контролюються пілотом. Мехи також часто з'являються в аніме і інших жанрах - наприклад, кіберпанк або антиутопія - за участю фантастичних і футуристичних елементів.
Обчи́слення - є гілкою математики, зосередженою на функціях, похідних, інтегралах, і нескінченному ряду чисел. Цей предмет являє собою важливу частину сучасної математичної освіти. Воно складається з двох основних галузей - диференціального і інтегрального численнь, які пов'язують основні теореми обчислення.
Відніма́ння - двомісна математична операція, обернена додаванню.
Цікаво відзначити, що в першій з них, машині Шиккарда, основними елементами були: підсумовуючий і помножувальний пристрій та пристрій для збереження проміжних результатів, аналоги яких можна знайти в сучасних комп’ютерах. Перші успіхи у створенні механічних лічильних машин привели Б.Паскаля до висновку, що розум людини діє автоматично, а ряд розумових дій виконується механічно. Однак на механічних машинах деякі операції в процесі обчислень повинні були виконуватися вручну.

І тільки в 19 столітті Ч. Беббедж висунув ідею цілком автоматичної обчислювальної машини з програмним керуванням.

У́спіх (англ. success; нім. Erfolg n; рос. успех), також до́спіх - позитивний наслідок роботи та справи, змагання, життя тощо; значні досягнення, удача, талан. позитивний результат діяльності, факт вищого досягнення поставленої мети.
При́стрій (англ. device, appliance, нім. Vorrichtung f, Einrichtung f) - обладнання, конструктивно завершена технічна система, що має певне функціональне призначення і за допомогою якої виконується яка-небудь робота або спрощується, полегшується певний процес.
Програмування - процес проектування, написання, тестування, зневадження і підтримки комп'ютерних програм. Програмування поєднує в собі елементи інженерії (існує навіть відповідна спеціальна галузь інженерії - програмна інженерія (англ. software engineering)
Числове́ програ́мне керува́ння (ЧПК) (англ. Computer numerical control) - комп'ютеризована система керування, яка зчитує командні інструкції спеціалізованої мови програмування (наприклад, G-код) і керує приводами метало-, дерево- чи пластмасообробних верстатів та верстатним оснащенням.
Ця ідея полягала в тому, що машина повинна уміти виконувати лічильні операції, операції збереження і друку, а послідовність операцій, тобто те, що ми зараз назвали б програмою, повинна задавати людина. Ця послідовність визначає роботу спеціального пристрою, що керує машиною.

Реалізація ідей Ч.Беббежа стала можливою тільки в 20 столітті. Спочатку з’явилася перша у світі універсальна автоматична цифрова обчислювальна машина (ЦОМ) із програмним керуванням Ц-З на електромагнітних реле, а в 1946р. була продемонстрована електронна обчислювальна машина (ЕОМ) ЕНІАК.

Електромагні́т (англ. electromagnet, нім. Elektromagnet m) - пристрій, що створює магнітне поле під час проходження електричного струму. Зазвичай електромагніт складається з обмотки і феромагнітного осердя, який набуває властивостей магніту при проходженні по обмотці струму.
Послідо́вність - функція визначена на множині натуральних чисел яка набуває значення на об'єктах довільної природи. f : N → X \,\rightarrow \,\!X} .
Програма (фр. programme письмове оголошення, порядок денний, від грец. prógramma вказівка) - заздалегідь затверджена (визначена) дія.
Реле (рос. реле, англ. relay, нім. Relais n, Wächter m) - електричний комутаційний апарат, який автоматично виконує певні перемикання контрольованого ним електричного кола.
Електро́нна обчи́слювальна маши́на (ЕОМ) - загальна назва для обчислювальних машин, що є електронними (починаючи з перших лампових машин, включаючи напівпровідникові тощо) на відміну від електромеханічних (на електричних реле тощо) та механічних обчислювальних машин.
Перша ЕОМ у континентальній Європі була створена в Києві під керівництвом академіка Сергія Лебедєва.
Керівн́ицтво - (адміністрування, розпорядництво) є однією з функцій управління, а в умовах командно-адміністративної системи саме тією функцією, що разом з контролем включила в себе всі інші функції.
Континентальна Європа - це широко використовуване позначення, яке вказує на територію Європи, розташовану на європейському континенті (материк Євразія). У поняття не включені європейські країни, розташовані на островах (Велика Британія, Ісландія, Ірландія та ін.).

Процеси проектування і створення ЕОМ виявилися надзвичайно складними, адже комп’ютер складається з великої кількості взаємодіючих елементів.

Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Велику роль у проектуванні комп’ютерів зіграло уявлення про них, як про пристрої зі скінченою множиною станів, які функціонують, переходячи визначеним чином із стану в стан, і визначають результат на виході, якщо відомі стан і вхід.
Уявлення: Розуміння чого-небудь, знання чого-небудь, яке ґрунтується на досвіді, одержаних відомостях, якихось даних тощо. У психології та філософії - чуттєво-наочний образ предметів або явищ дійсності, що зберігається і відтворюється у свідомості людини поза безпосереднім впливом їх на органи чуттів.
Тому були введені і названі автоматами математичні об’єкти, поведінка яких визначається таким чином. Це дозволило використовувати автомати при проектуванні комп’ютерів, адже на них можна було до створення комп’ютера моделювати його поведінку в тій чи іншій ситуації. Під впливом прикладних проблем дослідження автоматів розвинулися у окрему гілку дискретної математики, яка отримала назву „теорія автоматів”.
Множина́ - одне з основних понять сучасної математики. Строго воно не визначається, але може бути дано інтуїтивне визначення множини як сукупності певних і різних об'єктів довільної природи, яка розглядається як одне ціле.
Проектува́ння - процес створення проекту, прототипу, прообразу майбутнього об'єкта, стану та способів його виготовлення. У проектуванні застосовують системний підхід, який полягає у встановлені структури системи, типу зв'язків, визначені атрибутів, аналізуванні впливів зовнішнього середовища.
Моделювання (англ. scientific modelling, simulation, нім. Modellieren n, Modellierung f, Simulation f) - це метод дослідження явищ і процесів, що ґрунтується на заміні конкретного об'єкта досліджень (оригіналу) іншим, подібним до нього (моделлю).
Поведі́нка - родовий термін, який охоплює різні реакції живого організму чи групи організмів.
Дискре́тна матема́тика - галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру.
Результати цієї теорії широко використовувуються в науці і техніці при аналізі і синтезі систем з дискретними станами, зокрема, систем керування, зв’язку, комп’ютерів тощо.
Те́хніка (від грец. techne - мистецтво, майстерність) - сукупність засобів, створених людством для обслуговування своїх потреб виробничого і невиробничого характеру. У техніці матеріалізовані знання і виробничий досвід, накопичені людством у процесі розвитку суспільного виробництва.
Си́нтез - процес з'єднання або об'єднання раніше розрізнених речей або понять в ціле або набір. Термін походить від грец. σύνθεση - поєднання, приміщення разом (σύν - з, разом і θεση - стан, місце). Синтез є способом зібрати ціле з функціональних частин як антипод аналізу - способу розібрати ціле на функціональні частини.
Система керування, також Система управління (англ. control system) - систематизований набір засобів впливу на підконтрольний об'єкт для досягнення цим об'єктом певної мети. Об'єктом системи керування можуть бути як технічні об'єкти так і люди.



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

Прийнято розглядати вхідні і вихідні сигнали як символи в деяких алфавітах, а автомат асоціювати з деяким пристроєм, що в загальному випадку має структуру, зображену на рисунку 5.1.
Вхідні́ (рос. Входные) - група невеликих островів у затоці Петра Великого Японського моря. Знаходиться за 120 м на північний схід від мису Вхідного при вході до бухти Астаф'єва. Адміністративно належить до Хасанського району Приморського краю Росії.
Гра́фіка (нім. Graphik, грец. graphikos «написаний») - вид образотворчого мистецтва, для якого характерна перевага ліній і штрихів, використання контрастів білого і чорного та менше, ніж у живописі, використання кольору.
Сигна́л - зміна фізичної величини (наприклад, температури, тиску повітря, світлового потоку, сили струму тощо), що використовується для пересилання даних. Саме завдяки цій зміні сигнал може нести в собі якусь інформацію.
Си́мвол (англ. symbol символ) - знак, сутність, яка позначає іншу сутність.
Абе́тка (А́збука, Алфаві́т) (грец. Αλφάβητο, лат. Abecedarium) - розташована в певному порядку сукупність літер, що застосовуються для запису певної мови.


Рис. Узагальнена структура автомату



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


Автомат функціонує в дискретні моменти часу, здійснюючи так звані такти, виконання яких починається з читання голівкою зчитування/запису чергового символу зі вхідної стрічки. Кожен такт полягає в переході від однієї конфігурації автомату до іншої конфігурації. Під конфігурацією автомату будемо розуміти комбінацію стану і вмісту вхідної стрічки та памяті. Перехід від деякої конфігурації Сi до конфігурації Сj визначає функція переходів автомату. Функція переходів визначає наступний стан автомату і символи, що записуються у память, використовуючи в якості аргумента: стан автомата; символ вхідної стрічки в клітинці, на яку вказує голівка зчитування/запису на момент початку такту; символ в клітинці памяті, на яку вказує голівка зчитування/запису памяті на момент початку такту. Далі клітинку вхідної стрічки, на яку вказує голівка читання/запису вхідної стрічки, будемо називати поточною клітинкою вхідної стрічки, а клітинку пам’яті, на яку вказує голівка зчитування/запису пам’яті, - поточною клітинкою пам’яті. У залежності від особливостей вхідної стрічки і пам’яті розрізняють чотири типи автоматів:

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


  • автомати з магазинною пам’яттю;

  • лінійно-обмежені автомати;

  • машини Т’юрінга.

Автомати останніх трьох типів зазвичай поєднують у клас нескінчених автоматів.

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

Крім того, автоматні моделі використовуються в комп’ютерній лінгвістиці, де вони природним шляхом доповнюють моделі граматик породження.

Грама́тика (грец. γραμματική, від γράμμα - «літера», «написання») - термін, який вживається в двох пов'язаних значеннях: як будова мови і як розділ мовознавства, що вивчає граматичну будову мови.
Мовозна́вство, також лінгві́стика - наука, що вивчає мову в усій складності її прояву; наука про мову взагалі й окремі мови світу як індивідуальних її представників. Це гуманітарна наука, яка є розділом культурології (нарівні з мистецтвознавством і літературознавством) і філології (нарівні з літературознавством), а також галуззю семіотики.
Дійсно, у процесі комунікації одна сторона формує мовний твір, а інша сторона розпізнає його. Природними моделями для передаючої і приймаючої сторін є відповідно граматика, що породжує мовний твір, і автомат, що розпізнає його. Більш того, проблема трансляції може бути вирішена за допомогою автомата, що виступає тут вже в ролі перетворювача. Можна також указати на те, що автоматні моделі використовуються і для уточнення семантики мов програмування, навести інші приклади розв’язання проблем лінгвістики за допомогою автоматних моделей.
Мо́ва - система звукових і графічних знаків, що виникла на певному рівні розвитку людства, розвивається і має соціальне призначення; правила мови нормалізують використання знаків та їх функціонування як засобів людського спілкування.
Модель (рос. модель, англ. model, нім. Modell n, фр. modèle, від лат. modulus - «міра, аналог, зразок») - відтворення чи відображення об'єкту, задуму (конструкцій), опису чи розрахунків, що відображає, імітує, відтворює принципи внутрішньої організації або функціонування, певні властивості, ознаки чи(та) характеристики об'єкта дослідження чи відтворення (оригіналу).
Перетво́рювач - пристрій, елемент електричних, гідравлічних, пневматичних та інших схем, який перетворює один вид енергії на інший або сприяє цьому.
Сема́нтика мовна (давніше семасіологія) - розділ мовознавства, пов'язаний з лексикологією; вивчає значення (теж у діахронному, іст. перекрої) слів і їх складових частин, словосполук і фразеологізмів. Слово походить від грецького слова σημαντικός (семантікос), «значимий», з σημαίνω (семаіно), «значити, вказувати» та також від σήμα (сема), «знак, позначка, символ».


Наведене вище дозволяє зробити висновок про те, що засоби і методи теорії автоматів повинні скласти важливу частину засобів інженера-системотехніка і тому даний розділ включений у курс.
Ме́тод (від грец. μέθοδος - «шлях крізь») - систематизована сукупність кроків, які потрібно здійснити, щоб виконати певну задачу чи досягти певної мети; поняття тотожне алгоритму дій і технологічному процесу.
У лекціях першої теми даного розділу ми розглянемо скінче
ні автомати, а розгляду нескінчених автоматів буде присвячена наступна тема.
Інжене́рія (від лат. ingenium - здібність, винахідливість; син. - інжиніринг, рідше вживають «інженерна справа», ще рідше «інженерство») - галузь людської інтелектуальної діяльності по застосуванню досягнень науки до вирішення конкретних проблем людства.
Ле́кція (лат. lectio - читання) - основна форма проведення навчальних занять, призначених для засвоєння теоретичного матеріалу.

  1   2   3   4   5   6   7   8   9   10   11



  • Оглавление
  • Розділ 5. ТЕОРІЯ АВТОМАТІВ