Зубенко, Омельчук - Програмування. Поглиблений курс
.pdf
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА
В.В. Зубенко, Л.Л. Омельчук
ПР О Г Р А М У В А Н Н Я .
По г л и б л е н и й к у р с
Рекомендовано Міністерством освіти і науки України як навчальний посібник для студентів вищих навчальних закладів
К и ї в 2 0 1 1
УДК 519.85(075.8)
ББК 32.973.2-018я73 З 91
Рецензенти: М.М.Глибовець, д-р фіз.-мат.наук, проф.,
А.Ю.Дорошенко, д-р фіз.-мат.наук, проф.,
С.О.Лук’яненко, д-р тех. наук, проф., О.С.Бичков, канд.фіз.-мат. наук, доцент
Схвалено Вченою радою факультету кібернетики Київського національного університету імені Тараса Шевченка (протокол № 12 від 24. 06. 2008 )
Рекомендовано Міністерством освіти і науки України як навчальний посібник для студентів вищих навчальних закладів (лист № 14/18-Г-2030 від 29. 08. 08 )
В.В. Зубенко, Л.Л. Омельчук Програмування. Поглиблений курс. – К.:Видавничо-поліграфічний центр “Київський університет”, 2011. - 623 с. Бібліогр.: с. 602-609.
ISBN 978-966-439-380-2
Навчальний посібник містить поглиблений курс з основ інформатики та програмування, який у відповідності до Рекомендацій по викладанню інформатики в університетах
Computing Curricula 2001-2010: Computer Science має зв’язувати в єдине ціле ідеї програмування, дискретної математики, основ архітектури ЕОМ, теорії алгоритмів та математичної логіки. Перші дві частини присвячені ознайомленню з основними логіко-алгебричними дескриптологічними засобами та уточненню на їх основі основних понять інформатики та програмування. У третій описуються мови програмування С/C++. У четвертій розглядається низка класичних алгоритмів, які складають кістяк сучасного програмування. Викладення матеріалу супроводжується великою кількістю прикладів і задач для самостійної роботи.
Для студентів та аспірантів університетів відповідних спеціальностей.
© В.В. Зубенко, Л.Л. Омельчук, 2011 ©ВПЦ “Київський університет”, 2011
ПЕРЕДМОВА
Незважаючи на те, що дисципліна "Програмування" є однією з ба- зових у підготовці фахівців з інформаційних технологій, сьогодні в Україні (і не тільки) фактично немає сучасного підручника в цій галу- зі. Відповідно до "Рекомендацій із викладання інформатики в універ-
ситетах Computing Curricula 2001: Computer Science" [111] такий під-
ручник мав би бути синтетичним і поєднувати ідеї теорії програму- вання, дискретної математики, основ архітектури ЕОМ, теорії алго- ритмів і математичної логіки. Пропонований посібник є спробою зро- бити певний крок у цьому напрямі. Він містить поглиблений курс програмування з максимальним охопленням матеріалу, що відповідає
програмам CS101 B , CS102 B та CS103, які поєднують процедурне та
об'єктно-орієнтоване програмування.
Метою посібника є уточнення основних понять інформатики та програмування, формування на їхній базі певного лексикону, озна- йомлення з фундаментальними логіко-алгебраїчними дескриптологіч- ними засобами й мовами програмування високого рівня, деякими класичними алгоритмами.
Посібник складається зі вступу й чотирьох розділів. Останні поділяються на логічно завершені підрозділи. У вступі пропонуються означення інформатики та програмування як наукових дисциплін. На основі введеної термінології зроблено стислий огляд історії становлення інформатики та програмування. Окремий підрозділ присвячено історії інформатики в Україні. У двох перших розділах розглянуто фундаментальні логіко-алгебричні універсалії та елементи інформатики, у третьому – мови C/C++, які є важливими інструментами процедурного та об'єктно-орієнтованого програмування, у четвертому – класичні алгоритми, що становлять кістяк сучасного програмування.
Кожний підрозіл закінчується переліком додаткової навчальної та спеціальної літератури для поглибеної роботи над відповідними
темами, а також контрольними запитаннями та вправами. Символ "*"
позначає вправу підвищеної складності, а пара символів "** " – вправу дослідницького характеру.
ПРОГРАМУВАННЯ
Робота з посібником вимагає ґрунтовної математичної підготовки принаймні в обсязі середньої школи, а краще – перших двох курсів ВНЗ, елементарного знайомства з обчислювальною технікою й мовами програмування. Для кращого засвоєння матеріалу бажане паралельне вивчення нормативних курсів дискретної математики й алгебри з відповідним тематичним наповненням.
Посібник побудовано за принципом замкненості – у ньому можна знайти означення всіх численних допоміжних і базових понять математики та інформатики, що використовуються. Для цього передбачено спеціальний індексний покажчик.
Наукові погляди авторів формувалися під впливом світоглядних ідей акад. В. Н. Редька в галузі програмування та програмології, без яких поява даного посібника була б неможливою.
Автори висловлюють щиру подяку всім колегам з кафедри теорії та технології програмування факультету кібернетики Київського національного університету ім. Тараса Шевченка за плідні дискусії, які дали поштовх до написання посібника, і створення відповідних умов для роботи над ним; студентам – за їхні зауваження та пропозиції; М. М. Глибовцю, А. Ю. Дорошенку, С. О. Лук'яненку й О. С. Бичкову – за наукове рецензування; А. Б. Ставровському та О. В. Кривді – за допомогу й цінні поради, що сприяли суттєвому поліпшенню змісту та якості подання матеріалу.
Автори будуть вдячні за всі зауваження й побажання, які можна надсилати за адресою: 03022, Київ-22, просп. Акад. Глушкова, 2, ко- рпус 6, факультет кібернетики, або електронною поштою: vvz@unicyb.kiev.ua.
4
ВСТУП
¾Предмет вивчення інформатики
¾Програмування
¾Електронні обчислювальні системи
¾З історії інформатики
¾Становлення інформатики в Україні
Ключові слова: комунікативний процес, комунікативна система, запит, де- скриптивна система, екстенсіональні, інтенсіональні й мішані дескриптивні систе- ми, інформаційна система, інформатика як наука, програмування, мова програму- вання, дані, програма, ЕОМ, програмне забезпечення, електронна обчислювальна си- стема, інформаційні технології, парадигма програмування, програмна інженерія, теорія програмування, програмологія.
0.1. Предмет вивчення інформатики
Незважаючи на стрімкий розвиток інформатики протягом останніх кількох десятиріч, процес її самовизначення як науки все ще не можна вважати завершеним. Перебігає він досить суперечливо між кількома напрямами – інженерним, математичним, комунікативним тощо. Кожен із них має своє підґрунтя й зорієнтований на ті чи інші аспекти процесів обробки інформації.
Інженерний підхід розглядає інформатику як науку про комп'ютерні системи. Такий погляд домінував у період становлення інформатики, коли проектувались і створювались перші потужні комп'ютерні системи. Наприклад, відомі американські вчені А. Ньюел, А. Перліс і Г. Саймон проголосили предметом вивчення інформатики обчислювальні машини. Сьогодні даний підхід охоплює комплекс технологічних проблем, пов'язаних із проектуванням, розробкою й технічною експулуатацією обчислювальних систем, і має
ПРОГРАМУВАННЯ
загальну назву програмна інженерія. У комунікативному підході
першорядними є проблеми взаємодії між суб'єктами всередині комунікативних процесів.
Математичний підхід виникнув у останні десятиріччя, коли розпочалося тотальне проникнення інформаційних технологій у вci сфери життя суспільства та постала проблема різкого підвищення продуктивності й надійності праці в галузі продукування інформаційних технологій, а також суттєвого зниження їхньої вартості. Фактично вже йдеться про запровадження індустріальних методів не тільки в масове виробництво комп'ютерів, а й у виробництво програмного забезпечення для них. Подібне виробництво, з його всебічною автоматизацією, вимагає ґрунтовної математичної підтримки.
Наразі інформатику обслуговують багато розділів математики й математичної логіки, семіотики й математичної лінгвістики, і така тенденція буде зберігатись у майбутньому. Однак поряд із процесом обробки та засвоєння результатів суміжних дисциплін в інформатиці відбувається активний пошук і формування її власних основ. Створення такого фундаменту є однією з найактуальніших задач сучасної інформатики.
Що вивчає інформатика. На теренах СРСР під терміном інформа- тика розуміли спочатку так звану "бібліотечну" інформатику – спеціаль- ну наукову дисципліну, яка вивчає структуру й загальні властивості на- укової інформації, а також закономірності всіх процесів наукової кому- нікації – від неформальних процесів обміну такою інформацією до фор- мальних за допомогою наукової літератури, а сьогоднішню її проблема- тику вважали належною до кібернетики як науки про керування склад- ними системами. Д. Кнут у 1974 р. визначав інформатику як науку, що займається вивченням алгоритмів. Академік АН СРСР А. Єршов вва- жав інформатику фундаментальною природничою наукою, яка вивчає процеси передавання й обробки інформації. Французькі спеціалісти Б. Майер і К. Бодуен наводять два варіанти означення інформатики:
перший – як комп'ютерної науки, другий – як тeopiї обробки інформа-
ції. Відомі німецькі вчені Ф. Бауер і Г. Гооз посилаються на означення Французькою академією інформатики як науки про здійснювану за до-
помогою автоматичних засобів цілеспрямовану обробку інформації, що розглядається як подання знань і повідомлень у технічних, економічних і соціальних галузях. Близьким за змістом є ухвалене на сесії річних збо- рів АН СРСР у 1983 р. визначення інформатики як комплексної науко-
вої та інженерної дисципліни, що вивчає всі аспекти розробки, проекту- вання, створення, оцінки, функціонування заснованих на ЕОМ систем
6
ВСТУП
переробки інформації, їхнє застосування та дії на різні галузі соціальної практики. У сучасних джерелах основні напрями інформатики пов'я- зують із розробкою спеціальних комп'ютерних методів розв'язання складних дослідницьких i практичних задач у різних галузях, у тому чи- слі й гуманітарних, з розвитком інформаційних технологій і соціально- комунікативних процесів (роботи І.В. Сергієнка, В.С. Михалевича, Ю.М. Канигіна, В.І. Гриценка, А.В. Анісімова, С.В. Симовича та ін.). Та- ке різноманіття в підході до визначення предмета інформатики актуалі- зує проблему її самоідентифікації як наукової дисципліни.
Усі вищезгадані підходи можна було б спробувати об'єднати на ос- нові поняття моделі, виходячи з того, що будь-яка точна наука має справу з певними моделями природних чи суспільних явищ. Напри- клад, фізика вивчає фізичні моделі природних явищ, хімія – хімічні, кібернетика – моделі систем керування тощо. Цілком резонно постає питання: а які моделі мали б цікавити інформатику?
Усі означення інформатики тим чи іншим чином апелюють до про- цесів обробки інформації та систем, що їх реалізують. У подібних процесах обов'язковою є наявність (рис. 0.1):
1)певної сукупності інформаційних об'єктів (повідомлень та інфо- рмації, яку вони містять);
2)суб'єкта, що формує, передає та приймає певну вхідну й вихідну інформацію (суб'єкта-ініціатора);
3)суб'єкта, що приймає вхідну інформацію, за допогою певної вну- трішньої процедури перетворює її та повертає оброблену вихідну ін- формацію (суб'єкт-обробник).
Подібні процеси й системи, що їх реалізують, називаються комуні- кативними1. Кожний такий процес розгортається в певному часово- му просторі та складається з етапів. Етапи утворюють життєвий цикл процесу. Комунікативний процес має предметну область, яку складають первинні інформаційні об'єкти й певні співвідношення між ними. Розпочинається такий процес суб'єктом-ініціатором, який формує й передає спеціальними засобами (засобами зв'язку) суб'єкту- обробнику повідомлення, що містить запит на обробку певної вхідної інформації з предметної області. Запит, поряд із вхідною інформаці- єю, містить інформацію про мету обробки. Мета може бути сформу- льована або неявно – як вимоги до вихідної інформації, або явно – як детальний опис процесу обробки.
1 У кібернетиці подібні системи називають системами зі зворотним зв’язком.
7
ПРОГРАМУВАННЯ
Суб'єкт-ініціатор (предметна область)
Запити + |
Вимоги |
Результати |
Аргументи |
|
|
Кодування |
|
Декодування |
Вх. дані |
Внутрішня |
Вих. дані |
процедура |
|
|
|
|
Суб'єкт-обробник (Система Обробки Інформації)
Рис. 0.1
Запит оформлюється у вигляді певного набору дескрипцій2, зрозу- мілих суб'єкту-обробнику (напр., як сукупність алгоритмів чи про- грам). Останній приймає запит, виконує в межах певного часового інтервалу відповідну внутрішню процедуру для реалізації мети й по- вертає суб'єкту-ініціатору за допомогою засобів зв'язку оброблену ін- формацію. Зазвичай суб'єкт-обробник має власну систему інформа- ційних об'єктів, відмінну від предметної області, яка в кожний мо- мент часу перебуває в певному стані. Тому сам запит містить не вхід- ні об'єкти обробника, а їхні прообрази, які після кодування утворю- ють вхідні дані обробника. Це стосується й вихідної інформації, по- даної в заключному стані процесу обробки. Вона потребує декодуван- ня, щоб отримати дійсно результати запиту.
Комунікативні системи теж мають свій життєвий цикл, що склада- ється з певних етапів. Він розпочинається з початкового аналізу вхід- ної інформації та специфікації запиту і включає такі етапи, як проек- тування й побудову системи, обґрунтування її коректності, підготовку документації та, нарешті, безпосередньо експлуатацію системи.
На підставі сказаного можна було б у цілому визначити інформати-
ку як науку, що вивчає моделi комунікативних процесів і систем. Од-
нак, зважаючи на дискусійний характер обговорення, зробимо кілька зауважень щодо даного означення. Насамперед зазначимо, що в тако- му вигляді воно здається досить загальним і багатоаспектним. Моделi комунікативних процесів і систем можуть дуже різнитися й вимагати принципово різних підходів. Достатньо послатися на різноманіття кі-
2 Дескрипція (від англ. description – опис) – мовна конструкція, що замінює назву предмета, виражаючи його зміст іншими мовними засобами.
8
ВСТУП
бернетичних моделей систем (від автоматичного регулювання, імовір- нісних і статистичних моделей до нейрофізіологічних моделей керу- вання тощо). Тому було б доречно якимось чином обмежити їх.
Зауважимо, що інформація в комунікативній системі існує не сама по собі, а передається й отримується суб'єктами комунікативного процесу у вигляді певних дескрипцій. Це означає, що комунікативні процеси й системи за своєю суттю не можуть вивчатися поза межами їхніх дескриптивних засобів. Здається, що в центрі уваги інформати- ки мають бути не просто моделі комунікативних процесів і систем, а саме дескриптивні моделі. Дескриптивність моделі означає, що всі її інформаційні елементи можуть бути подані (описані) у межах певної дескриптивної системи (ДС).
ДС, у свою чергу, розподіляються на три класи – екстенсіональні, інтенсіональні й мішані. Інтенсіональні використовують індивідуаль- ні засоби – вони або прямо описують конкретну будову об'єкта (його сутність), або параметризований кістяк такої будови, який шляхом конкретизації (означення) параметрів перетворюється на об'єкт. Для екстенсіональних ДС характерні предикативні (об'ємні) засоби опису об'єктів і співвідношень. Різницю між екстенсіональними та інтенсіо- нальними засобами опису яскраво ілюструють натуральні числа. З одного боку, їх можна визначати як кардинальні числа через поту- жність множин (екстенсіональний підхід), а з іншого – індуктивно, за допомогою числа 0 і відповідної сукупності операцій збільшення на 1 (інтенсіональний підхід). Наприклад, число 3 інтенсіонально подаєть- ся як (((0 +1) +1) +1) тощо. Можна сказати, що при екстенсіональному підході здійснюється перехід на вищий рівень абстракції, при якому нівелюються індивідуальні риси конкретних об'єктів.
Мішані дескриптивні моделі систем можуть використовувати обидва засоби. Моделі систем будемо називати екстенсіональними, інтенсіона- льними або мішаними, якщо вони описуються відповідними ДС. Щоб підкреслити вагомість інтенсіональних елементів у мішаних моделях ко- мунікативних систем, останні теж будемо називати інтенсіональними за умови, що суб'єкт-обробник у них описується інтенсіонально, а для кож- ного запиту (навіть якщо він екстенсіональний) існує своя внутрішня процедура в моделі Виконавця, яка його реалізує (як у системах обробки інформації на базі обчислювальних машин). Виходячи з вищезазначено- го, запропонуємо таке визначення предмета інформатики:
Інформатика – це наука, що вивчає інтенсіональні моделi комунікативних процесів і систем.
За аналогією з математичними, фізичними та іншими моделями, мо- делі, що розглядаються в інформатиці, логічно було б назвати інформа-
9
ПРОГРАМУВАННЯ
тичними або, що більш звично – інформаційними. З урахуванням інте- нсіональності будемо говорити й про інформаційні комунікативні про- цеси та системи й називати їх просто інформаційними. Інтенсіональ- ність інформаційних моделей є їхньою принциповою рисою. Вона фік- сує границі інформатики та вберігає її від надмірного узагальнення й ототожнення з іншими науками3, особливо з кібернетикою як наукою про загальні закони перетворення інформації в комунікативних систе- мах та інформологією – узагальнюючою наукою про інформацію в ціло- му, усі її вияви, властивості й види інформаційних процесів.
Взаємовідносини між кібернетикою та інформологією, з одного бо- ку, та інформатикою – з іншого, приблизно такі, як між загальним поняттям і його конкретизацією. Як приклад можна навести взаємо- відносини між загальною теорією груп і теорією скінченно- визначених груп, між геометрією та скінченною геометрією тощо. Та- ким чином, не можна вважати, що кібернетика просто поглинається інформатикою, чи намагатися звести інформатику до певної техніч- ної галузі (програмної інженерії), яка тільки обслуговує кібернетику. Не йдеться й про ігнорування інформатикою взагалі екстенсіональ- них дескриптологічних засобів. Навпаки, вони можуть (і повинні!) широко використовуватись як допоміжні, наприклад при описі пред- метних областей, формулюванні запитів тощо. Однак подібні дескри- пції не є основою інформаційних систем. Водночас вони можуть бути центральними в тих самих кібернетичних моделях.
0.2. Програмування
Розглянемо тепер одне з головних понять інформатики – програмуван- ня. Зазвичай при визначенні програмування апелюють до тих чи інших його аспектів. Найчастіше його трактують як процес написання (конс- труювання) або побудови програм для розв'язання певної задачі за допо- могою ЕОМ. Останній варіант хоч i більш вдалий, але теж не може вва- жатися цілком задовільним, оскільки потребує, у свою чергу, з'ясування, що таке задача тощо. Змістовнішим виглядає таке означення:
Програмування – це процес реалізації життєвого циклу інформаційних систем.
3 У зв’язку з цим знову доречно нагадати про алгоритми як об’єкт вивчення інформа- тики за Д. Кнутом.
10