На головну

лекція 2

  1. II. ТЕМАТИКА ЛЕКЦІЙ Лекція 1. Об'єкт, предмет соціології, зв'язок з іншими науками
  2. Безпека життєдіяльності. Оглядова лекція
  3. Вступна лекція
  4. Вступна лекція
  5. ВСТУПНА ЛЕКЦІЯ. СИСТЕМА ПОЗНАЧЕНЬ.
  6. ДВАДЦЯТЬ П'ЯТА Лекція
  7. Демонстраційна лекція

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

визначення 1. Схемою нормального алгоритму в алфавіті

називається впорядкована послідовність

(1)

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

Формула називається простий, якщо є і заключної, якщо є

Дія НА на слово в алфавіті описується наступним визначенням.

Визначення 2. Нехай - слово в алфавіті і хоча б одне зі слів є його подсловом. Елементарним перетворенням слова по нормальному алгоритму зі схемою (1) називається заміна в першого входження слова з найменшим номером словом Якщо результатом зазначеного елементарного перетворення є слово то пишуть т. Е. Або.

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

 (2)

в якій

 або й слово не містить Підшар

В іншому випадку говорять, що алгоритм не застосовний до слову

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

Таким чином, НА в алфавіті задає часткове відображення безлічі всіх слів в алфавіті в саме себе. Вибираючи різні схеми, ми будемо отримувати різні НА.

Якщо - алфавіт, що містить, то НА в алфавіті називається нормальним алгоритмом над алфавітом.

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

1. НА в алфавіті зі схемою

переробляє будь-яке слово в себе, причому послідовність слів, відповідна слову має вигляд:.

2. НА зі схемою

не застосовують ні до одного слова. Послідовність, відповідна слову буде нескінченною:

3. НА в алфавіті зі схемою

приписує до будь-якому слову зліва слово:

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

.................

Послідовність слів, відповідна безпідставного слову в алфавіті, для цього НА має вигляд:

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

так, що вся схема запишеться у вигляді:

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

 де кількість букв дорівнюватиме,

де виходить з видаленням всіх входжень літери (т. е. є проекція в алфавіт).

5. Побудуємо НА, переробний будь-яке слово в перевернуте слово Для цього додамо до дві нові літери і візьмемо таку схему в алфавіті

Прослідкуйте, як вправу, що для будь-якого слова в алфавіті.

Наведемо ще приклади НА над числами. Домовимося натуральне число записувати у вигляді вертикальних паличок.

6. НА в алфавіті зі схемою

здійснює складання натуральних чисел.

7. НА в алфавіті зі схемою

здійснює множення натуральних чисел.

лекція 2

2.1. Максимальний струмовий захист

2.2. струмовий відсічення

2.3. Струмовий захист нульової послідовності

 



НОРМАЛЬНІ АЛГОРИТМИ | Максимальний струмовий захист
© um.co.ua - учбові матеріали та реферати