МОВИ ПРОГРАМУВАННЯ М.Глибовець glib@ukma.kiev.ua 463-69-85

- M.: Вид. будинок , 2000.
Бадд Т. Об'єктно-орієнтоване програмування

в дії. - СПб.: Пітер Паблішинг, 1997.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми: побудова й аналіз. - M.: МЦНМО, 2000.
Кушніренко А.Г., Лебедєв Г.В. Програмування для математиків. - М., Наука, 1988.
Вирт Н. Систематическое программирование. Введение-М.: Мир,1977.-183с. ,
Вирт Н. Алгоритмы + Структуры данных = Программы. -М.:Мир,1985.-406с.,

він…

Вступ

Інформатика - це наука про методи представлення, накопичення, передачі

і обробки інформації за допомогою електронно-обчислювальних машин (ЕОМ).
А.П.Єршов

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

передбачає
наявність матеріального носія інформації,
джерела і передавача інформації,
приймача

і каналу зв'язку між джерелом і приймачем інформації.

методи формуються у нас на очах.
можна виділити ядро, назвемо

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

Маємо три етапи в розв’язуванні задач (помітимо, що з точки

зору інформатики розв’язати задачу - це отримати програму, тобто по суті забезпечити можливість рішення з допомогою ЕОМ):
постановка задачі,
побудова і обгрунтування алгоритму,
складання і налагодження програми.

не завжди прозорий, навантажений неістотними із змістовної точки зору деталями,

але недвозначний) то пов'язані з нею об'єкти також повинні бути точними.

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

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

задачі, для яких не існує алгоритму розв`язку?
Тьюрінгом було доведено,

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

є прагнення розробляти ефективні алгоритми вирішення якомога ширших класів задач.

Історичний досвід розвитку математики, практика розв`язку багатьох проблем показали, що загальність методу і його ефективність знаходяться в постійному антагонізмі: виграємо в одному  програємо в іншому.

вирішенні конкретних задач із застосуванням ЕОМ важливо знати:
можна в ідеалі

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

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

булевських n-мірних векторів. Такі задачі називаються перебірними.
Число кроків перебору росте експоненційно в залежності від розміру задачі.
Для деяких задач із цього класу вдається побудувати алгоритми, що виключають повний перебір варіантів (знаходження паросполук в графі). Але число таких задач невелике.

дискретної математики  чи можна виключити перебір при розв`язку дискретних

задач?
Ця проблема має також велике пізнавальне значення. При пошуку ефективних точних методів розв`язку широкого класу дискретних задач потрібно враховувати можливість відсутності таких методів і, відповідно, вміти вчасно обмежувати своє прагнення, визнавши, що існують складновирішувані задачі.
Ця проблема залишається відкритою і зараз

виявлено значну кількість алгоритмічно невирішуваних проблем.
Для доведення нерозв`язності коректно

визначених математичних задач використовують апарат машин Тьюрінга і правило звідності.

яких потрібно знайти розв`язок. Але зі збільшенням розміру входу задачі

число варіантів швидко зростає і задача стає “складновирішуваною”, іншими словами  практично нерозв`язною.
Тому в скінченному випадку аналогом алгоритмічної нерозв`язності є перебір експоненційного числа варіантів, а аналогом розв`язності  існування алгоритму поліномінального типу.

математичної логіки.
Задача П1 зводиться до задачі П2, якщо метод

розв`язку задачі П2, можна трансформувати в метод розв`язку задачі П1.
Звідність називається поліномінальною, якщо подібне перетворення можна зробити за поліномінальний час.

клас NP всіх перебірних задач і
клас P перебірних задач,

розв`язок яких можна отримати за поліномінальний час на машині Тьюрінга.
Зрозуміло, що PNP. Головною проблемою теорії звідності є питання, чи співпадають класи P і NP.
Так математично формулюється проблема елімінації (уникнення) перебору.

тим, що в елемент пам'яті можна записати, взагалі кажучи, не

будь-яке число.
Він має обмежену місткість і тому існують обмеження на розрядність числа, що вміщується в ньому.

не одну, а декілька клітинок, що йдуть підряд, але це

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

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

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

трактує це слово так: “Евристика – мистецтво знаходження істини.”
В

древньогрецькій мові слово евристика (heuristic) має ті ж джерела що й слово еврика.
Прикладом ілюстрації цього методу в загальних рисах може служити класична задача про мавпу і банани.

займає знаходження варіантів розвязку цих задач для певних наборів даних

( а не для всіх даних) за поліноміальний час.

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

відповідає певним запитам людей, які пов’язані з бурхливим розвитком науки

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

Персії від автора книги з математики Abu Jafar Mohammed ibn

Musa al Khowarizmi.
Він визначав його як деякий спеціальний метод вирішення поставленої проблеми.
Поняття алгоритму відноситься до найбільш складних концепцій природознавства.
Воно пройшло складний історичний шлях розвитку, починаючи з інтуїтивного розуміння і стихійного застосування на перших кроках розвитку людського суспільства, та закінчуючи усвідомленням закономірностей природних явищ, застосуванням в сучасних ЕОМ.
Розвиток науки можна розглядати як неперервний процес уточнення алгоритмів і побудови відповідних моделей.

у собі накопичення фактів людиною, що засвоювала знання про природу

і стихійно формувала та закріплювала власні алгоритми поведінки.


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

теорія алгоритмів, яка уточнювала можливості теоретичного обчислення для практичного застосування

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

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

Алгоритм має скінчену

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

Форма задання алгоритму особливої ролі не відіграє, важливим є тільки

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

називалися також перші мови програмування високого рівня, наприклад, Алгол -

це просто скорочення ALGOrithmic Language - алгоритмічна мова.
Жодна мова програмування не може цілком замінити алгоритмічну мову, оскільки консервативна по своїй суті.
Стабільність - одна з необхідних компонент якості мови програмування.
Повинні бути гарантії, що всі програми, складені учора, в минулому році, десять років тому, не втратять значення ні сьогодні, ні завтра.

вимагає переробки системи програмування, знецінює напрацьоване програмне забезпечення.
У той

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

(В), козою (Кз) і капустою (Кп). Алгоритм її розв’язку можна

представити таким чином:

{ Л, В, Кз, Кп -> } - початковий стан
пливуть Л, Кз, Кп
{ В -> Л, Кз, Кп } - 1-ий крок
пливуть Л, Кз
{ Л, В, Кз -> Кп } - 2-ий крок
пливуть Л, В
{ Кз -> Л, В, Кп } - 3-ій крок
пливуть Л
{ Л, Кз -> В, Кп } - 4-ий крок
пливуть Л, Кз
{ -> Л, В, Кз, Кп } - кінцевий стан.

об'єкт, тому він вимагає абстрактного виконавця.
Визначення цього виконавця по

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

набору дій.
Команду на виконання окремої дії звичайно називають оператором

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

з пристрою управління і "робочого інструмента".
Кожний виконавець алгоритмів володіє

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

з більш "бідним" набором допустимих дій вимагають більш складних і

докладних алгоритмів.
Різні класи задач вимагають різних наборів допустимих дій, різних виконавців.

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

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

+ c = 0, a0, b0, c0.
0.Ввести значення a,b,c.
1.Знайти дискримінант

D=b ↑ 2- 4ac.
2.Якщо D<0, тоді
надрукувати повідомлення “рівняння не має дійсних коренів”.
В іншому випадку, якщо D=0, тоді надрукувати повідомлення “ рівняння має розвязок x1=x2= - …”
Інакше, (якщо D>0), тоді надрукувати повідомлення “ рівняння має два корені x1=… і x2= ….”
3.Кінець алгоритму.

за допомогою якоїсь мови програмування. Таке задання називають програмою.
program

EХ1_1;
var A,B,C,D: real;
begin
read(A,B,C);
D:=B*B-4*A*C;
if D=0 then
writeln(‘Рівняння має один розвязок x1=x2= ‘ , - B/(2*A))
else
if D>0 then
writeln (‘Рівняння має два корені x1 = ‘ , … ,
‘ i x2 = ‘, … )
else
writeln(‘Рівняння розв`язку в дійсних числах не має);
end.

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

і перетворюють їх на вихідні послідовності; тобто здійснюють інформаційні перетворення, в тому числі арифметичні операції. Такі перетворювачі будемо називати логічними схемами.
Логічні схеми можна розділити на два класи.
- Перший з них  комбінаційні схеми. Значення вихідних змінних комбінаційної схеми визначаються лише значенням вхідних змінних і не залежать від поточного стану схеми.
Інший клас логічних схем  схеми з памяттю.

від своїх вхідних змінних.
Булевою називається функція, і аргументи, і

результат якої можуть приймати одне з двох значень: 0 або 1.
Змінна, яка може дорівнювати або 0, або 1, називається булевою змінною.
На відміну від комбінаційної схеми скінченний автомат є перетворювачем, вихід якого залежить не тільки від вхідних і вихідних сигналів, але й від поточного стану автомата, причому кількість вхідних і вихідних змінних, кількість можливих значень цих змінних, а також кількість можливих станів автомата скінченна.
Поточний стан автомата зберігається в його пам’яті.

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

автоматів  скінченний автомат можна описати таким чином:
FА=, де
Q=(q1, q2, ... qn)  скінченна множина станів керування;
A=(a1, a2, ... am)  вхідний алфавіт;
b: Q x A  Q  функція переходів;
q0  початковий стан;
F  Q  множина заключних станів керування.

послідовності символів х і у, причому, в послідовності розпізнання кількість

одиниць повинна бути парною, а нулів  непарною.

Згідно з умовою задачі А буде складатися з символів х, у, #, де # буде позначати довільний символ, відмінний від х і у. Іншими словами, А=<х,у,#>.
Множину станів Q виберемо так: Q=, де
q0  початковий стан;
q1  стан помилки;
q2  стан, який визначає, що в послідовності кількість нулів непарна, а одиниць  парна (нуль будемо вважати числом парним);
q3  стан, який визначає, що в послідовності кількість нулів і одиниць непарна;
q4  стан, який визначає, що в послідовності кількість нулів і одиниць парна;
q5  стан, який визначає, що в послідовності кількість нулів парна, а одиниць  непарна.
Згідно з умовою задачі F=.

q3#q1 q4#q1 q5#q1
q0хq2 q0уq5
q1хq1

q1уq1
q2хq4 q2уq3
q3хq5 q3уq2
q4хq2 q4уq5
q5хq3 q5уq4

для вирішення проблеми безсмертя
Цю задачу можна сформулювати так. Нехай є

машина, що здатна замінювати свої деталі в міру того, як вони починають виходити з ладу.
Кожна деталь машини характеризується деяким середнім часом безвідмовної роботи.
Тоді розв’язок проблеми безсмертя в постановці Е.Ф.Мура полягає в створенні машини, що мала б більший середній час безвідмовної роботи, ніж довільна з її деталей.
Відповідь виглядає так: якщо деяка машина складається не більше, ніж з n деталей, і вірогідність безвідмовної роботи кожної деталі не перевищує деякої константи k>0, тоді вірогідність одночасної відмови всіх деталей в деякий момент часу, дорівнює в найгіршому випадку, 1-(1-k)^n. Тому прийде час, коли всі деталі відмовлять одночасно.

розбитої на квадратні комірки, та пристрою читання-запису.
Останній може читати

символ з комірки і записувати один символ в комірку, рухаючись вздовж стрічки в різні сторони.
Є також програма роботи  набір четвірок або п`ятірок, які визначають операції або обчислення машини як функцію від множини початкових символів на стрічці (входів).
В кінці роботи отримується вихідний набір, що є сукупністю символів, що залишились на стрічці після того, як були виконані всі операції, що задавались програмою.
Суттєвий факт, який вдалося довести за допомогою машини Тюрінга (МТ)  це те, що існує машина Тьюрінга, яка може при визначених вхідних значеннях обчислити довільну, обчислювальну за Тьюрінгом, функцію. Така машина називається універсальною машиною Тьюрінга.

є абстрактним обчислювачем, вона може бути виражена за допомогою різних

форм.
Наприклад зараз існують транслятори з мови програмування для класичної МТ.
Майже всі сучасні універсальні обчислювальні машини по своїй суті є МТ (ЦП-управляючий пристрій, машинна пам’ять-стрічка, ...).
Різницю лиш становить відмінність між скінченою пам’яттю обчислювача та потенційно нескінченною довжиною стрічки МТ. Тому без перебільшення можна сказати що сучасні комп’ютери реалізують основні функції, визначені Тьюрингом.
Тобто, основне значення МТ для сучасної теорії обчислювальних систем полягає в припущенні, що згідно тезису Чорча-Тьюринга, обчислювальна потужність МТ вища за довільну алгоритмічну систему.
Отже МТ представляє теоретичну межу можливості машин існуючих на практиці.