69126

Поняття алгоритму й основні алгоритмічні структури. Властивості та способи опису алгоритму. Алгоритмічна структура розгалуження і перетворення

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-30

56.5 KB

6 чел.

Лекіця 3. Тема: Поняття алгоритму й основні алгоритмічні структури.

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

                          Алгоритмічна структура розгалуження  і  перетворення.

План:

1. Поняття алгоритму й основні алгоритмічні структури

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

3. Алгоритмічна структура розгалуження

4. Алгоритмічна структура повторення

1. Поняття алгоритму й основні алгоритмічні структури

Одним з базових понять інформатики є поняття алгоритму. Алгоритм вказує, які операції, пов'язані з обробкою даних, і в якій послідовності треба виконати, щоб отримати розв'язок задачі. Алгоритм розрахований на певного виконавця, з погляду котрого вказівки мають бути елементарними, тобто такими, що можуть бути виконані безпосередньо, без подальшого тлумачення. Слово «алгоритм» походить від назви латинського перекладу трактату арабського математика IX століття Аль-Хорезмі («Трактат Аль-Хорезмі про арифметичне мистецтво індусів»).

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

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

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

Результативність — за скінченну кількість кроків алгоритм має приводити до розв'язання задачі або зупинятися через неможливість її розв'язати.

Дискретність - кроки обчислювального процесу мають бути відокремлені один від одного.

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

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

Є декілька способів опису алгоритму: словесний опис послідовності дій, алгоритмічна мова, аналітичний опис у вигляді набору формул, графічний — у вигляді блок-схеми тощо. Формалізована система правил текстуального опису алгоритмів є одним із різновидів мов програмування. А мови, призначені для запису алгоритмічних структур, називаються мовами структурного програмування.

Однією з наочних форм зображення алгоритму є блок-схема. Вона містить блоки, позначені геометричними фігурами. Усередині блоків записують елементарні дії. Блоки з'єднуються стрілками — так задається послідовність дій. Стрілки не є обов'язковими, якщо їхній напрямок відповідає просуванню «униз» і «праворуч». Кожній геометричній фігурі відповідає певний клас алгоритмічних інструкцій.

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

Ромбами позначається перевірка умови, залежно від результату якої визначається напрямок подальших обчислень. Тому блоки, що позначаються ромбами, називаються умовними. Оскільки результатом перевірки умови, записаної в умовному блоці, може бути значення «так» або «ні», тобто «істина» чи «хибність», блок має два виходи.

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

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

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

3. Алгоритмічна структура розгалуження

Алгоритмічна структура, що дозволяє виконавцеві алгоритму вибрати сценарій подальших дій залежно від істинності певного умовного твердження, називається розгалуженням. На блок-схемі (рис. 1.10) структури розгалуження позначаються ромбами. Дві стрілки, які відгалужуються від ромба, позначені словами «Так» і «Ні». Якщо записане всередині ромба умовне твердження є істинним, виконуються дії, на які вказує стрілка, позначена словом «Так». Якщо це твердження є хибним, виконуються дії, на які вказує стрілка, позначена словом «Ні».

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

4. Алгоритмічна структура повторення

Розглянемо задачу знаходження найбільшого спільного дільника двох натуральних чисел, застосувавши для її розв'язання алгоритм Евкліда. Позначимо найбільший спільний дільник чисел а і b через НСД(а, Ь), а остачу від ділення а на b - через a mod b. Алгоритм Евкліда грунтується на тому факті, що НСД(а, Ь) = = НСД(Ь, a mod b), якщо b * 0, і НСД(а, Ь) = а, якщо b = 0. Наприклад: НСД(12, 5) = НСД(5,12 mod 5) = НСД(5, 2)=НСД(2, 5 mod 2) = НСД(2,1) = = НСД(1, 2 mod 1) = НСД(1, 0) = 1.

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

Твердження, істинність якого перевіряється під час виконання циклічної структури, на блок-схемі записується всередині ромба (як і у випадку структури розгалуження). Особливістю зображення циклічної структури на блок-схемі є те, що одна зі стрілок повинна «повертатися назад», тобто має утворюватися замкнений «цикл» із блоків та стрілок. Такий цикл має містити умовний блок, в якому записана умова продовження повторення. Одна зі стрілок, що відгалужуються від цього блоку, повинна брати участь у циклі, а інша — вказувати на блок поза циклом.

Висновки

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

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

- Вісім послідовних бітів утворюють байт. Байт є базовою одиницею виміру
довжини інформаційного повідомлення й обсягу пам'яті.

- Оперативна пам'ять може розглядатись як послідовність байтів. Кожен байт ає свій номер — адресу.

- 3 погляду процесора програма - це розташована в оперативній пам'яті послідовність команд. Команди виконуються арифметико-логічним пристроєм
процесора.

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

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

- Програма-інтерпретатор виконує визначені програмою дії, не транслюючи програми у машинний код.

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

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

Розробка програмного забезпечення — це складний ітеративний процес, що, як правило, складається з таких етапів: постановка задачі, аналіз задачі та побудова її моделі, вибір або розробка алгоритму розв'язання задачі, кодування,
налагодження та тестування, дослідно-виробнича експлуатація і супровід програмного забезпечення.

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

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

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

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

Контрольні запитання та завдання

1. Поняття алгоритму й основні алгоритмічні структури

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

3. Алгоритмічна структура розгалуження

4. Алгоритмічна структура повторення


 

А также другие работы, которые могут Вас заинтересовать

13908. ВОСПРИЯТИЕ НА СЛУХ И ТРЕНИРОВКА ПАМЯТИ 67.5 KB
  УРОК 4 ВОСПРИЯТИЕ НА СЛУХ И ТРЕНИРОВКА ПАМЯТИ 1. Запишите на слух ряд чисел и повторите их по записи: 2. Повторите следующие имена собственные выражающие индивидуальные понятия в любом порядке: 3. Повторите в любом порядке существительные выражающие абстрактн
13909. О.П. Довженко «Україна в огні», її справедлива критика «культу особи». Особливості сюжету й композиції. Проблеми «людина і війна», «історична пам’ять народу». Образ Запорожця як символ нескореності свого народу 49.5 KB
  Урок української літератури 11 клас ТЕМА: О.П. Довженко Україна в огні її справедлива критика культу особи. Особливості сюжету й композиції. Проблеми людина і війна історична память народу. Образ Запорожця як символ нескореності свого народу. МЕТА: ознай
13910. Урок. У чому виявляється істинний патріотизм? (За поезією Тараса Шевченка «Минають дні, минають ночі) 30.99 KB
  Тема. У чому виявляється істинний патріотизм За поезією Тараса Шевченка Минають дні минають ночі Мета: допомогти учням поглибити знання про творчу діяльність великого митця зосередити увагу на ідейнохудожньому аналізі поезії Минають дні минають ночі засвої
13911. Зарождение демократии в Афинах 57 KB
  Конспект урока по истории Древнего мира в 6м классе Тема: Зарождение демократии в Афинах. Цель: дать представление о зарождении демократии в Афинах реконструировать социальный конфликт между демосом и аристократией в Афинах в VI в до н.э. ознакомить с рефо...
13912. Знаки препинания в сложных предложениях с разными видами связи 15.22 KB
  Урок русского языка в 9Б9В классах Тема урока: Знаки препинания в сложных предложениях с разными видами связи. Цель урока: углубить знания учащихся о знаниях препинания в сложных предложениях. Задача: формировать навыки и умения пунктуационной и орфографической гра...
13913. Обработка больших массивов числовых данных 1.62 MB
  Тема урока: Обработка больших массивов числовых данных Цель урока: Научиться использовать электронные таблицы для автоматизации расчетов Задачи урока: Образовательные: научиться обрабатывать числовые данные при помощи математических и статистических функци...
13914. Кіномистецька спадщина Олександра Довженка. Кіноповість як новий жанр у літературі, його характерні ознаки. Проблеми народу та війни, історичної пам’яті в кіноповісті «Україна в огні» 66 KB
  Урок літератури 11 клас Тема. Кіномистецька спадщина Олександра Довженка. Кіноповість як новий жанр у літературі його характерні ознаки. Проблеми народу та війни історичної памяті в кіноповісті Україна в огні. Мета: ознайомити учнів з творчим д
13915. Урок. Я НАРОДИВСЯ І ЖИВ ДЛЯ ДОБРА І ЛЮБОВІ (життєвий і творчий шлях Олександра Довженка) 115.5 KB
  Урок української літератури 11 клас Я НАРОДИВСЯ І ЖИВ ДЛЯ ДОБРА І ЛЮБОВІ життєвий і творчий шлях Олександра Довженка Мета уроку: поглибити знання учнів про життєвий і творчий шлях Довженка словесно намалювати живий образ письменника славного сина нар
13916. Анимация объектов 1.47 MB
  Урок 13. Анимация объектов Под анимацией сцены в max понимается автоматизированный процесс визуализации серии изображений называемых также кадрами frames каждое из которых фиксирует некоторые изменения состояния этой сцены. Эти изменения могут касаться положений объект