Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇHИ





МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇHИ

МАШИНОБУДІВНИЙ КОЛЕДЖ ДОHБАСЬКОЇ ДЕРЖАВНОЇ МАШИHОБУДІВНОЇ АКАДЕМІЇ

 

ТЕОРІЯ АЛГОРИТМІВ І СТРУКТУРИ ДАНИХ

 

КОНСПЕКТ ЛЕКЦІЙ

для студентів спеціальності 5.080406 «Експлуатація систем обробки інформації й прийняття рішень»

 


Конспект лекцій з дисципліни «Теорія алгоритмів і структури даних» для студентів усіх форм навчання./ Сост. Дерека Л.В. – Краматорськ: МК ДДМА, 2010 – 92 с.

 

 

Розглянуто й схвалено на

засіданні циклової комісії

«Комп'ютерних наук».

Протокол №___ від « »______

2010 р.

Голова___________ О.В. Олійник


 

ЗМІСТ

ЛЕКЦІЯ № 1 Базові поняття теорії алгоритмів. 4

ЛЕКЦІЯ № 2 Класи алгоритмів. 13

ЛЕКЦІЯ № 3 Поняття структури даних. 25

ЛЕКЦІЯ № 4 Поняття та подання графу. 31

ЛЕКЦІЯ № 5 Алгоритми проходження графу. 37

ЛЕКЦІЯ № 6 Алгоритми пошуку. 42

ЛЕКЦІЯ № 7 Алгоритми сортування: методи внутрішнього сортування. 50

ЛЕКЦІЯ № 8 Алгоритми сортування: методи зовнішнього сортування. 72

ЛЕКЦІЯ № 9 Класичні задачі комбінаторіки. 82

ПЕРЕЛІК ЛІТЕРАТУРИ.. 92

 


 

ЛЕКЦІЯ № 1

 

Тема: Базові поняття теорії алгоритмів

 

Ціль: розглянути поняття алгоритму , визначити виконавців алгоритму та властивості алгоритму

 

План

 

Визначення інформації

Визначення алгоритму

Виконавці алгоритмів

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

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

Поняття обчислювальної складності

 

Визначення інформації

 

Термін ≪інформація≫ походить від латинського слова ≪information» - виклад, роз'яснення фактів, подій. Тому, в найширшому розумінні інформація трактується наступним чином.

Інформація – це відомості, пояснення, знання про всілякі об'єкти, явища, процеси реального світу.

 

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

Інформація - нові відомості, які дозволяють поліпшити процеси, пов'язані з перетворенням речовин, енергії та самої інформації.

Інформацію не можна відокремити від процесу інформування. В основі цього процесу лежить взаємозалежність пари об'єктів - джерела і споживача інформації.

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

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

Інформація– це нові відомості, прийняті, зрозумілі і оцінені її користувачем як корисні.

Іншими словами, інформація - це нові знання, які отримує споживач (суб'єкт) в результаті сприйняття і опрацювання певних відомостей, тобто у результаті застосування до цих відомостей адекватних методів оперування ними (термін ≪адекватний≫ означає цілком відповідний; прирівняний; той, що влаштовує).

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

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

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

Інформація – це відомості, які є об'єктом збирання, реєстрації, збереження, передавання і перетворення.

 

Основна маса інформації збирається, передається і опрацьовується у знаковій формі – числовій, текстовій, табличній, графічній і т.ін. Знакове подання інформації інформатика пов'язує з поняттям ≪дані≫.

Дані — це відомості, подані у певній знаковій формі, придатній для передавання, інтерпретації та опрацювання людиною або автоматичним пристроєм.

Взаємозв'язок між інформацією, даними і методами оперування ними характеризується низкою властивостей.

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

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

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

Рівень інформативності даних залежить від ступеня адекватності методів, що застосовуються в інформаційних процесах.

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

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

 

Визначення алгоритму

 

За визначенням А.П.Єршова, інформатика - це наука про методи подання, накопичення, передавання та опрацювання інформації за допомогою комп'ютера. Що таке інформація? Вважається, що інформація - це поняття, яке передбачає наявність матеріального носія інформації, джерела і передавача інформації, приймача і каналу зв'язку між джерелом і приймачем інформації.

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

Відповідно до етапів маємо три групи засобів інформатики: специфікація, шігоритмізація і програмування.

Для специф ікації задач в курсі застосовані засоби типу рекурентних співвідношень, рекурсивних визначень, а також прості інваріантні співвідношення, початкові й кінцеві умови.

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

Істотно, що, порівняно з програмою, алгоритм може перебувати на вищому рівні абстракції, бути вільним від тих або інших деталей реалізації, пов'язаних з особливостями мови програмування та конкретної обчислювальної системи. Засоби, прийняті для зображення алгоритмів, за традицією називають алгоритмічною мовою. До речі, так називалися також перші мови програмування високого рівня, наприклад, Алгол – це просто скорочення ALGOrithmic Language - алгоритмічна мова. Але, загалом, жодна мова програмування не може цілком замінити алгоритмічну мову, оскільки консервативна за своєю суттю. Стабільність - один з необхідних компонентів якості мови програмування. Повинні існувати Гарантії, що всі програми, складені вчора, в минулому році, десять років тому, не втратять значення ні сьогодні, ні завтра. Модифікація мови програмування призводить до небажаних наслідків: вимагає перероблення системи програмування, знецінює напрацьоване програмне забезпечення. У той же час алгоритмічна мова може створюватися спеціально для певної предметної області, певного класу задач або навіть окремої задачі. Вона може розвиватися навіть при створенні алгоритму, вбираючи в себе новітні результати.

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

 

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

 

Приклад 1.1. Обчислити (х+у)/(а-b)

А = (A1, А2, А3)

A1:х+у

А2: а-b

А3: A12

 

Слово алгоритм походить від algorithmic – латинської форми написання імені великого математика IX ст. Аль-Хорезмі, який сформулював правила виконання арифметичних дій.

 

Приклад 1.2. Розглянемо відому задачу про людину з човном (Л), вовком (В), козою (Кз) і капустою (Кп). Алгоритм її розв'язання можна подати так:

{ Л, В, Кз, Кп → } - початковий стан,

пливуть Л, Кз, Кп

{ В →Л, Кз, Кп } - 1 - ий крок,

пливуть Л, Кз

{ Л, В, Кз → Кп } - 2-ий крок,

пливуть Л, В

{ Кз → Л, В, Кп } - 3-ій крок,

пливуть Л

{ Л, Кз → В, Кп } - 4-ий крок,

пливуть Л, Кз

{→Л, В, Кз, Кп } - кінцевий стан.

 

Виконавці алгоритмів

 

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

Кожен виконавець може виконати певну кількість команд. Ці команди називаються допустимими командами виконавця.

Виконавцем ми будемо називати пристрій, здатний виконувати дії із заданого набору дій. Команду на виконання окремої дії називають оператором або інструкцією. Приклади виконавців: пральна машина, телефон, мікрокалькулятор, магнітофон, комп'ютер тощо. Приклади інструкцій: перемотати плівку, встановити з'єднання із вданим номером, виконати прання бавовняної білизни, зіграти партію у реверсі і т.ін.

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

Розглянемо приклади найпростіших виконавців.

Виконавець ≪Обчислювач≫.Він вміє: множити число на 2 (*2); збільшувати число на 1 (+1). Треба скласти алгоритм отримання числа 100 з одиниці. Скільки дій у найкоротшому з таких алгоритмів? Розглянемо простішу задачу отримання з одиниці числа 4. Для її розв'язання можна використати алгоритм вигляду 1(+1)(+1)(+1) або 1(*2)(*2). Очевидно, що другий алгоритм коротший. Повернемося до попередньої задачі. Для отримання найкоротшого алгоритму перетворюємо число 100 у 1, використовуючи ділення на 2 і віднімання 1. Маємо

100 - > 50 - > 25 - ≫ 24 - > 12 - ≫ 6 - > 3 - > 2 - > 1.

Отже, для нашого виконавця алгоритм

1 (*2) (+1)(*2) (*2) (*2) (+1) (*2) (*2)

буде найкоротшим і містить 8 дій.

Виконавець ≪Маляр≫. ≪Маляр≫ може переміщуватися плоским полем, що розбитий на клітинки однакового розміру. Між клітинками поля можуть бути розташовані стіни, деякі клітинки можуть бути зафарбовані. Під час переміщення ≪Маляр≫ може зафарбовувати клітинки. Отже, виконавець може виконувати команди:

вгору

вниз

ліворуч

праворуч

зафарбувати.

Треба скласти алгоритм, при виконанні якого ≪Маляр≫ переміститься з клітинки А у клітку В і зафарбує клітинки, позначені крапками в полі:

 

А   В
   
       

 

Алгоритм розв'язування поставленої задачі такий:

вниз → праворуч → зафарбувати → праворуч → зафарбувати → вгору → зафарбувати → праворуч .

І, нарешті, складання програми для комп'ютера — це кінцевий етап розв’язування задачі. Якщо перший в більшій мірі абстрактно-математичний, то в останньому переважають моменти конкретно-виробничого характеру. Як влучно зазначив А.П.Єршов, ≪програміст мусить мати здатність першокласного математика до абстракції і логічного мислення в поєднанні з едісонівським талантом до створення чогось із нуля й одиниці≫ [21].

Якщо алгоритмічну мову вибирають, виходячи з власних бажань, то вибір мови програмування може диктувати певна реальність: замовник, комп'ютер, попередній досвід. У цьому посібнику розглядається одна з найбільш розповсюджених мов програмування — мова Сі. Створена 1972 року як мова для системного програмування, мова Сі дістала поширення у всьому світі. Сьогодні Сі має багатьох наступників серед виробничих мов програмування: C++, Java, C#. Приклади у курсі розглядаються з використанням системи Borland C++ v.3.1.

Іншою мовою, використаною у нашому посібнику, буде мова Паскаль, названа на честь великого французького вченого, який першим в світі 1642 року виготовив автоматичний пристрій для додавання чисел. Мова Паскаль створена у 1969 році Ніклаусом Віртом у Швейцарському технічному інституті у Цюріху спеціально для вивчення програмування. Сьогодні існує декілька варіантів мови Паскаль. Ми будемо дотримуватися версії системи Borland Pascal v.7.0.

 

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

 

Існують такі способи описання алгоритмів:

• словесний,

• формульний,

• графічний,

• алгоритмічною мовою.

Першій спосіб - це словесний опис алгоритму. Словесний опис потребує подальшої формалізації.

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

Третій спосіб - запис алгоритмів за допомогою блок-схеми. Цей метод був запропонований в інформатиці для наочності подання алгоритму за допомогою набору спеціальних блоків. Основні з цих блоків подані на рисунку 1.

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

Рисунок 1 – Блоки для подання блок-схем.

 

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

 

Розглянемо такі властивості алгоритмів: визначеність, скінченність, результативність, правильність, формальність, масовість.

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

Приклад 1.3. Невизначеність виникне в алгоритмі (х+у)/(а-b), якщо в знаменнику буде записано, наприклад, 92 - 92 (ділення на нуль неприпустиме).

Невизначеність виникне, якщо деяка команда буде записана неправильно, бо така команда не належатиме до набору допустимих команд виконавця, (х+у)/(а-b).

Скінченність алгоритму. Алгоритм повинен бути скінченним – послідовність команд, які треба виконати, мусить бути скінченною. Кожна команда починає виконуватися після закінчення виконання попередньої. Цю властивість ще називають дискретністю алгоритму.

Приклад 1.4. Алгоритм (х+у)/(а-b ) — скінченний. Він складається з трьох дій. Кожна дія, у свою чергу, реалізується скінченною кількістю елементарних арифметичних операцій. Нескінченну кількість дій передбачає математичне правило перетворення деяких звичайних дробів, таких як 5/3, у нескінченні десяткові дроби.

Результативність алгоритму. Алгоритм результативний, якщо він дає результати, які можуть виявитися і невірними.

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

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

Приклад 1.5. Наведені вище алгоритми є правильними. Помінявши місцями в алгоритмі з прикладу 1.2 будь-які дві команди, отримаємо неправильний алгоритм.

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

Приклад 1.6. Наведені алгоритми задовольняють цю умову, їх можуть виконати багато виконавців.

Масовість алгоритму. Алгоритм масовий, якщо він придатний для розв'язування не однієї задачі, а задач певного класу.

Приклад 1.7. Алгоритм з прикладу 1.1 не є масовим. Алгоритм Маляр є масовим, оскільки може застосовуватись не тільки для зафарбовування якихось елементів, але й для певних задач на графах. Прикладами масових алгоритмів є загальні правила, якими користуються для множення, додавання, ділення двох багатозначних чисел, бо вони застосовні для будь-яких пар чисел. Масовими є алгоритми розв'язування математичних задач, описаних у загальному вигляді за допомогою формул, їх можна викопати для різні їх вхідних даних.

 

ЛЕКЦІЯ № 2

 

Тема: Класи алгоритмів

 

Ціль: розглянути класифікацію алгоритмів за типами складності, основні визначення теорії алгоритмів: машина Тьюринга, рекурсія, теза Чорча

 

План

 

Машини Тьюринґа

Рекурсія та її використання

Машини Тьюринґа

 

Машина Тьюринґа, що була описана А.Тьюринґом 193 6 року, є теоретичною моделлю обчислювальної машини. Машину Тьюринґа (МТ) (рисунок 3) слід розглядати як одну з можливих формалізацій поняття алгоритму. її робота може бути описана таким чином.

Рисунок 3 – Схема машини Тьюринґа.

 

Розглянемо стрічку, розділену на окремі комірки; ця стрічка є потенційно нескінченною в обидва боки. У кожній комірці може бути записаний певний символ з деякого заданого алфавіту А. Машина Тьюринґа в будь-який момент часу може перебувати в певному стані (множина станів S є скінченною) і вказувати на певну комірку.

Машина Тьюринґа в залежності від поточного символа, на який вона вказує, може записати на його місце будь-який інший символ (він може співпадати зі старим), зсунутися на один символ вліво або вправо, змінити свій вміст чи зупинитися (часто вважається, що машина зупиняється автоматично, якщо немає жодної інструкції, яку вона могла б виконати). Робота машини Тьюринґа визначається її програмою.

Програма машини Тьюринґа є послідовністю інструкцій, кожна з яких має вигляд

aisj → akslI,

де ai, ak є A; sl, sm,S,I є {R,L,H}.

Цей запис читається так: якщо машина перебуває в стані sl і зчитує символ ai, вона повинна записати в поточну позицію символ ak, перейти до стану sm і зсунутися вправо (відповідає літері R), вліво (відповідає літері L) або зупинитися (відповідає літері H).

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

Приклад 1.9. Наведемо програму для машини Тьюринґа, яка обчислює функцію х+у, де х,у - натуральні числа. Необхідно домовитися про відображення цих чисел. Стандартним для машини Тьюринґа є подання натурального числа n послідовністю з n+1 одиниць.

Ідея реалізації такої програми могла б полягати у тому, щоб замінити крайній зліва та крайній справа символи ≪1≫ на ≪0≫, а роздільник ≪0≫ - на ≪1≫. Якби були доступні відповідні команди, це можна було б зробити просто і швидко, але ми обмежені жорсткими рамками машини Тьюринґа. За таких умов схема алгоритму полягає в такому: рухатися вправо до виявлення першої одиниці (початок першого числа); як тільки вона буде виявлена, замінити її на нуль і перейти в інший стан s1. Потім рухатися вправо, поки 0, який розділяє два числа, не буде замінений на 1; при цьому знову змінити стан. Далі рухатися вправо до появи першого нуля (кінця другого доданку). Після цього зсунутися вліво, замінити останню 1 на 0 та зупинитися.

Програма може мати вигляд:

 

Наведений приклад показує, що машина Тьюринґа є дуже незручною для програмування. Ці незручності пов'язані з тим, що:

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

• неструктурованють записів на стрічці; заздалегідь невідомо, де закінчується одне число і починається інше;

• дуже обмежений набір команд; відсутні, наприклад, основні арифметичні операції.

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

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

У інтуїтивному сенсі такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Тьюринґа служить одним із засобів обґрунтування універсальності конструкції Тьюринґа.

Реалізованість таких композицій доводиться у загальному вигляді, незалежно від особливостей конкретних алгоритмів А та В. Доведення полягає в тому, що вказується засіб побудови з програм А та В програми требаї композиції. Нехай, наприклад, треба побудувати машину А \cdot В, еквівалентну послідовному виконанню алгоритмів А та В. Поки виконується алгоритм А, у програмі A\cdot В працює частина А без урахування частини В. Коли алгоритм А дійде до кінця, то замість зупинки відбудеться перехід у перший стан частини В, і потім частина В буде працювати звичайним чином, наче частини А й не було.

Аналогічно конструюють й інші композиції машин Тьюринґа; щораз будуються загальні правила, які визначають, що на що змінювати у вихідних програмах.

Описуванняючи різноманітні алгоритми для машин Тьюринґа і стверджуючи реалізованість усіляких композицій алгоритмів, Тьюринґ переконливо показав розмаїтість можливостей запропонованої ним конструкції, що дозволило йому виступити з такою тезою:

Тьюринґа.

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

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

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

Рекурсія та її використання

 

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

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

До базових примітивних рекурсивних функцій відносяться три функції:

1) нуль-функція Z(x)=0 при будь-якому х;

2) додавання одиниці: N(x) = х+1;

3) проектуючі функції: Ui(xl,...,xn)=xi для всіх х1,...,хn.(визначає натуральне число з цієї множини).

Функція f(х1,…,хn) отримана з функцій g, h1,...,hm, за допомогою підстановки, якщо f(х1,…,хn) = g(h11,…,хn),...,hm1,…,хn)).

Функція f(х1,…,хn,y) отримана за допомогою рекурсії, якщо:

f(х1,…,хn,y+1)=h(х1,…,хn,y, f(х1,…,хn,y));

f(х1,…,хn,0)=g(х1,…,хn) при n≠0;

f(y+1)=h(y,f(y)); f(0)=k, k – ціле невід'ємне число при n = 0.

Функція f(х1,…,хn) отримана за допомогою µ-оператора, якщо її значення дорівнює мінімальному значенню у, при якому g(х1,…,хn,y)=0.

Частково рекурсивною називається функція, яка конструюється за допомогою скінченного числа підстановок, рекурсій та µ-операторів, але визначена не при всіх значеннях аргументів.

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

Приклад 1.10. Визначення функції ≪факторіал≫ задаються виразом: 0!=1, n!=nх (n-1)!. Вони утворюють множину {1,2,6,...}: 0!=1, 1!=1, 2!=2, 3!=6, ... . Усі її елементи, крім першого, визначаються рекурсивно.

Отже, функція ≪факторіал≫ задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Загалом, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності є прикладом рекурсивного означення.

Приклад 1.11. Арифметичні вирази зі сталими та знаком операції ‘+’ у повному дужковому записі (ПДЗ) задаються таким означенням:

1) стала є виразом у ПДЗ;

2) якщо Е і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.

Для коректного виходу з рекурсії повинні виконуватися умови:

ü множина означуваних об'єктів є частково упорядкованою;

ü кожна спадна за цим впорядкуванням послідовність елементів закінчується деяким мінімальним елементом;

ü мінімальні елементи означаються нерекурсивно;

ü неміпімшіьні елементи означаються за допомогою менших від них елементів.

Глибина рекурсії – кількість викликів підпрограми, що реалізують рекурсію.

Вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди треба писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Справа в тому, що виконання кожного виклику підпрограми потребує додаткових дій комп'ютера. Тому ≪циклічний≫ варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також нетреба вживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам'яті та аварійного завершення програми.

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

Приклад. 1.12. Маємо функцію, що розкладається у ряд:

 

.

 

#include <stdio.h>

#include<math.h>

double func1 (int n); // прототип нерекурсивної функції ряду

double func2(int n); // прототип рекурсивної функції ряду

void main()

{

int n; // n - кількість елементів ряду

double s=1; // значення функції

scanf("%n", &n); // ввели кількість елементів ряду

printf("Nonrecursiv result is %6.2f", func1(n));

printf("Recursiv result is %6.2f", func2(n));

}

double func1 (int n)

{

double s=1;

int x; // x - поточний член ряду

for(x=1;x<=n;x++)

s*=x/(exp(x) - x*x)

return (s);

}

double func2(int n)

{

double s=1;

if (n<1) // умова виходу з рекурсії

return (s);

else

s*=n/(exp(n) - n*n)*func2(n-1);// виклик рекурсивної функції з

n-1

}

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

Найяскравіший приклад задачі такого плану- задача про ханойські вежі.

Легенда свідчить, що десь в Ханої знаходиться храм, в якому розміщена така конструкція: на підставці знаходяться З діамантових стержня, на яких при створенні світу Брахма нанизав 64 золотих диска із отвором посередині, причому внизу опинився найбільший диск, на ньому трохи менший і так далі, поки на верхівці піраміди не опинився найменший диск. Жерці храму зобов'язані перекладати диски за такими правилами:

1) за один хід можна перенести лише один диск,

2) не можна класти більший диск на менший.

Керуючись цими правилами, жерці повинні перенести початкову піраміду з 1-го стержня на 3-й. Як тільки вони впораються з цим завданням, настане| кінець світу.

Для розв'язання задачі спочатку спробуємо побудувати абстрактну модель процесу перенесення частини піраміди.

Отже, вирішуємо узагальнену задачу: як перенести піраміду з n кілець із стержня i на стержень j, користуючись стержнем k як допоміжним? Ця задача розв'язується таким чином.

1. Перенести (n-1) кільце i на k.

2. Перенести 1 кільце з i на j.

3.Перенести (n-1) кільце на j.

Отже, задача перенесення n кілець розв'язується через перенесення (n-1) кільця. Залишилося лише додати тривіальну граничну умову для виродженого випадку перенесення порожньої піраміди з 0 кілець, щоб наш алгоритм завершився.

Реалізація алгоритму на мові С:

void Hanoj (int n, short і, short j , short k)

// перенесення піраміди з n дисків з стержня i

// на стержень j , використовуючи стержень k як допоміжний

{

//перевірка граничної умови - порожню піраміду не переміщувати

if (!n) return;

Hanoj (n-1, і, k,j);

// переносимо одне кільцо - фактично це Hanoj (1, і, j , k);

printf(≪%2d-%2d\n≫,i,j);

Hanoj (n-1, k, j , i);

}

 

ЛЕКЦІЯ № 3

 

План

 

Поняття структури даних

Рівні описування даних

СД у зовнішній пам'яті

Поняття структури даних

 

Структура даних (СД) - загальна властивість інформаційного об'єкта, з яким взаємодіє та або інша програма. Ця загальна властивість характеризується:

ü множиною допустимих значень цієї структури;

ü набором допустимих операцій;

ü характером організованості.

Найпростіші структури дацих називаються також типами даних.

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

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

Відома формула ≪Програма = Алгоритми + Структури даних≫ дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для опрацювання масиву даних визначає вибір тієї чи іншої структури даних для їх збереження, а навпаки.

 

Рівні описування даних

 

Розрізняють наступні рівні описуваннявання даних:

• абстрактний (математичний) рівень;

• логічний рівень;

• фізичний рівень.

Логічний рівень (ЛСД)– подання структури даного на тій чи іншій мові програмування.

Фізичний рівень (ФСД) — відображення у пам'ять комп'ютера інформаційного об'єкту відповідно до логічного описування.

Оскільки пам'ять комп'ютера обмежена, то виникають питання розподілу пам'яті й керування нею.







ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2023 zdamsam.ru Размещенные материалы защищены законодательством РФ.