Вступ

Поняття алгоритму інтуїтивно зрозуміло та часто використовується в математиці та інформаційних тенологіях, зокрема в комп’ютерних науках, системному аналізі та розробленні інформаційних систем. Термін «інформація» походить від латинського слова «informatio» – виклад, роз`яснення фактів, подій. Тому, в найширшому розумінні інформація трактується як відомості, пояснення, знання про об’єкти, явища та процеси реального світу. Доволі розповсюдженим є погляд на інформацію як на ресурс, аналогічний енергетичним, матеріальним, трудовим і грошовим ресурсам. Інформацію не можна відокремити від процесу інформування. В основі цього процесу лежить взаємозалежність пари об’єктів – джерела і споживача інформації. Джерелами інформації, насамперед, є природні об’єкти: люди, тварини, рослини, планети тощо. Разом із цим, у міру розвитку науки і техніки, джерелами інформації стають наукові експерименти, машини, апарати, технологічні процеси. Значний також перелік об’єктів, що є споживачами інформації: люди, тварини, рослини, різноманітні технічні пристрої тощо. Погляд на інформацію з точки зору її споживачів окреслюється у наступному понятті інформації. Інформація – це нові відомості, прийняті, зрозумілі і оцінені її користувачем як корисні. Іншими словами, інформація – це нові знання, які отримує споживач (суб’єкт) в результаті сприйняття і опрацювання певних відомостей, тобто у результаті застосування до цих відомостей адекватних методів оперування ними (термін «адекватний» означає цілком відповідний; прирівняний; той, що влаштовує). Адекватність є надзвичайно важливою вимогою до методів, які застосовуються до наявної інформації з метою отримання нової інформації. Так, для сприйняття відомостей, викладених на аркуші паперу незнайомою іноземною мовою, адекватним може бути метод перекладу зі словником. У той же час, для сприйняття усної іноземної мови цей метод є явно не адекватним і має бути застосований метод синхронного перекладу. Інформатика використовує своє власне тлумачення терміну «інформація», яке є значно вужчим, ніж розглянуті вище. Це зумовлене тим, що при визначенні цієї категорії, інформатика не може базуватися на таких поняттях як знання, відомості, усунення невизначеності. Засоби комп’ютерної техніки володіють здатністю опрацьовувати інформацію автоматично, без участі людини, і про жодні знання або незнання тут мова йти не може. Ці засоби можуть працювати зі штучною, абстрактною і навіть із хибною інформацією, яка не має об’єктивного відображення ні у природі, ні у суспільстві. Враховуючи зазначену специфіку комп’ютерної техніки, інформатика вилучає змістовні аспекти поняття інформації і використовує погляд на інформацію як на предмет певної діяльності. Найконцентрованіше це виражається у наступному понятті інформації. Інформація – це відомості, які є об’єктом збирання, реєстрації, збереження, передавання і перетворення.

Основна маса інформації збирається, передається і опрацьовується у знаковій формі – числовій, текстовій, табличній, графічній і т.ін. Знакове подання інформації інформатика пов’язує з поняттям «дані». Дані – це відомості, подані у певній знаковій формі, придатній для передавання, інтерпретації та опрацювання людиною або автоматичним пристроєм. Взаємозв’язок між інформацією, даними і методами оперування ними характеризується низкою властивостей. Інформація має динамічний характер. Вона не є статичним об’єктом, а динамічно змінюється й існує тільки у момент взаємодії даних і методів, тобто в момент протікання інформаційного процесу. Весь інший час вона перебуває у стані даних. Зв’язок даних і методів носить діалектичний характер. Дані є об’єктивними, коли вони виникають у результаті реєстрації об’єктивно існуючих сигналів, викликаних змінами в матеріальних тілах або полях. У той же час, методи оперування даними в інформаційних процесах є суб’єктивними. Дійсно, інформаційний процес здійснюється за допомогою штучних або природних методів, в основі штучних методів лежать алгоритми, складені і підготовлені людьми (суб’єктами), в основі природних – біологічні властивості суб’єктів інформаційного процесу. Дані надають інформацію лише в момент їх використання. Це означає, що збережувані дані залишаються лише даними доти, поки їх не використано в тих чи інших методах деяким суб’єктом інформаційного процесу (людиною або автоматичним пристроєм). Якщо дані зовсім не використовуються, то говорять, що вони мають нульову інформативність, і вважають такі дані інформаційним шумом. Дані, що використовуються, називають інформативними. Рівень інформативності даних залежить від ступеня адекватності методів, що застосовуються в інформаційних процесах. Дані сприймаються їх отримувачем як певна змістовна інформація лише в тому випадку, коли в його «пам’яті» закладені поняття і моделі, що дозволяють зрозуміти зміст отриманих відомостей. Коли дані опрацьовуються певними методами або евристиками, то на їх основі можна встановити залежності, послідовності чи висновки, які дозволяють здійснити підтримку процесу прийняття рішення.

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

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

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

Говорячи неформально, алгоритм (algorithm) – це довільна коректно визначена обчислювальна процедура, на вхід якої подається деяка величина або набір величин, а результатом виконання якої є вихідна величина або набір значень. Таким чином, алгоритм є послідовністю обчислювальних кроків, які перетворюють вхідні величини у вихідні. Походження слова алгоритм: понад тисячу років тому у Багдаді жив Абу Джафар Мухамад ібн Муса аль-Хорезмі, який у своїй праці «Трактат аль-Хорезмі про арифметичне мистецтво індусів» з арифметики та алгебри сформулював правила і окреслив послідовність дій при додаванні та множенні чисел. При переведенні латиною ім’я автора трансформувалося в Algorithmi, а з часом методи розв’язування задач стали називати алгоритмами.

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

Модифікація алгоритмічної мови, очевидно відповідної зміни іншого математичного об’єкту.

У цьому посібнику розглядається одна з найбільш розповсюджених мов програмування – мова С. Створена  1972 року як мова для системного програмування, вона отримала широке поширення у всьому світі. Сьогодні С має багатьох наступників серед мов програмування: C++, Java, C#.

Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування теорії алгоритмів та основ програмування, розроблення прикладних засобів та інформаційних систем аналізу та опрацювання інформації за допомогою алгоритмів. Викладення матеріалу супроводжується значною кількістю прикладів, що полегшує його сприйняття та засвоєння. Навчальний посібник призначається для студентів, що навчаються за спеціальностями 122 «Комп’ютерні науки та інформаційні технології», 124 «Системний аналіз» та 126 «Інформаційні системи та технології» і споріднених спеціальностей, які пов’язані з вивченням чисельних методів в інформатиці та інформаційних технологій. Може бути використаний аспірантами як підґрунтя для наукових досліджень та викладачами як дидактичний матеріал, а також для самостійного вивчення та підвищення кваліфікації. Книга призначена для спеціалістів із проектування, розроблення та впровадження інтелектуальних систем опрацювання інформаційних ресурсів, науковців у галузі глобальних інформаційних системи, систем штучного інтелекту, Інтернет-технологій, фахівців з електронної комерції, Інтернет-маркетингу та Інтернет-реклами, менеджерів комплексних Web-проектів, а також для здобувачів 3-ого (освітньо-наукового) рівня вищої освіти в галузі знань 12 «Інформаційні технології». Кожний розділ закінчується переліком питань для самоконтролю, прикладом тестових питань з відповідями з екзаменаційних білетів та перелік індивідуальних завдань для виконання лабораторних робіт. У кінці навчального посібника приведені приклади комп’ютерних проектів для виконання розрахункових та курсових робіт з дисципліни «Алгоритмізація та програмування».

Розділ 1 присвячений елементам обчислювальних машин та описує. архітектуру комп’ютерів. Більш детально пояснені архітектурні принципи Джона фон Неймана та позиційні системи числення (двійкова, вісімкова, шістнадцяткова система числення, та взаємозв’язок між ними). Розкрито поняття алгоритму та способи його подання. Описані машинні та високорівневі мови програмування. Розділ 2 знайомить нас з історією розвитку мови С та з основним засадами програмування як алфавіт мови С, структура програми, типи даних, змінні та константи. Розділ 3 присвячений основним операторам та операціям в мові С (оператор присвоєння, арифметичні операції, перетворення типів та операції відношень та логічні операції). В розділі 4 пояснено поняття розгалуження, описані оператори безумовного та умовного переходу, а також оператор вибору варіантів. Поняття ітерації та циклу описано в розділі 5: з параметром, з передумовою, з післяумовою та оператори переривання циклів. Вказівники та посилання подані в розділі 6: основні поняття, операції з вказівниками та вказівники на вказівники. Розділ 7 присвячений створенню підпрограм. Описано поняття підпрограми, параметри та їх види, статичні змінні, процес передавання параметрів функцій (параметри-значення, параметри-вказівники, параметри-посилання, параметри зі значеннями за замовчуванням, імена функцій як параметри), вбудовані функції та функції зі змінною кількістю параметрів. У розділі 8 визначено поняття рекурсії та рекурентних співвідношень.

Розділ 9 присвячений модульному програмуванню. Тут описано основні поняття модульного програмування, включення файлів, проблема подвійного включення, умовна компіляція та зовнішні змінні. Розділ 10 знайомить з поняттям масиву. Розглянуто одновимірні масиви (оголошення одновимірних масивів, операції над вказівниками на масиви, введення-виведення одновимірних масивів) і багатовимірні масиви (двовимірні та тривимірні масиви), а також опрацювання масивів у функціях. В розділі 11 описані загальні поняття динамічної пам’яті, функції для роботи з динамічною пам’яттю, динамічні одновимірні масиви, динамічні двовимірні масиви (реалізований як одновимірний або як двовимірний) та опрацювання динамічних масивів у функціях.

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

Розділ 15 присвячений динамічним структурам даних та алгоритмам їх опрацювання, тобто спискам, чергам, стекам та бінарним деревам. В розділі 16 описана загальна класифікація алгоритмів пошуку та основні відомі алгоритми пошуку такі як лінійний, двійковий (бінарний) пошук елемента в масиві, методом Фібоначчі, М-блоковий, бінарний пошук із визначенням найближчих вузлів, прямий пошук рядка, алгоритма Ахо-Корасика, Моріса-Прата. Кнута, Моріса і Пратта, Рабіна-Карпа, Боуера і Мура, Хорспула. Розділ 17 розкриває основні алгоритми сортування як сортування обміном (метод бульбашки), вставкою (включенням), прямим вибором та швидке (метод Хоара). Приділено також увага сортуванню включенням зі спадним приростом (метод Шелла), сортуванню за допомогою дерева (пірамідальне сортування) та сортування злиттям. Розділ 18 присвячний нелінійним структура дани та алгоритмам ї опрацювання.

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

Гожому О.П. – доктору технічних наук, професору кафедри комп’ютерної інженерії Чорноморського національного університету імені Петра Могили;

Голощуку Р.О. – кандидату технічних наук, доценту кафедри соціальних комунікацій та інформаційної діяльності Інституту гуманітарних та соціальних наук Національного університету «Львівська політехніка»;

Григоровичу В.Г. – кандидату технічних наук, доценту кафедри інформаційних систем і технологій Дрогобицького державного педагогічного університету імені Івана Франка;

Кравцю П.О. – кандидату технічних наук, доценту кафедри інформаційних систем та мереж Національного університету «Львівська політехніка»;

Литвиненку В.І. – доктору технічних наук, професору, завідувачу кафедри інформатики і комп’ютерних наук Херсонського технічного університету;

Литвину В.В. – доктору технічних наук, професору, завідувачу кафедри інформаційних систем та мереж Національного університету «Львівська політехніка»;

Марікуці У.Б. – кандидату технічних наук, доценту кафедри систем автоматизованого проектування, декану базової вищої освіти, заступник директора інституту компютерних наук та інформаційних технологій Національного університету «Львівська політехніка»;

Бісікалу О.В. – доктору технічних наук, професору, завідувачу кафедри автоматики та інформаційно-вимірювальної техніки Вінницького національного технічного університету;

Шароновій Н.В. – доктору технічних наук, професору, завідувачу кафедри інтелектуальних комп’ютерних систем Національного технічного університету «ХПІ»;

Шаховській Н.Б. – доктору технічних наук, професору, завідувачу кафедри систем штучного інтелекту Національного університету «Львівська політехніка».;

Шпак З.Я. – кандидату технічних наук, доценту кафедри автоматизованих систем управління Національного університету «Львівська політехніка».

(Для ознайомлення з повним текстом статті необхідно залогінитись)