Алгоритми,їх основні властивості

План:

1. Алгоритми,їх основні властивості.
2. Способи представлення алгоритмів.
3. Блок-схеми. Приклади створення блок-схем
4. Поняття про криптографію.
5. Методи кодування інформації.
6. Приклади криптографічних задач.
7. Поняття рекурсії. Рекурсія в синтаксичних правилах.
8. Задача про Ханойські вежі.

Алгоритми,їх основні властивості

Алгоритм – це скінчена послідовність вказівок (команд), виконання  яких дозволяє за обмежений час отримати розв’язок задачі.

Сам термін “алгоритм” утворився  в результаті перекладу на європейські  мови імені арабського математика ІХ століття Аль-Хорезмі, який описав правила (алгоритми) виконання основних арифметичних операцій у десятковій системі числення.

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

Кожний алгоритм повинен  відповідати наступним властивостям:

Властивості алгоритмів

1. Скінченність. Виконання  алгоритму повинно приводити  до очікуваного результату за  скінченну кількість кроків.

2. Результативність. Виконання  алгоритму завжди повинно призводити  до певного результату.

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

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

5. Масовість. За допомогою  складеного алгоритму повинен  розв’язуватись цілий клас подібних  задач.

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

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

Способи представлення алгоритмів

Виділяють декілька основних видів представлення алгоритмів:

1. Форма опису. Всі команди описуються за допомогою простих речень.

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

Алгоритм «Ранок»;

1. 6:00 прокинутися;
2. 6:10 вмитися;
3. 6:30 застелити ліжко;
4. 6:35 зробити ранкову зарядку;
5. 6:50 поснідати;
6. 7:10 зібратися до школи;
7. 8:30 вийти з дому до школи.

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

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

• словесна або вербальна (мовна, формульно-словесна);
• псевдокод (формальні алгоритмічні мови);

      Схемна:

• структурограми (схеми Нассі-Шнайдермана);
• графічна (блок-схема, виконується за вимогами стандарту).

Блок-схеми

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

Блок-схема  алгоритму визначення дієвідміни в  дієслові.

Використовуючи дані блоки, можна подати, наприклад, алгоритм чищення  картоплі в такому вигляді:

Поняття про криптографію

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

Методи  кодування інформації

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

  Кодування - це перетворення інформації без зміни її змісту в інший вигляд за допомогою певного коду. Код - це набір правил перетворення для кодування. Прикладом учнівського кодування є такий прийом: випису¬ється алфавіт і всі букви нумеруються за порядком. Наприклад, так: За допомогою цієї кодової таблиці можна написати зашиф¬ровану записку, де букви замінені відповідними числами. Наприклад, таку: З 1 22 33 6 1 14 22 20 11 22 1 23 11 1 16 4 7 2 21 24 Одержувач такої записки повинен користуватися цією ж кодовою таблицею, щоб розшифрувати і прочитати повідомлення. У комп'ютері носіями інформації є електричні або магнітні сигнали, які можуть мати лише два значення: 0 - вимкнуто (нема струму, розмагнічено) або 1 - ввімкнуто (є струм, намагнічено). За допомогою таких 0 і 1 кодують будь-яку інформацію, яку обробляє комп'ютер. Якщо застосувати згаданий метод, то цифр 0 і 1 вистачить на позначення лише двох символів. Можна застосувати кодування комбінацією із кількох Oil. Якщо взяти по два знаки (00, 01. 10, 11), це дозволить кодувати вже 4 символи. Тризначний код дає 8 комбінацій, чотиризначний - 16. Цього мало для зображення літер алфавіту, цифр і розділових знаків, спеціальних символів тощо. Такої кількості символів вистачає для відображення літер, цифр, розділових, а також графічних елементів. Малюнки і звуки зображуються тими ж комбінаціями, але перед ними стоїть спеціальний знак, який вказує на характер інформації.

Усі символи, які використовує комп'ютер, заносяться в табли¬цю і  нумеруються десятковими числами, які перетворюються у двійковий  код із 8 знаків 0 і 1 - виходить кодова таблиця символів. Наприклад, в комп'ютерах застосовується восьмизначний код ASCII, розрахований на 256 символів. Для  кожного символу - це послідовність  з 8-ми цифр Oil, яка визначає певний символ. У комп'ютер заноситься та обробляється текстова інформація, цілі і дійсні числа, графічні побудови, малюнки і  музика. І всі вони представлені у вигляді комбінацій із восьми «0»  і «1» - байтами. Яка б інформація в комп'ютері не була (голос диктора  або його зображення), вона завжди кодується  байтами. Визначимо головну відмінність  між книгою і занесеним в комп'ютер текстом. Вона полягає в тому, що коли ми відкриваємо книгу, то бачимо зображення символів, сформованих дрібними крих¬тами друкарської фарби. А  якщо ж «відкриємо» пам'ять комп'ютера, то «побачимо» коди літер, складених  із 0 і 1. Звичайний текст зображується в комп'ютері послідовністю кодів. Тобто замість кож¬ної літери тексту зберігається її номер за кодовою  таблицею. І тільки при виведенні  літер у зовнішнє середовище (на папір або екран монітора) проводиться  формування звичних зорових образів  літер.

Витяг з кодової таблиці  символів ASCII

 В сучасних програмах  розповсюджене кодування символів 16-бітним кодом (2 байти) UNICODE з  номерами від 0 до 65535, що практично  вміщує алфавіти всіх народів  світу.

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

Найпростіша модель криптосистеми

Рис. 1

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

Поняття рекурсії

Поняття підпрограми тісно  пов’язане з одним методом  розв’язання задач, яке має назву  рекурсія. Рекурсія – це метод визначення чи вираження функції, процедури, мовної конструкції чи рішення задачі за допомогою тієї ж функції, процедури  та т.п. Слово рекурсивний, рекурентний  вийшло від латинського “recurro” (бігти  назад, вертатися).

Термін рекурсія дуже популярний у математиці і програмуванні. У  широкому смислі, рекурсія — це звертання  до самого себе (цей термін походить від латинського слова recursio —  повернення). У математиці і програмуванні  цей термін використовується при  визначенні так званих  рекурсивних  функцій і рекурсивних процедур.

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

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

Задача  про Ханойські вежі.

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

 Уточнимо постановку  задачі. Нехай ми маємо три  спеціальних сердечники, на яких  проходить переміщення дисків. Висота  сердечників достатня для того, щоб на ній могли розміститись всі n дисків. Всі диски різного діаметру, а внутрішній отвір більший за діаметр сердечників. Спочатку всі диски розміщені на першому сердечнику в спадному, згідно зовнішнього діаметра, порядку. Їх потрібно перенести на третій сердечник, використовуючи другий сердечник, так , щоб вони розмістились в такому ж порядку, як були на першому сердечнику. При переміщеннях потрібно дотримуватись такого обмеження: ніколи диск більшого діаметра не може знаходитись зверху хоча б над одним диском меншого діаметра.

 Для переносу можна  запропонувати наступний рекурсивний  алгоритм.

* Один диск можна перенести  прямо на потрібний сердечник.

* N дисків можна перемістить  так:

1. Перемістити останній (N-ий) диск прямо на третій (правий) сердечник;

2. Перемістити N-1 диск  на другий (середній) сердечник;

3. Перемістити прямо N-ий  диск з третього сердечника  на перший (лівий);

4. Перемістити N-1 диск  з другого на третій;

5. Перемістити N-ий диск  прямо з першого на третій  сердечник.

 Поділ слів на склади.

 На прикладі розв’язання  цієї задачі продемонструємо  можливості Прологу при обробці  текстової інформації в редакторах.

 Для розв’язання задачі  ділення слів на склади, будемо  використовувати простий алгоритм, який базується на впорядкуванні  голосних і приголосних в слові. 

 Наприклад, розглянемо  дві послідовності:

1) приголосна - голосна - приголосна. В цьому випадку, слово  ділится після першої голосної:

ruler ---> ru-ler

prolog ---> pro-log

2) голосна - приголосна - приголосна. В цьому випадку , слово ділиться між двома приголосними:

number ---> num-ber

panter ---> pan-ter

 Ці два правила добре  застосовуються для більшості  слів, але не працюють для слів  типу handbook и hungry, які не підходять  до жодного правила. 

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

ПРАКТИЧНА ЧАСТИНА

Приклад 1:

domains

loc = right;

middle;

left

predicates

hanoi(integer)

move(integer, loc, loc, loc)

inform(loc, loc)

clauses

hanoi(N) :- move(N, left, middle, right).

move(1, A, _, C) :- inform(A, C), !.

move(N, A, B, C) :- N1=N-1,

move(N1, A, C, B),

inform(A, C),

move(N1, B, A, C).

inform(Loc1, Loc2) :-

write("\nMove a disk from ", Loc1, "to", Loc2).

  Приклад 2:

domains

letter = char

word = letter*

predicates

divide(word, word, word, word)

vocal(letter)

consonant(letter)

string_word(string, word)

append(word, word, word)

repeat

goal

clearwindow,

repeat,

write("Write a multi-syllable word: "),

readln(S),

string_word(S, Word),

divide([], Word, Part1, Part2),

string_word(Syllable1, Part1),

string_word(Syllable2, Part2),

write("Division: ",Syllable1,"-",Syllable2),nl,

fail.

clauses

divide(Start, [T1, T2, T3|Rest], D1, [T2, T3|Rest]):- vocal(T1),    consonant(T2), vocal(T3), append(Start, [T1], D1).

divide(Start, [T1, T2, T3, T4|Rest], D1,[T3, T4|Rest]):- vocal(T1), consonant(T2), consonant(T3), vocal(T4), append(Start, [T1, T2], D1).

divide(Start, [T1|Rest], D1, D2):- append(Start, [T1], S), divide(S, Rest, D1, D2).

vocal('a').vocal('e').vocal('i').

vocal('o').vocal('u').vocal('y').

consonant(B):- not(vocal(B)), B <= 'z', 'a' <= B.

string_word("", []):-!.

string_word(Str, [H|T]):- bound(Str), frontchar(Str, H, S), string_word(S, T).

string_word(Str, [H|T]):- free(Str), bound(H), string_word(S,T),

frontchar(Str,H,S).

append([], L, L):-!.

append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).

repeat.

repeat :- repeat.

Література:

1. Ахи А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ. М.: Издат. дом «Вильямс», 2000.  С. 183–225
2. Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ. СПб.: «ДиаСофтЮП», 2003. С. 673–1000
3. Зуйкова О.Л. Основи криптографічного захисту інформації. Навчальний посібник
4. Аліпов Ілля Миколайович. Методи захисту інформації при її передаванні
5. Браян. В. Керніган і Деніс М. Річі : Мова програмування C
6. Барвайс Дж. (ред.) - Довідкова книга з математичної логіки. Частина 3. Теорія рекурсії