Понятие алгоритма

Тип работы:
Реферат
Предмет:
Информатика, программирование


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Слово «Алгоритм «походить від algorithmi — латинського написання імені аль- Хорезми, під що у середньовічний Європі знали найбільшого математика з Хорезма (місто в сучасному Узбекистані) Мухаммеда бен Мусу, жив 783- 850 рр. У книжці «Про індійському рахунку «він сформулював правила записи натуральних чисел з допомогою арабських цифр і правил дій з них стовпчиком. Надалі алгоритмом почали називати точне розпорядження, що б послідовність дій, що забезпечує отримання необхідного результату із вихідних даних. Алгоритм то, можливо призначений до виконання його людиною чи автоматичним пристроєм. Створення алгоритму, навіть найпростішого, — процес творчий. Він доступний виключно живих істот, а довгий час вважали, що тільки людині. Інша річ — реалізація вже наявного алгоритму. Її можна доручити суб'єкту чи об'єкту, який зобов’язаний вникати у суть справи, а можливо, і здатний його зрозуміти. Такий суб'єкт чи об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може служити пральна машина-автомат, яка точно виконує належні їй дії, навіть коли ви забули покласти у ній порошок. Людина також має здатність в ролі формального виконавця, та першої чергу формальними виконавцями стають різні автоматичні устрою, з комп’ютером зокрема. Кожен алгоритм створюється для цілком конкретної виконавця. Ті дії, що може здійснювати виконавець, називаються його його припустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен утримувати ті дії, які припустимі для даного виконавця. Об'єкти, з яких виконавець може виконувати дії, утворюють так звану середу виконавця. Для алгоритмів, можна зустріти у математиці, середовищем тієї чи іншої виконавця може бути числа різною природи — натуральні, справжні тощо., літери, літерні висловлювання, рівняння, тотожності тощо. Дане вище визначення алгоритму не вважається суворим — зрозуміло, що таке «точне розпорядження «чи «послідовність дій, забезпечує отримання необхідного результату «. Тому зазвичай формулюють кілька загальних властивостей алгоритмів, дозволяють відрізняти алгоритми від інших инструкций.

Такими властивостями є: Дискретність (переривчастість, окремість) — алгоритм має бути процес розв’язування завдання як послідовне виконання простих (чи раніше певних) кроків. Кожне дію, передбачене алгоритмом, виповнюється тільки тоді, як закінчилося виконання попереднього. Визначеність — кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цьому властивості виконання алгоритму носить механічного характеру і потребує додаткових вказівок чи даних про розв’язуваної завданню. Результативність (кінцівку) — алгоритм повинен спричинить рішенню завдання за кінцеве число кроків. Масовість — алгоритм виконання завдання розробляється загалом, тобто, повинен бути застосуємо для деякого класу завдань, різняться лише вихідними даними. У цьому вихідні дані можуть вибиратися з деякою області, що називається областю застосовності алгоритму. З цих властивостей іноді дається визначення алгоритму, наприклад: «Алгоритм — це послідовність математичних, логічних чи разом узятих операцій, відмінних детерменированностью, масовістю, спрямованістю і яка веде до вирішення всіх завдань даного класу за кінцеве число кроків.» Таке трактування поняття «алгоритм» є неповної і неточною. По-перше, не так пов’язувати алгоритм з рішенням будь-якої завдання. Алгоритм загалом не вирішувати жодного завдання. По-друге, поняття «масовість» належить немає алгоритмам як до таких, а до математичним методам загалом. Рішення поставлених практикою завдань математичними методами грунтується на абстрагуванні - ми виділяємо низку істотних ознак, притаманних деякого кола явищ, й будуємо виходячи з цих ознак математичну модель, відкидаючи несуттєві ознаки кожної конкретної явища. У цьому сенсі будь-яка математична модель має здатність масовості. Якщо рамках побудованої моделі ми вирішуємо завдання й рішення уявляємо як алгоритму, те решіння буде «масовим» завдяки природі математичних методів, а чи не завдяки «масовості» алгоритму. Роз’яснюючи поняття алгоритму, часто наводять приклади «побутових алгоритмів»: закип’ятити воду, відчинити двері ключем, перейти вулицю тощо. буд.: рецепти приготування будь-якого ліків чи кулінарні рецепти є алгоритмами. Але, щоб приготувати ліки за бабусиним рецептом, треба зазначити фармакологію, а приготування страви по кулінарному рецептом треба вміти варити. Тим більше що виконання алгоритму — це бездумне, автоматичне виконання розпоряджень, що у принципі не вимагає ніяких знань. Якби кулінарні рецепти виглядали алгоритми, то ми не було б такою спеціальності - кухар. Правила виконання арифметичних операцій чи геометричних побудов є алгоритми. У цьому залишається без відповіді запитання, що ж відрізняється поняття алгоритму від такого типу понять, як «метод», «спосіб», «правило». Можна навіть зустріти твердження, що «алгоритм», «спосіб», «правило» висловлюють один і той ж (тобто. є синонімами), така твердження, очевидно, суперечить «властивостями алгоритму». Саме вираз «властивості алгоритму» некоректно. Властивості мають об'єктивно існуючі реальності. Можна сказати, наприклад, про властивості будь-якого речовини. Алгоритм — штучна конструкція, що її споруджуємо задля досягнення своєї мети. Щоб алгоритм виконав свою призначення, його потрібно будувати за правилами. Тому треба говорити щодо властивості алгоритму, йдеться про правилах побудови алгоритму, або про вимогах, що висуваються до алгоритму. Перше правило — при побудові алгоритму насамперед потрібно поставити мно-жество об'єктів, з яким працювати алгоритм. Формалізоване (закодирован-ное) уявлення цих об'єктів називається даних. Алгоритм починає працювати з певним набором даних, які називаються вхідними, і цього своєї рабо-ты видає дані, які називаються вихідними. Отже, алгоритм пре-образует вхідні дані у вихідні. Це дозволяє відразу відокремити алгоритми від «методів» і «способів». Зараз ми не маємо формалізованих вхідних даних, ми можемо побудувати алгоритм. Друге правило — до роботи алгоритму потрібно пам’ять. Ще розміщуються вхідні дані, із якими алгоритм починає працювати, проміжні дані і вихідних даних, що є результатом роботи алгоритму. Пам’ять є дискретної, тобто. що з окремих осередків. Пойменована осередок пам’яті носить на-звание перемінної. Теоретично алгоритмів розміри пам’яті не обмежуються, т. е. счита-ется, що ми можемо надати алгоритму будь-який необхідний роботи обсяг пам’яті. У шкільній «теорії алгоритмів» ці дві правила не розглядаються. У той самий час практична роботу з алгоритмами (програмування) починається саме з цих правил. У мовами програмування розподіл пам’яті здійснюється декларативними операторами (операторами описи змінних). У мові Бейсик в повному обсязі перемінні описуються, зазвичай описуються лише масиви. Але однаково під час запуску програми транслятор мови аналізує все ідентифікатори з тексту програми розвитку й відводить пам’ять під відповідні перемінні. Третє правило — дискретність. Алгоритм будується із окремих кроків (дій, операцій, команд). Безліч кроків, у тому числі складено алгоритм, звісно. Четверте правило — детерменированность. Після кожного кроку необхідно вказувати, який крок виконується наступним, або давати команду зупинки. П’яте правило — відповідність (результативність). Алгоритм повинен завершувати роботу після кінцевого числа кроків. У цьому необхідно вказати, що вважати результатом роботи алгоритму. Отже, алгоритм — неопределяемое поняття теорії алгоритмів. Алгоритм кожному певному набору вхідних даних ставить за відповідність певний набір вихідних даних, т. е. обчислює (реалізує) функцію. Зблизька конкретних питань у теорії алгоритмів завжди мають на увазі якась конкретної моделі алгоритму. Будь-яка робота за комп’ютером — це є обробка інформації. Роботу комп’ютера можна схематично зобразити наступним образом:

[pic] «Інформація» зліва і «інформація» справа — це ж різні інформації. Комп’ютер сприймає інформацію ззовні й як результату своєї роботи видає нову інформацію. Інформація, з якою працює комп’ютер, називається «дані». Комп’ютер перетворює інформацію з певних правил. Ці правила (операції, команди) заздалегідь занесені на згадку про комп’ютера. Спільно цих правил перетворення інформації називаються алгоритмом. Дані, які у комп’ютер, називаються вхідними даними. Результат роботи комп’ютера — вихідних даних. Отже, алгоритм перетворює вхідні дані в выходные:

[pic] Нині можна порушити питання: і може людина обробляти інформацію? Звісно, може. Як приклад можна навести звичайний шкільний урок: вчитель запитує (вхідні дані), учень відповідає (вихідних даних). Найпростіший приклад: вчитель дає завдання — помножити 6 на 3 і результати написати на дошці. Тут числа 6 і трьох — вхідні дані, операція множення — алгоритм, результат множення — вихідні данные:

[pic] Висновок: рішення математичних завдань — окреме питання перетворення інформації. Комп’ютер (англійською мовою означає обчислювач, російською — ЕОМ, електронна обчислювальну машину) створили саме виконання математичних розрахунків. Розглянемо таку завдання. Довжина класу 7 метрів, ширина — 5 метрів, висота — 3 метри. У класі 25 учнів. Скільки кв. м площі й скільки куб. м повітря посідає одного учня ?

Рішення задачи:

1. Обчислити площа класу:

7 x 5 = 35

2. Обчислити обсяг класу:

35×3 = 105

3. Обчислити, скільки кв. метрів площі на одну учня:

35: 25 = 1,4

4. Обчислити, скільки куб. метрів повітря на одну учня:

105: 25 = 4,2

Відповідь: однієї учня доводиться 1,4 кв. метрів площі й 4,2 куб. метрів повітря. Якщо тепер прибрати обчислення і залишити тільки «дії», одержимо алгоритм — перелік операцій, які потрібно виконати, щоб вирішити це завдання. Виходить, що з рішенні будь-який математичної завдання ми складаємо алгоритм рішення. Але ми самі й виконували цей алгоритм, тобто доводили рішення до відповіді. І ось ми лише вміє писати, що потрібно зробити, але обчислення проводить думати. Вираховувати буде комп’ютер. Наш алгоритм являтиме набір вказівок (команд) комп’ютера. Коли ми обчислюємо якусь величину, ми записуємо результат на папері. Комп’ютер записує результат своєї роботи у пам’ять як перемінної. Тому кожна команда алгоритму повинна мати вказівку, у яку зміну записується результат. Алгоритм рішення нашої завдання буде такий вигляд:

1. Обчислити площа класу тут і записати в зміну S.

2. Обчислити обсяг класу тут і записати в зміну V.

3. Обчислити, скільки кв. метрів площі на одну учня та не записати в зміну S1.

4. Обчислити, скільки куб. метрів повітря на одну учня та не записати в зміну V1.

5. Вивести на екран значення змінних S1 і V1. Тепер залишається тільки перевести команди алгоритму з російської на мову, зрозумілий комп’ютера, й вийде програма. Програмування — це є переклад алгоритму з «людського» мови на «комп'ютерний» мову. Трактування роботи алгоритму як зміни вхідних даних у вихідні природним чином підводить нас до розгляду поняття «постановка завдання». А, щоб скласти алгоритм виконання завдання, необхідно з умови виділити ті величини, які вхідними даними і чітко сформулювати, які саме величини потрібно знайти. Інакше кажучи, умова завдання потрібно сформулювати як «Дано … Потрібна» — те й є постановка задачи.

Алгоритм стосовно обчислювальної машині - точне розпорядження, тобто. набір операцій та правил їх чергування, з якого, починаючи з деяких вихідних даних, можна вирішити будь-яке завдання фіксованого типу. Види алгоритмів як логіко-математичних коштів відбивають зазначені компоненти людської роботи і тенденції, не бажаючи алгоритми в залежність від мети, початкових умов завдання, шляхів її вирішення, визначення дій виконавця поділяються так:. Механічні алгоритми, чи інакше детермінований, жорсткі (наприклад алгоритм роботи машини, двигуна тощо.);. Гнучкі алгоритми, наприклад стохастические, тобто. імовірнісні і евристичні. Механічний алгоритм задає певні дії, позначаючи в єдиною і достовірної послідовності, забезпечуючи цим однозначний необхідний чи шуканий результат, якщо виконуються ті умови процесу, завдання, котрим розроблений алгоритм. Імовірнісний (стохастический) алгоритм дає програму виконання завдання кількома шляхами чи способами, приводящими до потенційному досягненню результату. Евристичний алгоритм (від грецького слова «еврика») — це таке алгоритм, у якому досягнення кінцевого результату програми дій однозначно не визначено, як і не позначена вся послідовність дій, не виявив усі дії виконавця. До эвристическим алгоритмам відносять, наприклад, інструкцією, і розпорядження. У цих алгоритми використовуються універсальні логічні процедури і знаходять способи прийняття рішень, засновані на аналогіях, ассоцияциях і колишньому досвіді рішення схожих завдань. Лінійний алгоритм — набір команд (вказівок), виконуваних послідовно у часу друг за іншому. Артеріальне алгоритм — алгоритм, у якому хоча одне умова, в результаті перевірки якого ЕОМ забезпечує перехід однією з цих двох можливих кроків. Циклічний алгоритм — алгоритм, який передбачає багаторазове повторення однієї й тієї самі діяння (одним і тієї ж операцій) над новими вихідними даними. До циклічним алгоритмам зводиться більшість методів обчислень, перебору варіантів. Цикл програми — послідовність команд (серія, тіло циклу), яка може виконуватися багаторазово (нових вихідних даних) до задоволення деякого умови. На малюнку продемонстровані в умовних позначеннях схеми основних конструкцій алгоритмів: а). лінійного алгоритму; б, в, г). разветвляющихся алгоритмів (б-ответвление, в-раздвоение, р- переключення); д, е, ж). циклічних алгоритмів (д, ж-проверка на початку циклу, е-проверка в кінці циклу). Допоміжний (підлеглий) алгоритм (процедура) — алгоритм, раніше розроблений і повністю використовуваний при алгоритмізації конкретного завдання. У окремих випадках за наявності однакових послідовностей вказівок (команд) щодо різноманітних даних із метою скорочення записи також виділяють допоміжний алгоритм. На всі етапи підготовки до алгоритмізації завдання широко використовується структурне уявлення алгоритму. Структурна (блок-, граф-) схема алгоритму — графічне зображення алгоритму як схеми пов’язаних між собою з допомогою стрілок (ліній переходу) блоків — графічних символів, кожен із яких відповідає одному кроку алгоритму. Усередині блоку дається опис відповідного дії. Графічне зображення алгоритму широко використовується перед програмуванням завдання внаслідок його наочності, т.к. зорове сприйняття зазвичай полегшує процес написання програми, її коригування при можливих помилках, осмысливание процесу обробки інформації. Можна зустріти навіть такий твердження: «Зовні алгоритм є схему — набір прямокутників та інших символів, всередині яких записується, що обчислюється, що вводять у автомобіль і що видається на печатку та інші засоби відображення інформації «. Тут форма уявлення алгоритму змішується із самою алгоритмом. Принцип програмування «згори донизу» вимагає, щоб блок-схема поетапно конкретизувалася й у блок «розписувався» до елементарних операцій. Але такий підхід можна здійснити під час вирішення нескладних завдань. За позитивного рішення серйозною завдання блок-схема «розповзеться» настільки, що її не вдасться охопити одним поглядом. Блок-схемы алгоритмів зручно використовуватиме пояснення роботи вже готового алгоритму, причому у ролі блоків беруться справді блоки алгоритму, робота яких немає потребує пояснень. Блок-схема алгоритму повинна для спрощення зображення алгоритму, а чи не для ускладнення. За позитивного рішення завдань за комп’ютером необхідно й не так вміння складати алгоритми, скільки знання методів вирішення завдань (як і загалом у математиці). Тому вивчати потрібно програмування як такий (і алгоритмізацію), а на методи вирішення математичних завдань за комп’ютером. Завдання слід класифікувати за типам даних, як це зазвичай робиться (завдання на масиви, на символьні перемінні тощо. буд.), а, по поділу «Потрібна». У інформатики процес розв’язування завдання розподіляється між двома суб'єктами: програмістом і комп’ютером. Програміст становить алгоритм (програму), комп’ютер його виконує. У традиційної математиці такого поділу немає, завдання вирішує одна людина, що становить алгоритм виконання завдання і сам виконує його. Сутність алгоритмізації в тому, що ухвалено рішення завдання представляється як набору елементарних операцій, суть у тому, що виконання завдання розбивається на два етапу: творчий (програмування) і не творчий (виконання програми). І виконують цих етапів різні суб'єкти — програміст і виконавець У підручниках з інформатики зазвичай пишуть, що виконавцем алгоритму може бути прибутковим і людина. Насправді алгоритми для таких людей хто б становить (не забуваймо, що ні всякий набір дискретних операцій є алгоритмом). Людина перетворюється на принципі неспроможна діяти за алгоритму. Виконання алгоритму — це автоматичне, бездумне виконання операцій. Людина завжди діє осмислено. А, щоб людина могла виконувати якийсь набір операцій, він повинен пояснити, як це робиться. Будь-яку роботу людина зможе виконувати тільки тоді ми, що він розуміє, як виконується. У цьому — «пояснення й розуміння» — й полягає різницю між поняттями «алгоритм» і «спосіб», «метод», «правило». Правила виконання арифметичних операцій — це і є правила (чи засоби), а чи не алгоритми. Звісно, цих правил можна викласти як алгоритмів, та це від рівня цього нічого очікувати. А, щоб молода людина зміг вважати за правилами арифметики, його треба навчити. Але є процес навчання, отже, ми маємо справа ні з алгоритмом, і з методом. Під час упорядкування алгоритму програміст нічого не пояснює, а виконавець не намагається нічого зрозуміти. Алгоритм розміщається у пам’яті комп’ютера, який дістає команди за однією і виконує їх. Людина рухається за іншому. Аби розв’язати завдання, людині тримати в пам’яті метод виконання завдання загалом, а втілює його кожен по- своєму. Дуже яскраво ця особливість людської психології - неалгоритмичность мислення — проявилася у методичесом посібнику А. Р. Гейна і У. Ф. Шолоховича. У посібнику викладаються вирішення завдань з його відомого підручника. Рішення завдань мають бути представлені як алгоритмів. Проте автори посібники розуміють, що й просто написати алгоритм виконання завдання, то дати раду самому рішенні буде складно. Тому спочатку наводять «нечітке виклад алгоритму» (т. е. пояснюють вирішення завдання), та був пишуть сам алгоритм.

Л І Т Є Р, А Т У Р, А 1. Нестеренко А. У. ЕОМ і професія програміста. М., Просвітництво, 1990. 2. Брудно А. Л., Каплан Л. І. Московські олімпіади з програмування. М., Наука, 1990. 3. Кузнєцов Про. П., Адельсон-Вельский Р. М. Дискретна математика для інженера. М., Энергоатомиздат, 1988. 4. Гейн О. Г. та інших. Основи інформатики, і обчислювальної техніки. М., Просвітництво, 1994. 5. Інформатика. Щотижневе додаток до газети «Перше вересня». 1998, № 1. 6. Радченко М. П. Відповіді стосовно питань випускних іспитів. — Инфоматика і освіту, 1997, № 4. 7. Касаткін В.М. Інформація, алгоритми, ЕОМ. М., Просвітництво, 1991. 8. Каныгин Ю. М., Зотов Б. І. Що таке інформатика? М., Дитяча література, 1989. 9. Гейн А. Р., Шолохович В. Ф. Викладання курсу «Основи інформатики, і обчислювальної техніки» у неповній середній школі. Керівництво для вчителя. Єкатеринбург, 1992. 10. Візників В.А. Інформатика з поняттями і термінах. 11. Газета «Інформатика», № 35, 1997 р. 12. Л. З. Шауцуков Основи інформатики у питаннях і ответах.

ПоказатьСвернуть
Заполнить форму текущей работой