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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

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