69126

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

Лекция

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

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

Украинкский

2014-09-30

56.5 KB

7 чел.

Лекіця 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. Алгоритмічна структура повторення


 

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

34696. Фирма и индивидуальные предприниматели. Организационно-правовые формы фирмы 20.46 KB
  Чем отличаются друг от друга хозяйственные товарищества и общества Вопервых товарищество это группа лиц которые принимают участие в работе фирмы а общество объединение капиталов его участники могут в фирме и не работать. К хозяйственным обществам относят общество с ограниченной ответственностью и общество с дополнительной ответственностью. Общество с ограниченной ответственностью имеет уставной капитал который разделен на доли. Общество с дополнительной ответственностью отличается от общества с ограниченной ответственностью...
34697. Общие, средние и предельные издержки фирмы 17.64 KB
  Общие средние и предельные издержки фирмы. Экономисты различают общие средние и предельные издержки. Общие издержки ТC это издержки всего выпуска продукта фирмы. Общие издержки делятся на постоянные и переменные издержки.
34698. Типы экономических систем. Традиционная экономическая система 19.1 KB
  Традиционная экономическая система. Экономическая наука выделяет четыре основных типа экономических систем: традиционная командная или административноплановая рыночная смешанная. Самой древней из экономических систем является традиционная система. Традиционная экономическая система способ организации экономической жизни при котором земля и капитал находятся в общем владении племени а ограниченные ресурсы распределяются в соответствии с длительно существующими традициями.
34699. Административно-плановая (командная) экономическая система 23.83 KB
  Административноплановая командная экономическая система существовала в СССР. Это объяснялось тем что в городах практически отсутствовало жилье для вновь прибывших и тем что в соответствии с законом СССР было очень сложно получить постоянную прописку в данном городе. Высшим плановым органом являлся Госплан СССР. Госплан СССР определял плановые задания республиканским и местным плановым органам а также плановым отделам министерств и ведомств которые давали плановые задания государственным предприятиям то есть указывали им...
34700. Монополия. Монопольная власть. Условия максимизации прибыли при монополии. Ценовая дискриминация 17.8 KB
  Монополия. Монополия тип рыночной системы в котором существует только один продавец контролирующий всю отрасль производства определенного товара не имеющего близкого заменителя. Закрытая монополия. Естественная монополия отрасль в которой долгосрочные средние издержки минимальны только тогда когда одна фирма обслуживает весь рынок целиком.
34701. Экономическая рента 16.61 KB
  Рассмотрим понятие экономической ренты на примере рынка труда где экономическая рента равна разности между фактической ценой труда и тем ее уровнем который достаточно для того чтобы привлечь работника трудиться по данной профессии рисунок1 Ставка зарплаты в час W1 Е S А D L1 Колво чел.L 0 1 2 3 4 5 Допустим что...
34702. Коммерческие банки. Центральный банк 17.35 KB
  Поэтому все частные банки называют коммерческими банками в отличие от Центрального банка. Операции любого банка подразделяются на пассивные и активные. Создание коммерческого банка начинается с того что его владелец акционерное общество должен инвестировать сложить собственные деньги в кассу банка деньги в строительство здания в оборудование сейфы и др. Чем выше процентная ставка по вкладу тем больше вкладчиков у банка.
34703. Бухгалтерские издержки и прибыль 20.08 KB
  Бухгалтерские издержки и прибыль. Экономические издержки и прибыль. Издержки производства поразному определяются бухгалтером и экономистом. Бухгалтер определяет издержки чтобы установить во что обошлось фирме производство продукции.
34704. Рынок и его функции. Виды рынков. Рыночная экономическая система 22.68 KB
  Рынок и его функции. Для домашней хозяйки рынок это городской базар или магазин. Поэтому рынок это форма контактов между продавцами и покупателями товаров и услуг недвижимости ценных бумаг и валюты. Таким образом рынок выполняет информационную функцию то есть через постоянно меняющиеся цены рынок сообщает производителям где и какой продукции не хватает где и какая продукция произведена с избытком.