69126

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

Лекция

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

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

Украинкский

2014-09-30

56.5 KB

8 чел.

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


 

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

76251. Инвестиционные операции американских банков 41.78 KB
  Депозитные институты: Коммерческие банки предлагают чековые и сберегательные счета физическим лицам предпринимателям и правительственным агентствам. Сберегательные и ссудные ассоциации специализируются на сберегательных счетах и кредитовании под залог недвижимости.
76252. Абай Кунанбаев, Джамбул Джабаев 24.49 KB
  Огромную роль в просвещении своего народа сыграл основоположник письменной казахской литературы поэт Абай Кунанбаев (1845-1904). Сын богатого и деспотично го феодала Кунанбая, Абай порвал со своим отцом, многими обычаями предков, оспаривал установления корана,чтобы обратиться к подлинным источникам света и знания.
76253. Наказателен закон 1896 года 47.5 KB
  След Освобождението в България останал да действува Османският наказателен закон. Той обаче бил още по-малко пригоден да удовлетвори изискванията, които се поставяли пред новата българска държава, отколкото османските граждански закони.
76254. Абу-Симбел 926 KB
  Современное название Абу-Симбел произошло от скалы на которой в том месте где река делает к ней изгиб высечен в барельефе египетский мужчина в заострённом фартуке которого арабские моряки усматривали подобие хлебной меры...
76255. Крымская война в исторических и мемуарах 39.81 KB
  Он отражает дипломатическую обстановку этого кровавого конфликта; как смотрели на эту войну представители различных общественно-политических течений в Западной Европе и России; каким рисовалось современникам внутреннее положение России в рассматриваемый момент.
76256. Общие понятия сервиса. Социально-культурный, технический и технологический сервис 57.47 KB
  Перевозка в настоящее время является основным звеном в получении прибыли железнодорожным транспортом а сервисные услуги до и после перевозки должны поддерживать безубыточную работу принося перевозчику дополнительные прибыли.
76257. Hydroelectric power water use 214.71 KB
  Hydroelectric power must be one of the oldest methods of producing power. No doubt, Jack the Caveman stuck some sturdy leaves on a pole and put it in a moving stream. The water would spin the pole that crushed grain to make their delicious...
76259. Роль радиотермометрии при хирургическом лечении непальпируемых новообразований молочной железы 116.5 KB
  Исследований направленных на определение эффективности радиотермометрии для выявления ранних так называемых малых раков не проводилось. Данное обстоятельство послужило причиной для более подробного изучения возможностей радиотермометрии в скрининге непальпируемых новообразований молочных...