69126

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

Лекция

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

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

Украинкский

2014-09-30

56.5 KB

5 чел.

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


 

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

79519. Основные принципы деятельности педагога-психолога 29.62 KB
  Принцип индивидуального подхода к учащемуся основной принцип работы практического психолога в его основе лежат понимание и признание индивидуальности человека как ценности как уникального явления. Принцип целостности предполагает что деятельность психолога и психологической службы образовательного учреждения должна быть ориентирована на целое на систему. Это означает что внимнием психолога должно быть охвачено большинство учащихся.
79520. Этические принципы деятельности психолога 31.11 KB
  Укрепление авторитета психологической службы образования среди обучающихся воспитанников родителей и педагогической общественности. Принцип квалификационной пропаганды психологии.Информация полученная психологом в процессе проведения работы не подлежит сознательному или случайному разглашению а в ситуации необходимости передачи ее третьим лицам должна быть представлена в форме исключающей ее использование против интересов клиента.
79521. Психологическая служба как отрасль прикладной психологии. Роль психологической службы в образовании 31.88 KB
  Государственная ПСО – структура призванная в рамках общей концепции соблюдения прав ребенка на достойный уровень жизни и полноценное психическое развитие обеспечить психологическую поддержку воспитания и образования оказать квалифицированную помощь при наличии проблем и отклонений в развитии ребенка Развитие практической психологии в 1990 гг. в значительной степени обусловило гуманизацию системы образования что способствовало постановке и решению следующих задач: Переход от унифицированного образования к вариативному; Переход от...
79522. Концепция школьной психологической службы Л.М. Фридмана 31.7 KB
  Фридмана цели школьной психологической службы должны соответствовать главной цели школы на современном этапе воспитание каждого ученика образованной культурной высоконравственной творчески активной и социально зрелой личностью. Поэтому главной целью школьной психологической службы является научное психологическое обеспечение учебновоспитательного процесса в школе т. Утверждается что главная функция психологической службы образования профессиональная забота о психологическом здоровье детей.
79523. Объединение Русских земель Москвы (14-первая половина 16 веков) 21.07 KB
  Объединение Руси начавшийся в XIV XV веках процесс объединения раздробленных русских земель вокруг нескольких новых политических центров приведший в конечном итоге к образованию централизованного Русского государства и его последующему возобладанию над внешними политическими конкурентами за земли Руси. Объединение Северовосточной Руси завершилось в правление Ивана III присоединение Новгорода 1478 Твери 1485 ликвидация формальной автономии Пскова 1510 и Рязани 1521. Он принял титул государя всея Руси...
79524. Начало эпохи великих географических открытий и первые колониальные захваты. Новое время как особая фаза всемирно исторического процесса 22.1 KB
  Новое время или новая история период в истории человечества находящийся между Средневековьем и Новейшим временем. Критерием определения нового времени его новизны по сравнению с предшествующей эпохой был с точки зрения гуманистов расцвет в период Ренессанса светской науки и культуры то есть не социальноэкономический а духовнокультурный фактор. Однако этот период довольно противоречив по своему содержанию: Высокое Возрождение Реформация и гуманизм соседствовали с массовым всплеском иррационализма развитием демонологии...
79525. Реформация и ее экономические, политические и социокультурные причины. Религиозные войны в Европе 21.7 KB
  С одной стороны католический мир который объединял все народы Западной Европы под духовным руководством папы римского прекратил существование. С другой стороны национальные церкви способствовали росту национального сознания народов Европы. При этом существенно повысился культурный и образовательный уровень жителей Северной Европы которая до этого была как бы окраиной Христианского Мира необходимость изучения Библии приводила к росту как начальных учебных заведений в основном в форме церковноприходских школ так и высших что...
79526. Государство и общество стран Западной Европы в 17 веке 21.34 KB
  Их концептуальным выражением и итогом стали теории естественного права и общественного договора основанные на рационализме. Теория естественного права явилась классическим воплощением нового мировоззрения. Теория естественного права основана на признании всех людей равными от природы и наделенными природой же естественными страстями стремлениями разумом. Законы природы определяют предписания естественного права которому должно соответствовать положительное позитивное волеустановленное право.
79527. Внутренняя и внешняя политика Ивана 4 Грозного 20.85 KB
  Иван IV стал великим князем в 1533 г. в 3 года. Регентшей была его мать Елена Глинская, а после ее смерти в 1538 г. началось боярское правление, сопровождавшееся борьбой боярских группировок. В 1547 г. Иван IV венчался на царство.