Вступ
За
визначенням
А.П.Єршова,
інформатика -
це наука про
методи
представлення,
накопичення,
передачі і
обробки
інформації
за допомогою
електронно-обчислювальних
машин (ЕОМ). Що
таке
інформація?
Незважаючи
на те, що
поняття
інформації є
наріжним
каменем
всієї науки
про
обчислювальну
техніку, на це
питання не
може бути
дано
однозначної
відповіді. У
цьому
значенні
поняття
"інформація"
в
інформатиці
схоже з
поняттям "точка",
"пряма" і
"площина" в
геометрії -
все це
невизначені
терміни, про
які можуть
бути зроблені
деякі
твердження і
висновки, але
які не можуть
бути
пояснені в
термінах
більш елементарних
понять.
Вважається,
що інформація
- це поняття,
що
передбачає
наявність матеріального
носія
інформації,
джерела і
передавача
інформації,
приймача і
каналу
зв'язку між
джерелом і
приймачем
інформації.
Наука
інформатика
знаходиться
зараз на
етапі свого
становлення,
її зміст і методи
формуються у
нас на очах.
Однак вже зараз
можна
виділити
ядро, назвемо
його загальною
інформатикою,
куди
віднесемо
питання
постановки
задач, їх
алгоритмізації
і програмування.
Основними
в загальній
інформатиці будуть
три поняття:
задача,
алгоритм,
програма.
Відповідно,
маємо три
етапи в
розв’язуванні
задач
(помітимо, що
з точки зору
інформатики
розв’язати
задачу - це
отримати
програму,
тобто по суті
забезпечити
можливість рішення
з допомогою
ЕОМ):
постановка
задачі, побудова
і
обгрунтування
алгоритму,
складання і
налагодження
програми.
Оскільки програма
- об'єкт
гранично
формальний, а
тому точний,
(можливо не
завжди
прозорий,
навантажений
неістотними
із
змістовної
точки зору деталями,
але
недвозначний)
то пов'язані
з нею об'єкти
також
повинні бути
точними. Алгоритм
містить
чіткий і
ясний спосіб
побудови
результатів
за точно
вказаній в
постановці
задачі
залежності
їх від
наявних аргументів.
Відповідно
етапам маємо
три групи засобів
інформатики:
специфікація,
алгоритмізація
і
програмування.
Для
специфікації
задач в курсі
застосовані
засоби типу
рекурентних
співвідношень,
рекурсивних
визначень, а
також прості
інваріантні
співвідношення,
початкові і
кінцеві
умови.
Побудова
алгоритму за
точною
постановкою
задачі дає
можливість
його
обгрунтування
математичними
методами.
Більш того,
існують
класи задач,
які
дозволяють
формальне
перетворення
специфікації
в алгоритм.
Вивченню
деяких таких
класів і
відповідних
методів
відводиться
важливе
місце в
нашому курсі.
Істотно,
що порівняно
з програмою алгоритм
може
знаходитися
на більш
високому
рівні
абстракції,
бути вільним
від тих або
інших
деталей
реалізації,
пов'язаних з
особливостями
мови
програмування
та конкретної
обчислювальної
системи.
Засоби,
прийняті для
зображення
алгоритмів,
по традиції
називають
алгоритмічною
мовою. Між
іншим, так
називалися
також перші мови
програмування
високого
рівня, наприклад,
Алгол - це
просто
скорочення ALGOrithmic Language -
алгоритмічна
мова. Але,
взагалі кажучи,
жодна мова
програмування
не може цілком
замінити
алгоритмічну
мову, оскільки
консервативна
по своїй
суті.
Стабільність
- одна з
необхідних
компонент
якості мови
програмування.
Повинні бути
гарантії, що
всі програми,
складені
учора, в
минулому році,
десять років
тому, не
втратять
значення ні сьогодні,
ні завтра.
Модифікація
мови програмування
призводить
до небажаних
наслідків:
вимагає
переробки
системи
програмування,
знецінює
напрацьоване
програмне забезпечення.
У той же час
алгоритмічна
мова може створюватися
спеціально
для певної
предметної
області,
певного
класу задач
або навіть
окремої
задачі. Вона
може
розвиватися
навіть при
створенні
алгоритму,
вбираючи в себе
новітні
результати.
Алгоритм
- точне
формальне
розпорядження,
яке
однозначно
визначає
зміст і
послідовність
операцій, що
переводять
задану
сукупність
початкових
даних в
шуканий
результат
або можна
також сказати,
що алгоритм -
це кінцева
послідовність
загальнозрозумілих
розпоряджень,
формальне
виконання
яких
дозволяє за
кінцевий час
отримати
рішення
деякої
задачі або
будь-якої
задачі з
деякого
класу задач.
Слово
алгоритм походить
від algorithmi -
латинської
форми
написання
імені великого
математика IX ст.
Аль-Хорезмі,
який
сформулював
правила виконання
арифметичних
дій.
Розглянемо,
наприклад,
відому
задачу про
людину з
човном (Л),
вовком (В),
козою (Кз) і
капустою (Кп).
Алгоритм її
розв’язку
можна
представити
таким чином:
{ Л, В,
Кз, Кп -> } -
початковий
стан
пливуть
Л, Кз, Кп
{ У ->
Л, Кз, Кп } - 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 дій.
Виконавець
"Маляр".
"Маляр" може
переміщуватися
по плоскому
полю,
розбитому на
клітки
однакового розміру.
Між клітками
поля можуть
бути розташовані
стіни, деякі
клітки
можуть бути зафарбовані.
Під час
переміщення
"Маляр" може
зафарбовувати
клітки. Отже,
виконавець
може
виконувати
команди:
вгору
вниз
ліворуч
праворуч
зафарбувати.
Потрібно
скласти
алгоритм, при
виконанні якого
"Маляр"
переміститься
з клітки А в клітку
B і
зафарбує
клітки,
відмічені
точками в полі
-т---т---т---т---т-
¦ А - ¦. - B ¦
-+---+---+---+---+-
¦ ¦.
-. ¦ ¦
-+---+---+---+---+-
Алгоритм
розв’язку
поставленої
задачі наступний:
вниз
праворуч
зафарбувати
вгору
праворуч
зафарбувати
вниз
зафарбувати
праворуч
вгору.
І нарешті
складання
програми для
ЕОМ - це заключний
етап рішення
задачі. Якщо
перші два в
більшій мірі
абстрактно-математичні,
то в
останньому
переважають
моменти
конкретно-виробничого
характеру. Як
влучно помітив
А.П.Єршов,
"програміст
повинен
володіти
здатністю
першокласного
математика
до абстракції
і логічного
мислення в
поєднанні з едісонівським
талантом до
створення
чого-небудь з
нуля і
одиниці"
(А.П.Єршов
"Людський
чинник у
програмуванні").
Якщо
алгоритмічну
мову
вибирають, виходячи
з власних
бажань, то
вибір мови
програмування
можуть
диктувати
певна
реальність:
замовник,
комп'ютер, попередній
досвід. У
цьому курсі
розглядається
одна з
найбільш
рогзповсюджених
мов програмування
- мова Сі.
Створена у 1972
році як мова
для
системного
програмування,
мова Сі
дістала
поширення у
всьому світі.
Сьогодні Сі
має багатьох
наступників
серед виробничих
мов
програмування:
C++, Java, C#.
Приклади у
курсі
розглядаються
з використанням
системи Borland C++ v.3.1.
Мові
Сі все ж
відводиться
другорядна
роль. Іншою, а
точніше основною,
мовою в
загальному
курсі
інформатики
буде мова
Паскаль,
названа в
честь великого
французького
вченого, який
першим в світі
у 1642 році
виготував
автоматичний
пристрій для
додавання
чисел. Мова
Паскаль була
створена у 1969
році
Ніклаусом
Віртом в Швейцарському
технічному
інституті у
Цюріху
спеціально
для вивчення
програмування.
Сьогодні
існує
декілька
варіантів
мови Паскаль.
Ми будемо
дотримуватися
версії системи
Borland Pascal v.7.0.
При
записі
структур
керування у
мовах рядки
символів
будемо брати
у кутові
дужки <...>, а
необов'язкові
параметри - у
квадратні [...].
Для багатьох
задач наводяться
програми на
мові Паскаль
(в кінці номера
програми
стоїть
символ Р) і на
мові Сі (- символ
С). Практична
робота на ЕОМ
- необхідне доповнення
до
лекційного курсу.
Мінімальна
кількість
задач для самостійного
розв’язку
наводиться в
окремому
розділі в
кінці кожної
частини. Він
не є догмою,
але швидше
орієнтованим
для додаткового
підбору
типових
задач із
задачників,
що
використовуються,
і
практикумів.
Не заважає також
розібрати на
ЕОМ приклади,
розв’язані у
тексті.