Тема 4. Особливості вивчення основ алгоритмізації та програмування

Практична робота №4

Тема 4. Особливості вивчення основ алгоритмізації та програмування

Пендзей Л.Р

Основні поняття алгоритміки

     Алгоритміка (англ. agorithm design) — дисципліна, що вивчає алгоритми, та їх застосування до розв'язування задач.

Рішення задач за допомогою ПК включає в себе наступні основні етапи, частина з яких здійснюються до використання комп'ютера:

Постановка завдання. Етап включає в себе: збір інформації про завдання; визначення кінцевих цілей рішення задачі; визначення форми видачі результатів; опис даних.

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

Розробка алгоритму. Етап полягає у виборі форми запису алгоритму і в подальшому процесі розробки алгоритму.

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

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

Аналіз результатів розв'язання задачі. На цьому етапі здійснюється аналіз програми при реальних вихідних даних. У результаті аналізу результатів розрахунку можливе уточнення математичної моделі і повторення етапів 2-5.

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

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

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

детермінованість - однозначність отримання результату при одних і тих же вихідних даних;

результативність - обов'язковість отримання шуканого ре результату за кінцеве число кроків;

масовість - можливість отримання результату при різних вихідних даних розглянутого класу задач;

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

Існують різні способи опису алгоритмів. Наприклад такі найбільш поширені наступні форми подання алгоритмів:

словесна - послідовність дій, описана природною мовою;

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

 псевдокод - опис алгоритму на умовно алгоритмічній мові, що включає в себе як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення;

 програмна - текст програми на мові програмування.

В 3 класі авт. Г. В. Ломаковська, Г. О. Проценко, Ф. М. Рівкінд , Й. Я. Ривкінд. Розділ5. ст. підручника 109-138. К-сть год. 5.

В 4 класі по підручнику авт. Г. В. Ломаковська, Г. О. Проценко, Ф. М. Рівкінд , Й. Я. Ривкінд. Розділ 5. Ст.93-130. К-сть год 8.

В 6 класі по підручнику Н.В.Морзе, О.В.Барна, В.П.Вембер, О.Г.Кузьмінська, Н.А.Саражинська розділ 1. Ст..6-50.  К-сть год 7.

В 7 класі по підручнику О.П.Казанцева, І.В.Стеценко, Фурик Л.В. Розділ 3. Ст.61-77. К-сть год 10.

Поняття математичної логіки

Математична логіка по суті є формальною логікою, що використовує математичні методи. Формальна логіка вивчає акти мислення (поняття, судження, умовиводи, доведення) з точки зору їх форми, логічної структури, абстрагуючись від конкретного змісту. Творцем формальної логіки є Аристотель, а першу завершену систему математичної логіки на базі строгої логіко-математичної мови - алгебру логіки, - запропонував Дж. Буль (1815-1864).

Логіко-математичні мови і теорія їх смислу розвинуті в роботах Г. Фреге (1848-1925), який ввів поняття предикату і кванторів. Це надало можливість застосувати логіко-математичні мови до питань основ математики. Виклад цілих розділів математики на мові математичної логіки та аксіоматизація арифметики зроблені Дж. Пеано (1858-1932). Грандіозна спроба Г. Фреге та Б. Рассела (1872-1970) зведення всієї математики до логіки не досягла основної мети, але привела до створення багатого логічного апарату, без якого оформлення математичної логіки як повноцінного розділу математики було б неможливе.

На межі 19-20 ст. були відкриті парадокси, зв'язані з основними поняттями теорії множин (найвідомішими є парадокси Г. Кантора та Б. Рассела). Для виходу з кризи Л. Брауер (1881-1966) висунув інтуїціоністську програму, в якій запропонував відмовитися від актуальної нескінченності та логічного закону виключеного третього, вважаючи допустимими в математиці тільки конструктивні доведення. Інший шлях запропонував Д. Гільберт (1862-1943), який в 20-х роках 20 ст. виступив з програмою обґрунтування математики на базі математичної логіки.

Програма Гільберта передбачала побудову формально-аксіоматичних моделей (формальних систем) основних розділів математики та подальше доведення їх несуперечливості надійними фінітними засобами. Несуперечливість означає неможливість одночасного виведення деякого твердження та його заперечення. Таким чином, математична теорія, несуперечливість якої хочемо довести, стає предметом вивчення певної математичної науки, яку Д. Гільберт назвав метаматематикою, або теорією доведень. Саме з розробки Д. Гільбертом та його учнями теорії доведень на базі розвинутої в роботах Г. Фреге та Б. Рассела логічної мови починається становлення математичної логіки як самостійної математичної дисципліни.

Булеві функції та предикати

Визначення. Булевой функцією f (X1, X2, …, Xn) називається довільна n – місцева функція, аргументи і значення якої належать безлічі {0, 1}.

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

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

X1	X2	· ØX1	X1&X2	X1ÚX2	X1ÞX2	X1ÛX2
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

 

Поняття предикатів

Визначення. Предикатом P (x1, x2, …, xn) називається функція, перемінні якої приймають значення з деякої безлічі М, а сама функція приймає два значення: И (істина) і Х (неправда), тобто

 

Предикат від п аргументів називається п – місцевим предикатом. Висловлення вважаються нуль – місцевими предикатами.

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

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

Практична робота №4

Тема 4. Особливості вивчення основ алгоритмізації та програмування

Пендзей Л.Р

1234Следующая ⇒

Поделиться: