Західно-Казахський Аграрно-Технічний університет Жангіра-хана
Кафедра: В«ІнформатикиВ»
Реферат
На тему
Основи алгоритмізації
Підготував: Іванов П.
Перевірив: Кухта В.С.
Уральськ 2010
План
1. Поняття алгоритму і його властивості
2. Способи опису алгоритмів
3. Основні структурні алгоритмічні конструкції
4. Список літератури
Поняття алгоритму і його властивості
Алгоритм - описана на деякій мові точна кінцева система правил, що визначає зміст і порядок дій над деякими об'єктами, суворе виконання яких дає рішення поставленої задачі. Поняття алгоритму, що є фундаментальним в математиці і інформатиці, виникло задовго до появи засобів обчислювальної техніки. Слово В«алгоритмВ» з'явилося в середні століття, коли європейці познайомилися зі способами виконання арифметичних дій у десятковій системі числення; описаними узбецьким математиком Муххамедом бен Аль-Хорезмі (В«аль-ХорезміВ» - людина з міста Хорезмі; в Нині місто Хіва в Хорезмской області Узбекистану). Слово алгоритм - є результат європейського вимови слів аль-Хорезмі. Спочатку під алгоритмом розуміли спосіб виконання арифметичних дій над десятковими числами. Надалі це поняття стали використовувати для позначення будь послідовності дій, що приводить до вирішення поставленої задачі.
Будь алгоритм існує не сам по собі, а призначений для певного виконавця (людини, робота, комп'ютера, мови програмування і т.д.). Властивістю, що характеризує будь-якого виконавця, є те, що він вміє виконувати деякі команди. Сукупність команд, які даний виконавець уміє виконувати, називається системою команд виконавця. Алгоритм описується в командах виконавця, який буде його реалізовувати. Об'єкти, над якими виконавець може вчиняти дії, утворюють так звану середу виконавця. Вихідні дані і результати будь-якого алгоритму завжди належать середовищі того виконавця, для якого призначений алгоритм.
Значення слова В«алгоритмВ» дуже схоже зі значеннями слів В«рецептВ», В«методВ», В«процесВ». Однак, на відміну від рецепту або процесу, алгоритм характеризується наступними властивостями: дискретністю, масовістю, визначеністю, результативністю, формальністю.
Дискретність (розривність - протилежно безперервності) - це властивість алгоритму, що характеризує його структуру: кожен алгоритм складається з окремих закінчених дій, говорять: В«Ділиться на крокиВ».
Масовість - застосовність алгоритму до всіх завдань розглянутого типу, при будь-яких вихідних даних. Наприклад, алгоритм розв'язання квадратного рівняння в області дійсних чисел має містити всі можливі наслідки рішення, тобто, розглянувши значення дискримінанта, алгоритм знаходить або два різних кореня рівняння, або два рівних, або робить висновок про те, що дійсних коренів немає.
Визначеність (детермінованість, точність) - властивість алгоритму, яке вказує на те, що кожен крок алгоритму має бути строго визначений і не допускати різних тлумачень; також строго має бути визначений порядок виконання окремих кроків. Пам'ятаєте казку про Івана-царевича? В«Йшов Іван-царевич по дорозі, дійшов до розвилки. Бачить великий камінь, на ньому напис: В«Прямо підеш - Голову втратиш, направо підеш - дружину знайдеш, наліво підеш - розбагатієш В». Варто Іван і думає, що далі робити В». Таких інструкцій алгоритм містити не може.
Результативність - властивість, що складається в тому, що будь-який алгоритм повинен завершуватися за кінцеве (може бути дуже велика) число кроків. Питання про розгляді нескінченних алгоритмів залишається за рамками теорії алгоритмів.
Формальність - це властивість вказує на те, що будь-який виконавець, здатний сприймати і виконувати інструкції алгоритму, діє формально, тобто відволікається від змісту поставленої задачі і лише строго виконує інструкції. Міркувати В«що, як і чому?В» Повинен розробник алгоритму, а виконавець формально (не думаючи) почергово виконує запропоновані команди і отримує необхідний результат.
Способи опису алгоритмів
Розглянемо наступні способи опису алгоритму: словесний опис, псевдокод, блок-схема, програма.
Словесний опис являє структуру алгоритму на природному мовою. Наприклад, будь-який прилад побутової техніки (праска, електропила, дриль і т.п.) має інструкцію по експлуатації, тобто словесне опису алгоритму, в Відповідно до якого даний прилад повинен використовуватися.
Ніяких правил складання словесного опису не існує. Запис алгоритму здійснюється у довільній формі на природному, наприклад, російською мовою. Цей спосіб опису не має широкого поширення, так як суворо не формалізуємо (під В«формальнимВ» розуміється те, що опис абсолютно повне і враховує всі можливі ситуації, які можуть виникнути в ході вирішення); допускає неоднозначність тлумачення при описі деяких дій; страждає многословность.
Псевдокод - опис структури алгоритму на природному, частково формалізованій мові, що дозволяє виявити основні етапи виконання завдання, перед точної його записом на мові програмування. У псевдокоді використовуються деякі формальні конструкції і загальноприйнята математична символіка.
Строгих синтаксичних правил для записи псевдокоду не існує. Це полегшує запис алгоритму при проектуванні і дозволяє описати алгоритм, використовуючи будь-який набір команд. Однак у псевдокоді зазвичай використовуються деякі конструкції, властиві формальним мовам, що полегшує перехід від псевдокоду до запису алгоритму на мові програмування. Єдиного або формального визначення псевдокоду НЕ існує, тому можливі різні псевдокоду, що відрізняються набором використовуваних слів і конструкцій.
Блок-схема - опис структури алгоритму за допомогою геометричних фігур з лініями-зв'язками, що показують порядок виконання окремих інструкцій. Цей спосіб має ряд переваг. Завдяки наочності, він забезпечує В«ЧитаністьВ» алгоритму і явно відображає порядок виконання окремих команд. В блок-схемі кожної формальної конструкції відповідає певна геометрична фігура пли пов'язана лініями сукупність фігур.
Розглянемо деякі основні конструкції, що використовуються для побудови блок-схем алгоритмів програм, регламентовані ГОСТ 19.701-90.
Блок, який характеризує початок/кінець алгоритму (для підпрограм - виклик/повернення)
Блок - процес, призначений для описи окремих дій
Блок - приречення процес, призначений для звернення до допоміжним алгоритмам (Підпрограм)
Блок - введення/виводу з невизначеного носія або опису вихідних даних
Блок - рішення (перевірка умови або умовний блок)
Блок - кордону циклу, що описує циклічні процеси типу: В«цикл з передумовоюВ», В«цикл з постусловіем В»
Сполучні блоки
Описи алгоритму в словесній формі, на псевдокоді або у вигляді блок-схеми допускають деякий свавілля при зображенні команд. Разом з тим вона настільки достатня, що дозволяє людині зрозуміти суть справи і виконати алгоритм. На практиці виконавцями алгоритмів виступають комп'ютери. Тому алгоритм, призначений для виконання на комп'ютері, має бути записаний на В«зрозумілоюВ» йому мовою, такою формалізований мову називають мовою програмування.
Програма - опис структури алгоритму мовою алгоритмічного програмування.
Основні структурні алгоритмічні конструкції
Елементарні кроки алгоритму можна об'єднати в наступні алгоритмічні конструкції: лінійні (Послідовні), розгалужуються, циклічні з передумовою та циклічні з постусловіем. Будь алгоритм можна скласти, використовуючи ці чотири алгоритмічні конструкції.
Лінійної називають алгоритмічну конструкцію, реалізовану у вигляді послідовності дій (кроків), в якій кожна дія (крок) алгоритму виконується рівно один раз, причому після кожного i-го дії (кроку) виконується (i +1)-е дію (крок), ...
