Има два вида изпълнители: официални и неформални.

Официалният изпълнител винаги изпълнява една и съща команда по един и същи начин.

Неформалният изпълнител може да изпълни команда по различни начини.

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

По правило човек действа като неформален изпълнител.

Формалните изпълнители са предимно технически средства.

Човек в ролята на неформален изпълнител носи отговорност за собствените си действия.

Обектът, който го контролира, отговаря за действията на формалния изпълнител.

Нека разгледаме по-подробно набора от официални изпълнители. Формалните изпълнители са изключително разнообразни, но за всеки от тях е възможно да се определи кръг от задачи за решаване, среда, система за управление, система за отказ и режими на работа.

1. Обхват от задачи за решаване. Всеки изпълнител е създаден за решаване на определен клас проблеми.
2. Артистична среда. Районът, обстановката, условията, в които изпълнителят работи, обикновено се наричат ​​средата на дадения изпълнител.
3. Командна система на изпълнителя. Инструкция за извършване на отделно завършено действие на изпълнителя се нарича команда. Съвкупността от всички команди, които могат да бъдат изпълнени от даден изпълнител, образува SKI - системата от команди на изпълнителя.
4. Система за отказ на изпълнител. Отказът „Не разбирам“ възниква, когато изпълнителят получи команда, която не е част от неговия SKI. Отказът „не мога“ възниква, когато команда от SCI не може да бъде изпълнена от него при специфични условия на околната среда.
5. Режими на работа на изпълнителя. За повечето изпълнители са осигурени режими на директен и програмен контрол. В първия случай изпълнителят чака команди от човек и незабавно изпълнява всяка получена команда. Във втория случай на изпълнителя първо се дава пълна последователност от команди (програма), след което той автоматично изпълнява всички тези команди. Редица изпълнители работят само в един от посочените режими.

Разработка на алгоритъм - трудоемка задача, която изисква от човек дълбоки познания и много време. Решаването на проблем с помощта на готов алгоритъм изисква само изпълнителят да следва стриктно дадените инструкции. Изпълнителят не се задълбочава в смисъла на това, което прави и не разсъждава защо постъпва така, а не иначе – той действа формално. Свързана с това е възможността за автоматизиране на човешките дейности:

• процесът на решаване на проблем се представя като последователност от прости операции;
• създава се машина (автоматично устройство), която е способна да изпълнява тези операции в последователността, посочена в алгоритъма;
• човек се освобождава от рутинни дейности, изпълнението на алгоритъма се поверява на автоматично устройство.

Математически основи на компютърните науки

А.Г. Гейн

Учебна програма

№_ВЕСТНИЦИ	Лекция
	Лекция 1.Какво е "математически основи на компютърните науки".Защо компютърните науки често се смятат за подобни на майка на математиката? Това истина ли е? Възможна ли е компютърната наука без математика? Каква математика трябва да владеете? Информатика? Може ли училищната математика да осигури основа за компютърни науки? Информация и нейното кодиране. Математика на кодовете. Кодове за коригиране на грешки. Икономично кодиране.
	Лекция 2.Математически модели на формални изпълнители.Какво е формална обработка на информация? Край- нови машини. Кое е първо: езикът или изпълнителят? Граматика на езика. Признати езици. Универсални версии тели (машина на Тюринг, машина на Пост).
	Лекция 3.Алгоритъм и неговите свойства. Алгоритмична неразрешимост. Изчислимост. Сложност.
	Тест №1.
	Лекция 4. Графики. Графи и диграфи. В какви задачи възникват? Различни свойства на графиките (Ойлер, Хамилтон) новини, планарност, двустранност). мрежи. Потоци в мрежите. Графично представяне. Основни алгоритми върху графики.
	Лекция 5. Логически модели в компютърните науки.Алгебра на предложенията. Булеви функции. Нормални форми. Пълна класове булеви функции. Контактни схеми на реле. Клапани. Математически модели на компютърен процесор и памет. Предикати и отношения. Релационна алгебра. Теоретични основи на релационните СУБД. Езици за логическо програмиране и тяхната математическа основа.
	Тест No2.
	Лекция 6. Компютърна теория на числата и изчислителна геометрия.Защо е необходима теорията на числата в компютърните науки? науки? Надпревара за прости числа. Как да разложа число на множители? Каква е разликата между теоретичната геометрия и компютри? Защо е гладко на хартия, но е тромаво на компютъра? Основни правила и алгоритми на изчисленията геометрия.
23/2007	Лекция 7. Защита на данни. Защита на символна информация. Какво трябва да се защити? Електронен подпис. системи проверка. Криптосистеми с публичен ключ. Защита на графична информация. Математиката на електронните водни знаци.
24/2007	Лекция 8. Основи на методите за преподаване на математическите основи на компютърните науки.
	Финална работа

Лекция 2.
Математически модели на формални изпълнители

„Благодатта е студена в този суетен свят.“ Тази фраза е съставена от компютър, използващ една от първите програми за генериране на текст на естествен език. Но емоцията, предадена от тази фраза, разбира се, е недостъпна за компютър. И компютърът не може да разбере значението на тази фраза. Защото той е просто формален изпълнител.

В нашето обществено съзнание думата „формално” обикновено има негативна конотация. Ние присъждаме презрителния етикет „формалист” на длъжностно лице, което действа единствено въз основа на дадените му указания, без да желае да навлезе в същността на поставения му проблем.

Но винаги ли е лошо да си официален изпълнител? Ще бъде ли щастлив собственикът на овчаря, когато командата „Фас!“ неговият четириног приятел ще се чуди дали си струва да се забърква с бандита. Или когато самолетът, в отговор на движението на кормилото на пилота, продължава да лети по същия курс, защото не искате да правите завой. И операторът на ядрен реактор, изоставил инструкциите, ще го управлява по прищявка. Съгласете се, че дори за човек понякога е просто необходимо да бъде формален изпълнител. Що се отнася до устройствата за автоматична обработка на информация, неформалният път просто не е възможен. Нека припомним, че както беше отбелязано в лекция 1, компютърните науки се занимават с изучаването на процесите на автоматизирана обработка на информация.

Обработката (преобразуването) на информация е доста широко разбиран информационен процес. Обработката на информация се разбира като получаване на нова информация от съществуваща информация или трансформиране на формата на представяне на информация.

Криминалистите са събрали доказателства и са установили извършителя на престъплението. Математикът сравни известните му твърдения и доказа нова теорема. DI. Менделеев, въз основа на информация за химичните свойства на елементите, формулира периодичния закон. Във всички тези примери се появи нова информация в резултат на обработка на информация.

Изчисляването на сумата от две числа също трябва да се признае за обработка на информация - в крайна сметка от две известни данни се получава нова, неизвестна преди. Обработката на информация е например превод на изречение от руски на чужд език.

На пръв поглед има голяма разлика между процесите на обработка на информация, посочени в предишните два параграфа. Основната разлика тук е, че за намиране на престъпник или доказване на нова теорема няма и не могат да бъдат определени строги правила за това как трябва да се обработва първоначалната информация. Както се казва, в тези случаи човек действа евристично. Когато събираме две числа, ние вече се ръководим от строго определени правила. Такава работа може да бъде поверена на техническо устройство, което е в състояние да разбере и изпълни възложените му инструкции. Устройства, които се управляват от инструкции и изпълняват работата си автоматично, се наричат ​​програмируеми и се казва, че изпълняват работата си формално.
По-специално можем да говорим за формална обработка на информация. Изпълнителят, извършващ такава обработка, не трябва да задълбава в смисъла на действията, които извършва; следователно формалната обработка на информацията по правило се отнася до промяна на формата на нейното представяне, а не на нейното съдържание.

Така че под обработка на информация е удобно да се разбира всяка трансформация на нейното съдържание или форма на представяне.

Какъвто и да е методът на обработка на информацията – формален или евристичен, има нещо или някой, който извършва тази обработка. Обикновено се нарича изпълнител.

Официалните изпълнители могат да бъдат структурирани по много различни начини. За изучаването им, както във всяка наука, се използва моделиране. В тази лекция ще ви кажем какви математически модели се използват за изследване на формалните изпълнители.

§ 3. Формален изпълнител: автомат

Човекът е много успешен в създаването на различни устройства, които изпълняват тази или онази работа в съответствие с ясни инструкции. В същото време той вече не трябва постоянно да е близо до това устройство, за да го контролира. В този случай те казват, че устройството извършва работата автоматично и се нарича самото такова устройство автоматично.

В действителност слот машините са много различни. Това може да бъде машина за продажба на билети за влакове, или машина за опаковане на готови продукти, или машина за производство на всякакви части. Автоматите от последния тип често се наричат индустриални роботи.

От гледна точка на компютърните науки няма значение от какво е направена машината. Единственото важно нещо е, че той възприема някои сигнали като команди и за всяка команда извършва някакво действие, преминавайки от едно състояние в друго. Следователно можем да предположим, че всеки автомат е описан от набор от възможни състояния, списък с валидни команди и списък от кое състояние автоматът преминава от кое под въздействието на всяка команда. Например, ако има само две команди, тогава те могат да бъдат обозначени с букви, да речем, аИ b, или с цифри, състоянията на машината - с букви р 1, р 2, ..., qmи можете да изброите опциите за преход от едно състояние към друго с помощта на таблица (вижте Таблица 1).

маса 1

Клетката, разположена в пресечната точка на ред и колона, показва състоянието, в което преминава автоматът, ако е бил в състоянието, посочено в заглавката на същата колона, и е получил командата, посочена в заглавката на същия ред. За всички е ясно, че такава таблица представлява информационен модел на реална машина.

Автоматът може да бъде описан и с друг информационен модел - диграф*. Върховете на орграфа са състоянията на автомата, а дъгите са преходи от едно състояние към друго. Всяка дъга има знак, указващ коя команда се използва за преход. След това машината, описана в табл. 2, ще се покаже, както е показано в ориз. 1.

таблица 2

Едно от състоянията се нарича начално състояние - именно в него се намира машината преди да започне работа. Нека се съгласим винаги да обозначаваме началното състояние р 1. Някои от състоянията са крайни - привеждането на машината в това състояние е целта на управлението на машината чрез една или друга последователност от команди. Например, ако това е машина за продажба на железопътни билети, тогава в първоначалното състояние машината очаква монети да започнат да текат в монетоприемника. Има две крайни състояния: издаване на билет и връщане на парите. Освен това има междинни състояния - отчитане на сумата пари, прехвърлена към машината в този момент. Командите, които прехвърлят машината от едно състояние в друго, са поставяне на монета в монетоприемника, натискане на бутона за издаване на билет или натискане на бутона за връщане на пари. Ще обозначим факта, че това състояние е окончателно с буквата К в скоби до обозначението на това състояние. Например, р 2 (К).

Ясно е, че целта на управлението на автомат е да му се издаде последователност от команди, които го прехвърлят от начално състояние в някакво крайно състояние. Тъй като всяка команда е обозначена с буква, наборът от команди, разбран от тази машина, може да се счита за определена азбука А. Тогава последователността от команди, т.е. програмата ще бъде написана като дума на тази азбука. Например думата абапревежда машината, описана в табл. 2, от първоначалното състояние р 1 в състояние р 4 . Можем да кажем, че думата абадефинира върху диграфа на даден автомат определен маршрут от състоянието р 1 в състояние р 4 .

Наборът от всички тези думи, които прехвърлят автомата от началното състояние в едно от крайните състояния, образува определен формален език. Този език се нарича език, разпознат от тази машина. Ако за определен език има поне един автомат, който този език разпознава, тогава такъв език се нарича разпознаваем.

На ориз. 2 показва автомат с две състояния - р 1 (K) и р 2 - и разбира две команди, които са обозначени с числата 0 и 1. Лесно е да се разбере, че езикът, разпознат от тази машина, се състои от онези и само онези думи, които съдържат четен брой единици и произволен брой нули. С други думи, тази машина изчислява сбора от цифри в число, записано в двоичната бройна система.

Нека сега имаме фиксирана азбука А, И Л- определен набор от думи, съставен от символи на дадена азбука. Винаги ли е възможно да се изгради автомат, така че комплектът Лбеше ли разпознаваем език за него? Отговорът е не.

Теорема. Позволявам А = {а, b}, Л = {a n b n, Където нминава през множеството от всички естествени числа). Няколко Лне е признат език.

Записвайте a n, фигуриращ във формулировката на тази теорема, означава, че буквата Аповтаря се нведнъж.

Доказателството на теоремата използва един от най-важните математически методи – от противно. Така че нека приемем, че Л- разпознат език. Това означава, че има автомат, който може да бъде преведен в някакво крайно състояние с всяка дума от този език. Нека тази машина има кдържави. Помислете за думата a k b k. Принадлежи на езика Ли следователно прехвърля този автомат от първоначалното състояние р 1 до някакво крайно състояние рс. От писмото Асе повтаря не по-малко пъти от броя на състоянията на автомата, има такова състояние р t , което е за първия кприложения за писма Аще бъде преминат два пъти (вж ориз. 3). Оставете машината да влезе в състояние за първи път р t в резултат на приложение a u, а следващия път ще бъде в същото състояние след нанасяне a u + v. Помислете за думата a k + v b k. Ясно е, че прилагането на тази дума към първоначалното състояние р 1 ще го постави в същото крайно състояние рс. Това означава, че тази дума също се разпознава от тази машина и следователно трябва да принадлежи на езика Л. Но в изобилие Лняма такава дума. Полученото противоречие показва, че направеното предположение е неправилно, т.е. Няма автомат, за който този набор да служи като разпознаваем език.

Ориз. 3. Маршрут върху диграфа на автомата от началното състояние р 1 до крайно състояние р s (към държавата р t буква Астои на арки uведнъж, на цикъл - пак vведнъж)

Тъй като не всеки набор от думи съставлява разпознаваем език, възниква въпросът кои набори са подходящи за тази цел. Математиците намериха удобни начини да опишат разпознаваеми езици и тези методи формираха основата за дизайна на всички съществуващи в момента езици за програмиране.

Въпроси и задачи

1. Какви два информационни модела могат да бъдат представени от автомат?

2. Какъв е езикът, разпознат от тази машина?

3. Какъв език се нарича разпознаваем?

4. За машината, показана в ориз. 1, определете в какво състояние ще бъде след изпълнение на последователността от команди

а) абба; V) бабаабааа;

б) ababbabbb; G)* a n b n.

5. За машината, показана в ориз. 2, направете описание под формата на таблица.

6. Изградете под формата на графика информационен модел на машината, посочена в табл. 3.

Таблица 3

7. Кой език над азбуката с два знака (0, 1) се разпознава от машината, показана в ориз. 4?

Ориз. 4

8. Кой език е над азбуката с два знака ( а, b) се разпознава от машината, посочена в таблицата. 3?

9. Начертайте под формата на графика информационния модел на автомат, който би разпознал език над азбуката (0, 1), състоящ се от всички думи, съдържащи точно 5 последователни.

10. Начертайте като графика информационния модел на автомат, който би разпознал език над азбуката (0, 1), състоящ се от всички думи, съдържащи точно 5 единици.

11. Начертайте като графика информационния модел на автомат, който би разпознал език над азбуката (0, 1), състоящ се от всички думи, започващи с единица (т.е. този автомат разграничава естествените числа, записани в двоичната бройна система, от произволни последователности знаци 0 и 1).

12. Сред изброените по-долу езици Л 1 , Л 2 , Л 3 , Л 4, дефинирани върху азбука от два знака (1; 2), посочете кои от тях са разпознаваеми. За всеки от разпознатите езици изградете автомат, който го разпознава; за всеки от неразпознаваемите езици докажете, че е неразпознаваем.

а) Л 1 се състои от всички думи, които представляват четни естествени числа, започващи с числото 1;

б) Л 2 се състои от всички думи, чийто брой единици е естествено число, завършващо на цифрата 3;

V) Л 3 се състои от всички думи, в които броят на двойките е просто число;

G) Л 4 се състои от всички думи, които са естествени числа, делими на 3.

13. От гледна точка на компютърните науки, каква е разликата между „живот според законите“ и „живот според концепциите“?

§ 4. Универсален изпълнител

Компютърни игри... Вероятно всеки, който поне веднъж се е занимавал с компютър, е виждал, а може би дори е играл някаква компютърна игра. На екрана някои обекти под формата на живи същества или технически устройства се подчиняват на командите на играча, други се управляват от компютър, който изпълнява дадена програма. Всички тези обекти са формални изпълнители, всеки със собствен набор от допустими действия. Само че тези обекти не са реални, а симулирани от компютър. Оказва се, че с помощта на един формален изпълнител се имитират други.

Ако се опитаме да формулираме какво означава, че един изпълнител е имитиран с помощта на друг, ще получим следното. Казват, че формалният изпълнител Аимитира формален изпълнител IN, Ако

Всеки обект, върху който изпълнителят извършва действия IN, еднозначно съответства на обекта, върху който изпълнителят извършва действия А(имитация на средата на изпълнителя);

Всяко допустимо действие на изпълнителя INдопустимото действие на изпълнителя е еднозначно съгласувано върху един или друг обект от средата Анад съответния обект от неговата среда (имитация на действия);

Всяка инструкция е съставена за изпълнителя INи водещи, когато се изпълняват, до определен резултат (т.е. до определено състояние на средата на изпълнителя и самия него), могат да бъдат трансформирани чрез имитация на допустими действия в инструкции за изпълнителя А, чието изпълнение води до съответния резултат в средата на изпълнителя А.

Въпреки това, предположението, че изпълнителите АИ INразличната среда, в която съществуват, не е фундаментална от информационна гледна точка. Например изпълнител Аборави с числа и INконвертира графични изображения. Но вече знаете, че всъщност във всеки от тези случаи говорим за трансформиране на подходящо кодирана информация. Освен това може да се предположи, че се използва един и същ двоичен код. В този смисъл можем да считаме, че средата на изпълнителя е просто същата – информация, представена под формата на кодирано съобщение.

Един от най-важните въпроси в теоретичната компютърна наука е: има ли такъв формален изпълнител, с който човек може да имитира всеки формален изпълнител? Естествено е да се обадите на такъв изпълнител универсален. Лесно е да се разбере, че универсален изпълнител не съществува като физическо устройство - в крайна сметка информацията може да бъде кодирана в произволно дълги съобщения и всяка физическа среда е ограничена. Ако говорим за универсалния изпълнител като идеален обект, тогава се оказва, че отговорът на зададения въпрос е положителен. И тя е получена почти едновременно и независимо от двама изключителни учени - А. Тюринг (през 1936 г.) и Е. Пост (през 1937 г.). Предложените от тях изпълнители се различаваха помежду си, но се оказа, че те могат да се подражават един на друг и най-важното - въобще да имитират всеки формален изпълнител.

Универсалният изпълнител обикновено се нарича машина. Също така е обичайно да се кръщават машини на техните изобретатели. Така че универсалният изпълнител, изобретен от А. Тюринг, се нарича машина на Тюринг; изпълнителят, описан от Е. Пост - машината на Пост. По-късно се появиха и други универсални изпълнители, например машината Мински.

И така, можем да приемем, че имаме съобщение, написано на някаква азбука, и то трябва да бъде преобразувано в друго съобщение. Разбира се, писането на инструкции до официален изпълнител за обработка на конкретна двойка съобщения не е сложен въпрос. Но вече знаете, че истинският интерес е към инструкции (т.е. алгоритми), които ви позволяват да решавате цял клас проблеми от същия тип - така нареченото „масово свойство на алгоритъм“. Например тази задача: добавете друг предварително определен символ вдясно на произволно съобщение. Ако, да речем, поредица от еднакви символи действа като код за естествено число - броят на символите в поредицата е естественото число, което се кодира - тогава всъщност говорим за създаване на алгоритъм за увеличаване на числото с 1.

Естествено е да приемем, че съобщението е записано на лента. Освен това е удобно да си представим тази лента, разделена на равни клетки и всяка клетка съдържа точно един знак за съобщение. Тъй като съобщенията могат да бъдат толкова дълги, колкото желаете, ще се съгласим да си представим емисията като безкрайна. Празните клетки ще се считат за запълнени със символ "интервал". По този начин обявихме, че всяка азбука, която ще използваме за запис на съобщения на тази лента, трябва да съдържа „интервал“. Нека се съгласим да го обозначим А 0 . Останалите знаци от азбуката, използвани за запис на съобщения на лента, ще бъдат обозначени с А 1 , А 2 , ..., Ан. Ако, например, трябва да запишем задачата за изчисляване на сумата от две числа, тогава азбуката може да се приеме, както следва: А 0 ; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. За определена двойка данни (т.е. две числа), записът на лентата може да изглежда, например, както е показано в ориз. 5.

Ориз. 5

Ние, разбира се, няма да пишем символ на лентата в празни клетки А 0, което означава, че е там. Освен това се съгласяваме, че първият знак на съобщението, различен от интервал, винаги се появява в една и съща клетка - on ориз. 4 се отбелязва Ї. Ще наречем тази клетка начална.

Съобщението, записано на лентата, се обработва от някакво устройство и резултатът се записва обратно на лентата. Тъй като изпълнителят е формален, той не се задълбочава в смисъла на посланието, а според инструкциите, съставени за него, заменя някои символи с други. Не се интересуваме как физически се извършва такава подмяна, така че можем да си представим, че по лентата се движи някакъв автомат, който чете символ от клетка на лентата, обработва получената информация, отпечатва друг знак в клетката (ако е предписано от инструкциите) и се премества в съседната клетка - вдясно или вляво.

Вече знаете, че всеки автомат се описва от набор от състояния. Обичайно е да се обозначават състоянията на определената машина за четене и печат с букви р 0 , р 1 , р 2 , ..., рм. В същото време се съгласяваме, че когато машината е включена, т.е. в началото на работа винаги е в едно и също състояние, което ще обозначим р 0 и се намира срещу началната клетка.

Така машината на Тюринг е формално описана от набор от две азбуки: А = {А 1 , А 2 , ..., А) И Q = {р 0 , р 1 , р 2 , ..., рм). Азбука АНаречен външени служи за запис на начални съобщения, азбука QНаречен вътрешнии описва набор от състояния на четеца-печатащо устройство. Ще изобразим машина на Тюринг, както е показано на ориз. 6.

Ориз. 6

На ориз.Фигура 6 показва момента на работа на машината на Тюринг, когато четящо-печатащото устройство разглежда третата клетка от първоначалната (в този момент в нея имаше символ като 3) и е в състояние q k.

И така, допустимите действия на машина на Тюринг са:

Напишете всеки символ от външната азбука в секцията на лентата (символът, който е бил там преди, се презаписва);

Преминете към следващия раздел;

Променете състоянието на едно от тези, посочени от символа на вътрешната азбука;

Спрете работата (спирайте).

Разбира се, в това изброяване всеки ред показва не едно действие, а група действия от един и същи тип - има толкова действия „напишете символ на външната азбука“, колкото са тези символи, можете да преминете към съседните раздел отдясно или отляво, има толкова действия за промяна на състоянието, колкото са тези състояния (т.е. колко знака от вътрешната азбука).

Сега трябва да кажем как са написани командите за извършване на посочените действия. Всяка машинна команда съдържа най-много едно действие от всяка група действия и има формата

Действителните команди изглеждат така:

a i р j - пишете в наблюдавания раздел а i , преместете се надясно (до следващия раздел) и влезте в състоянието р j;

a i р j - пишете в наблюдавания раздел а i , преместете се наляво и отидете на състояние р j;

a i S р j - пишете в наблюдавания раздел ai, спрете и отидете на състояние рй.

За извършване на действия машината на Тюринг има оперативно-логическа единица. Този блок има два входа: през единия от тях се получава информация кой символ се намира в наблюдаваната клетка, през другия - информация в какво състояние се намира машината на дадена стъпка от нейната работа. Тази информация еднозначно определя коя команда трябва да изпълни машината. Тъй като една команда може да съдържа инструкция за извършване на три действия - писане на символ на лентата, преместване и промяна на състоянието - оперативно-логическият блок има три изхода: писане на знак А, изместване Ми промяна на състоянието Q(см. ориз. 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. Лентата на машината на Тюринг съдържа низ, състоящ се от няколко последователни символа „*“, последвани от няколко символа „#“, а в края на реда има символ „e“ (един от възможните варианти на такъв низ е показано в ориз. 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 г. Там ще намерите и анализ на още няколко задачи за програмиране на машината на Тюринг; просто трябва да имате предвид, че те използват малко по-различна (която е напълно безпринципна) командна система.

* Припомнете си, че графиката е набор от точки, наречени върхове, и линии, свързващи някои от върховете. Ако посоката е посочена на линиите, свързващи върховете, тогава графът се извиква ориентиран(съкратено диграф), а репликите се наричат ​​негови дъги. В обикновена графика, т.е. неориентирани се наричат ​​линиите, свързващи върховете ребра. Графиките ще бъдат разгледани по-подробно в Лекция 4.

Формални изпълнители, тоест тези, които не разбират смисъла на алгоритъма, а изпълняват само посочените стъпки и не могат да ги редактират: куче, което не разбира значението на командите, телевизор, изобщо - всякакви неодушевени изпълнители. Неформални - тези, които разбират значението на алгоритъма и могат да направят корекции в него - да речем, човек.

Всеки алгоритъм предполага наличието на някои първоначални или първоначални данни и в резултат на прилагането води до получаване на определен желан резултат. Например, в алгоритъм с разработчик, първоначалните данни са съдържанието на голям и малък пакет, вода. Желаният резултат е готов за употреба проявител на фолио. При изчисляване на ранга на матрица, първоначалните данни са правоъгълна таблица, съставена от рационални числа, резултатът е естествено число, което е рангът на тази матрица.

Освен това прилагането на всеки алгоритъм се осъществява чрез извършване на дискретна верига (последователност) от определени елементарни действия. Тези действия се наричат ​​стъпки, а процесът на извършването им се нарича алгоритмичен процес. По този начин се отбелязва свойството дискретност на алгоритъма.

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

41 .

Формален аналог на машина на Тюринг.

Машината на Тюринг (MT) се състои от лента за броене (разделена на клетки и ограничена отляво, но не и отдясно), глава за четене и запис, лентов механизъм и оперативен задвижващ механизъм, който може да бъде в един от дискретните състояния qo, q1,..., qs, принадлежащи към някаква крайна колекция (азбука на вътрешните състояния). В този случай qо се нарича начално състояние.

Главата за четене и писане може да чете буквите от работната азбука A = [a0, a1,..., at), да ги изтрива и отпечатва. Всяка клетка от лентата във всеки момент от времето е заета от буква от множеството A. Най-често срещаната буква е a0 - “интервал”. Главата се намира във всеки момент от време над определена клетка на лентата - текущата работна клетка. Механизмът за задвижване на лентата може да премества лентата така, че главата да е над съседната клетка на лентата. В този случай е възможно лентата да излезе отвъд левия ръб (LC), което е аварийно (неприемливо) или спиране на машината (MS), когато машината отговаря на заповедта за спиране.

Работният ред на МТ (с работната азбука a0, a1,..., at и състояния q0, q1,..., qs) се описва от таблицата на машината на Тюринг. Тази таблица е матрица с четири колони и (s + 1)(t + 1) редове. Всеки ред изглежда така

Изчислими функции на Тюринг. Тезата на Тюринг.

Тезата на Тюринг: абстрактна машина на Тюринг е способна да извършва всяка операция, която се подчинява на определени правила и в този смисъл е чисто механична.

Машината работи по следната програма.

В началния момент на лентата се записва определена верига от много V * , всички останали клетки на лентата се запълват със символа #. Контролът в началния момент е в държавата р 0 , главата за четене и запис сканира най-левия знак на записания низ. Работата на машината се състои в повтаряне на следния цикъл от елементарни действия:

1. Четене от главата на символ от клетката срещу него.

2. Намиране на приложимата команда, а именно командата qa → q’a’d, Където q-известно състояние на контрол, а-знак за четене.

3. Изпълнете намерената команда, която е както следва. Символът се записва в клетката, сканирана от главата а’, символ а-се изтрива, контролът преминава в състоянието q'и главата се движи относително д. Ако d=rглавата се премества с една клетка надясно, ако аз -премества една клетка наляво, стр– не се извършва движение. Спира се, ако на следващата стъпка не е приложима команда на програмата. Резултатът от машината на Тюринг е верига, записана на лента.

Съвременният човек е заобиколен от много различни технически устройства: телевизор, магнетофон, камера, телефон, пералня, кола и др. Всяко от тези устройства е предназначено да решава своя собствена задача и е в състояние да изпълнява определен ограничен набор от действия или команди .

Изпълнител- това е обект (човек, животно, техническо устройство), способен да изпълнява определен набор от команди. Команди, които могат да бъдат изпълнени от определен изпълнител формират система от изпълнителски команди(СКИ).

Има различни изпълнители. Един от най-простите изпълнители може да се счита за бутон за включване / изключване на тялото на монитора.

Командната система на изпълнителя - CD плейър е показана на фиг. 56.

Ориз. 56

По-сложен изпълнител е модерна пералня, чиято електронна памет съдържа различни програми за пране на пране, разработени от инженери. Машината извършва целия процес на пране (накисване, пране, изплакване, центрофугиране, сушене) автоматично, без човешко участие, а по избрана от човек програма.

Между автоматични устройстванай-завършените изпълнители са роботи. Малко вероятно е човек да може да сглоби сложна част толкова бързо, точно и ефективно, колкото прави манипулатор робот в автоматизирано производство. В наши дни са създадени хуманоидни роботи и играчки-роботи, наподобяващи домашни любимци.

Друг пример за изпълнител - компютър. Неговата отличителна черта е многофункционалност. Запознати сте с компютърни програми, предназначени за обработка на текстова, числова и графична информация, с образователни програми и компютърни игри. Освен това има програми, с които компютърът контролира работата на други устройства, свързани с него (изпълнители).

В много случаи самият човек е изпълнител на алгоритмите. Например, всеки от нас, пресичайки улицата, е изпълнител на следния алгоритъм:

1. спрете на тротоара;
2. погледнете наляво;
3. ако няма транспорт, отидете до средата на улицата и спрете, в противен случай следвайте стъпка 2;
4. погледнете надясно;
5. ако няма транспорт, отидете на отсрещния тротоар, в противен случай следвайте стъпка 4.

Изпълнителите на голям брой алгоритми са ученици, които изпълняват множество писмени и устни задачи.

Официални изпълнители

Има два вида изпълнители: официални и неформални. Официалният изпълнител винаги изпълнява една и съща команда по един и същи начин. Неформалният изпълнител може да изпълни команда по различни начини.

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

По правило човек действа като неформален изпълнител. Формалните изпълнители са предимно технически средства. Човек в ролята на неформален изпълнител носи отговорност за собствените си действия. Обектът, който го контролира, отговаря за действията на формалния изпълнител.

Нека разгледаме по-подробно набора от официални изпълнители. Формалните изпълнители са изключително разнообразни, но за всеки от тях е възможно да се определи кръг от задачи за решаване, среда, система за управление, система за отказ и режими на работа.

1. Обхват от задачи за решаване. Всеки изпълнител е създаден за решаване на определен клас проблеми.
2. Артистична среда. Районът, обстановката, условията, в които изпълнителят работи, обикновено се наричат ​​средата на дадения изпълнител.
3. Командна система на изпълнителя. Инструкция за извършване на отделно завършено действие на изпълнителя се нарича команда. Съвкупността от всички команди, които могат да бъдат изпълнени от даден изпълнител, образува SKI - системата от команди на изпълнителя.
4. Система за отказ на изпълнител. Отказът „Не разбирам“ възниква, когато изпълнителят получи команда, която не е част от неговия SKI. Отказът „не мога“ възниква, когато команда от SCI не може да бъде изпълнена от него при специфични условия на околната среда.
5. Режими на работа на изпълнителя. За повечето изпълнители са осигурени режими на директен и програмен контрол. В първия случай изпълнителят изчаква команди от управляващия обект и незабавно изпълнява всяка получена команда. Във втория случай на изпълнителя първо се дава пълна последователност от команди (програма), след което той автоматично изпълнява всички тези команди. Редица изпълнители работят само в един от посочените режими.

Автоматизация

Разработването на алгоритъм е трудоемка задача, която изисква от човек дълбоки познания и много време. Решаването на проблем с помощта на готов алгоритъм изисква само изпълнителят да следва стриктно дадените инструкции. Изпълнителят не се задълбочава в смисъла на това, което прави и не разсъждава защо постъпва така, а не иначе - той действа формално. Свързана с това е възможността автоматизациячовешка дейност - замяна на част от човешкия труд с работата на машини (автоматични устройства):

• процесът на решаване на проблем се представя като последователност от прости операции;
• създава се машина, способна да извършва тези операции в последователността, определена в алгоритъма;
• изпълнението на алгоритъма е поверено на автоматично устройство; човек се освобождава от рутинни дейности.

Приложение No1

АЛГОРИТЪМ И ИЗПЪЛНИТЕЛИ

Цел на изследването: владеят понятията алгоритъм, изпълнител, имат представа за алгоритъма като модел на дейността на изпълнителя.

Алгоритъм

Дефиниции алгоритъм

Алгоритъмът е точно описание на последователността от действия, които са насочени към решаване на даден проблем.

Алгоритъмът е модел на дейността на изпълнителя на алгоритъма.

Мишена

Разработва се алгоритъм за решаване на конкретен проблем или клас проблеми.

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

Алгоритмите могат да бъдат записани под формата на таблица, номериран списък, програма или блок-схема.

Съставя се алгоритъм за конкретен изпълнител на език, който той разбира.

Изпълнители на алгоритъм

Изпълнителят на алгоритъма може да бъде човек, група хора, животно или технически устройства, способни да изпълняват определена последователност от команди.

Фиг. 1 Изпълнител - техническо средство

Фиг.2. Изпълнителят е животно

Фиг.3. Изпълнител - човек

Екип

Инструкция за извършване на отделно завършено действие от изпълнител се нарича команда. Командите, които конкретният изпълнител трябва да изпълни, образуват система от команди на изпълнителя.

Официални и неформални изпълнители на алгоритъма

Изпълнителите на алгоритъма могат да бъдат формални и неформални.

Неформален изпълнител може да изпълни една и съща команда по различни начини. Ролята на неформален изпълнител се играе от човек или животно. Неформалният изпълнител носи отговорност за собствените си действия.

Ориз. 4. Неформален изпълнител

Официалният изпълнител винаги изпълнява една и съща команда по един и същи начин. Формалните изпълнители са предимно технически средства. Например микровълнова фурна, пералня и т.н. Обектът, който го управлява, отговаря за действието на формалния изпълнител. За всеки формален изпълнител можете да посочите обхвата от задачи, които трябва да бъдат решени, средата, командната система, системата за отказ на изпълнителя и режимите на работа.

Фиг.5. Формален изпълнител

Средата на изпълнителя обикновено се нарича областта, обстановката и условията, в които изпълнителят работи. Например средата на изпълнителя Чертожнике координатната равнина.

Ориз. 6. Средата на художника е чертожник.

Провали

Като се има предвид средата и системата от команди на изпълнителя, е възможно да се създаде система от откази: „Не разбирам“, „Не мога“. Ако на изпълнителя бъде дадена команда, която не е включена в неговата система от команди за изпълнител, тогава се получава отказ „Не разбирам“.

Команда: „Загрейте сандвича“

Ориз. 7. Отказ „Не разбирам“

Ако на изпълнителя бъде дадена команда от командната система на изпълнителя, която той не може да изпълни при специфични условия на околната среда, тогава възниква повреда „Не мога“.

Екип: "Продължавай"

Ориз. 8. Отказ „Не мога“

Управление на артисти

Управлението е процес на насочено въздействие на едни обекти върху други.

Изпълнителите са обект на управление. Можете да ги управлявате, като създадете алгоритъм за тях.

Два режима на управление

За повечето изпълнители са предвидени два режима - директно и програмно управление.

Режимът, при който обектът на управление управлява изпълнителя в даден момент, се нарича режим на пряко управление.

Ориз. 7. Директен режим на управление

Режимът, в който човек управлява изпълнителя с помощта на подготвена програма, се нарича режим на програмен контрол.

Ориз. 8. Режим на програмно управление

За да постигнете целта на изучаването на този параграф, попълнете обучение и тествайте себе си с помощта на модула домашна работа .