Властивості алгоритму.

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

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

Дискретність. Процес, який визначається алгоритмом, повинен мати дискретний (перервний) характер, тобто являти собою послідовність окремих завершених в собі кроків. У зв’язку з цим повідомленням проте, яку саме операцію треба виконати на кожному кроці, подають у вигляді речень наказової форми доконаного виду (“Виконати ...”, а не “Виконувати ...”). такі повідомлення називають вказівками (або командами). Кожна операція алгоритму повинна виконуватися за скінчений час, а виконання наступної операції повинно починатися після завершення попередньої.

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

Формальність. Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати поставлене завдання. Ця властивість має особливе значення для автоматизації виконання алгоритму.

Форми запису алгоритмів

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

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

Запис алгоритмів за допомогою блок-схем. Цей метод був запропонований в інформатиці для наочності представлення алгоритму за допомогою набору спеціальних блоків. Основні:Блок початку або кінця алгоритму – еліпс, блок введення або виведення даних – паралелограм, командний блок – прямокутник, блок розгалуження або умовний блок – ромб.

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

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

Типи алгоритмів:

-Простими є такі команди: виконати, встати, іти, вміти тощо. Якщо алгоритм складається лише з послідовності простих команд то його називають простим, або лінійним. Приклад: "Алгоритм Ранок":Встати о 6.30 годині. Виконати гімн. вправи. Умитися. Поснідати. Вийти з дому о 7.30 годин

Якщо в алгоритмі, окрім простих команд, є команда, яка містить умову, то такий алгоритм називається розгалуженим. Умови в інформатиці називаються логічним виразом. Приклад: "Алгоритм Вечір": Повернутися з коледжу додому після занять.Пообідати.Якщо погода хороша, то попрацювати в саду, інакше піти в бібліотеку, взяти книжку, повернутися додому.Зробити домашнє завдання.Повечеряти. Якщо є цікава телепередача, то подивитися телевізор, інакше почитати книжку. Лягти спати.

Циклічні алгоритми. Циклом називають процес повторення дій. Циклічні алгоритми забезпечують повторне виконання деяких команд скінчену кількість разів. Приклад: Алгоритм коледж Іти на першу пару.Доки не закінчилися заняття іти на наступну пару.Іти додому.

Універсальні алгоритми – це такі які містять в собі вище перечисленні такі алгоритми.

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

Алгоритми, що складаються для розв'язування окремих підзадач основної задачі, називаються допоміжними. Вони створюються при поділі складної задачі на прості або при необхідності багаторазового використання одного ж того набору дій в одному або різних алгоритмах. Допоміжний алгоритм повинен мати тільки один вхід та один вихід, причому того, хто користується ним, зовсім не цікавить, як реалізований цей алгоритм. Головне, щоб всі команди, що входять до складу допоміжного алгоритму входили до системи команд обраного виконавця. Таким чином, можна вважати допоміжний алгоритм своєрідним "чорним ящиком", на вхід якого подаються деякі вхідні дані, а на виході ми отримуємо очікуваний результат.

Етапи розв’язування.

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

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

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

Запис і трансляція програми Якщо алгоритм складено, з погляду на розв’язок задачі на ЕОМ користувачу залишається більш технічна, аніж творча робота. Враховуючи характер задачі необхідно вибрати певну мову програмування для запису програми та записати її текст. Зрозуміло, що користувач повинен володіти потрібним обсягом знань з використання команд (операторів) обраної мови.

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

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

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

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

Аналіз алгоритмів.

Доведення коректності. Часткова коректність — програма дає коректний результат для тих випадків, коли вона завершується.

Повна коректність — програма завершує роботу та видає коректний результат для всіх елементів з діапазону вхідних даних.

Під час доведення коректності порівнюють текст програми зі специфікацією бажаного співвідношення вхідних-вихідних даних.

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

Час, який витрачає алгоритм як функція від розміру задачі n, називають часовою складністю цього алгоритму T(n).

Машина з довільним доступом до пам’яті.Аналіз алгоритму полягає в тому, щоб передбачити потрібні для його виконання ресурси. Іноді оцінюється потреба в таких ресурсах, як пам’ ять, пропускна здатність мережі або необхідне апаратне забезпечення, але найчастіше визначається час обчислення. Шляхом аналізу деяких алгоритмів, призначених для розв’ язку однієї та тієї самої задачі, можна легко обрати найбільш ефективний з них. В процесі такого аналізу може також виявитись, що декілька алгоритмів приблизно рівноцінні, а всі інші варто відкинути.З урахуванням того, що алгоритми реалізуються у вигляді комп’ ютерних програм, в більшості випадків в якості технології аналізу алгоритмів буде використовуватись модель узагальненої однопроцесорної машини з довільним доступом до пам’ яті (Random-Access Machine – RAM). В цій моделі команди процесора виконуються послідовно; операції, які виконуються одночасно, відсутні.У цю модель входять ті команди, які зазвичай можна знайти в реальних комп’ ютерах: арифметичні (додавання, віднімання, добуток, ділення, обчислення остачі від ділення, наближення дійсного числа найближчим більшим чи найближчим меншим цілим числом), операції переміщення даних (завантаження значення в пам’ ять, копіювання) та керуючі операції (умовне та безумовне галуження, виклик підпрограми і повернення з неї). Для виконання кожної такої інструкції потрібно певний фіксований проміжок часу. Кеш та віртуальна пам’ ять відсутні у RAM. Моделі, які включають в себе таку ієрархію, набагато складніше моделі RAM, тому вони можуть ускладнити роботу. Аналіз навіть простого алгоритму в моделі RAM може вимагати значних зусиль. В число необхідних математичних інструментів може увійти комбінаторика, теорія ймовірностей, алгебраїчні перетворення та здатність ідентифікувати найбільш важливі доданки в формулі. Оскільки поведінка алгоритму може відрізнятись для різних наборів вхідних значень, буде потрібна методика обліку, яка описує поведінку алгоритмів за допомогою простих та зрозумілих формул.

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

38. Інформатика як наука і як шкільний предмет у середній школі. Мета викладання інформатики в середній школі. Вплив інформатизації суспільства на його наyково-технічний та соціально-економічний розвиток. Про концепцію інформатизації освіти в Україні.

<== попередня сторінка	\|	наступна сторінка ==>
Підручник «Інформатика. 5 клас»(авт.Морзе Н.В., Барна О.В., Вембер В.П., Кузьмінська О.Г., Саражинська Н.А.)	\|	ІНФОРМАТИКА ЯК НАУКА І ЯК НАВЧАЛЬНИЙ ПРЕДМЕТ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.026 сек.