Ніжинський державний університет

імені Миколи Гоголя

М. С. Нікітченко теорія програмування Частина 1

Навчальний посібник

Ніжин-2010

УДК 004.4

ББК 22.18я73

Н 62

Рекомендовано вченою радою

Ніжинського державного університету імені Миколи Гоголя

Протокол № 3 від 02.11.2010 р.

Рецензенти

д-р фіз.-мат. наук Бєлов Ю.А.

д-р фіз.-мат. наук Буй Д.Б.

Нікітченко М.С.

Н 62 Теоретичні основи програмування: [навчальний посібник] / М. С. Нікітченко. – Ніжин: Видавництво НДУ імені Миколи Гоголя, 2010. – _____ с.

Викладено теоретичні основи програмування. Матеріал подано в семантико-синтаксичному стилі на основі єдиного для програмування, математичної логіки та теорії алгоритмів композиційно-номінативного підходу. Викладення проілюстровано прикладами, у кінці розділів запропоновано питання для самоконтролю та вправи для самостійного розв’язання.

Для студентів спеціальностей «Інформатика», «Прикладна математика», «Системний аналіз».

ББК 22.18я73

 Нікітченко М.С., 2010

ВСТУП

Інформаційні технології застосовуються зараз практично у всіх сферах життя людства. Ці технології докорінно змінили світ. Значні успіхи в телекомунікаціях, енергетиці, транспорті, медицині, освіті, космічних дослідженнях та інших сферах діяльності людства досягнуто завдяки використанню інформаційних технологій. Однак таке розширення сфери їх застосувань має і негативну сторону. Людство стає все більш залежним від надійного і правильного функціонування комп’ютерних систем; помилки в їх роботі часом ведуть до величезних фінансових, а навіть і людських втрат. Дотепер фірми-розробники програмного забезпечення не дають гарантію на програмні продукти, які вони пропонують користувачу. Але такого фактично немає в жодній іншій сфері діяльності. Будь-який легальний продавець якогось товару дає гарантії якості і готовий нести (пригадаємо повернення мільйонів автомобілів на заводи виробника у разі виявлення дефектів) фінансову і юридичну відповідальність за поставку недоброякісного продукту.

Можна навести і безліч інших прикладів, коли погане програмне забезпечення призводило до знищення космічних ракет, аварій на заводах, гідроелектростанціях тощо. Про складний стан справ говорять і самі фахівці галузі комп’ютерних технологій. У чому ж причини? Вони, безумовно, різноманітні і пов’язані з науковими, економічними, соціальними, психологічними та іншими проблемами створення і використання інформаційних технологій. Серед наукових однією з найважливіших є проблема створення ефективних методів розробки програмних систем. Такі методи мають базуватися на розвиненій теорії програмування, яка має на меті дослідження програм та методів їх аналізу і синтезу. Відзначимо, що тут термін «програма» тлумачиться у широкому смислі, охоплюючи, зокрема, як програми конкретних мов програмування, так і великі програмні системи.

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

Щоб надати початкове уявлення про цю дисципліну, треба визначити її мету і завдання, об’єкт та предмет, а також вказати на її основні методи.

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

Об’єктом навчальної дисципліни «Теорія програмування» є програми, а її предмет включає в себе вивчення основних (базових) понять теорії програмування, розгляд основних аспектів програм (семантика та синтаксис), їх формалізацію та дослідження, а також уточнення основних методів розробки програм.

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

Місце у структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна «Теорія програмування» є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня «бакалавр». Курс теорії програмування потрібен для подальшого вивчення нормативних дисциплін «Системне програмування», «Бази даних та інформаційні системи», «Інтелектуальні системи», «Теорія обчислень», «Штучний інтелект», «Формальні методи розробки програмних систем», «Інформаційні технології», «Прикладна логіка», низки спецкурсів відповідного напряму.

Суть теорії програмування – категоріальний (поняттєвий) аналіз процесу програмування. Поняття визначаються у єдності їх двох моментів: змісту (інтенсіоналу) та обсягу (екстенсіоналу). Тому в курсі так багато часу приділяється аналізу основних понять програмування і розкриттю їх інтенсіоналів та екстенсіоналів. Звідси випливає, що для теорії програмування найважливішим є не конкретна програма, а відношення між програмними поняттями (тобто не стільки предметна, екстенсіональна складова, скільки логічна, інтенсіональна). Тому вміння писати конкретні програми ще не означає розуміти теорію програмування. Тут є аналогія з політикою, бо задача політики є не стільки безпосередня робота з пересічною людиною, скільки вибудова суспільних відносин.

Структура курсу:

• формалізація простої мови програмування;

• основні програмні поняття;

• синтактика;

• семантика;

• методи розробки програм.

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

Назва курсу «Теорія програмування» складається з двох термінів – «теорія» та «програмування». Існують різні підходи до побудови теорій. Щоб зрозуміти особливості теорії програмування сформулюємо декілька загальних запитань щодо властивостей теорій.

Яке значення та роль теорії?

Яку теорія потрібна (за побудовою)?

Яким методом будувати теорію?

Коротко відповісти на ці запитання можна наступним чином.

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

Відповідаючи на друге запитання, відзначимо, що існують різні підходи до побудови теорій: історичний, логічний, еволюційний тощо. Тут зосередимось на розгляді феноменологічного та сутнісного підходів. Феноменологічний підхід має на меті описати зовнішні прояви певних процесів, а сутнісний – їх внутрішні причини. Хоча ці підходи мають багато спільного, ми основну увагу будемо приділяти сутнісному підходу.

Трете питання пов’язане з вибором методи побудови теорії. Зважаючи на те, що основні методи побудови програм (систематичний, зверху-вниз, структурний тощо) орієнтовані на поступове уточнення програм, будемо використовувати метод побудови теорії від абстрактного до конкретного (від простого до складного).

Таким чином, основними принципами побудови теорії програмування будуть

принцип єдності теорії та практики,

принцип побудови сутнісної теорії,

принцип побудови теорії методом від абстрактного до конкретного.

Інші принципи будемо обговорювати пізніше.

Автор вдячний студентам факультету кібернетики Київського національного університету імені Тараса Шевченка та студентам Ніжинського державного університету імені Миколи Гоголя за участь у підготовці прикладів.

Закінчення доведення теорем, лем, прикладів або зауважень, позначаємо знаком _▄ .