69126

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

Лекция

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

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

Украинкский

2014-09-30

56.5 KB

9 чел.

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


 

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

73996. Огосударствление экономики СССР.Индустриализация и коллективизация в СССР 28.31 KB
  Необходимость проведения индустриализации в России мало у кого вызывает какиелибо сомнения. Впрочем по вопросу о темпах и методах индустриализации в советском руководстве не существовало единства мнений. оставляла единственную возможность получить средства для индустриализации за счет мобилизации внутренних ресурсов. С точки зрения наиболее решительных сторонников индустриализации Е.
73997. Основные особенности и этапы внешней политики СССР между двумя мировыми войнами 18.92 KB
  Основные особенности и этапы внешней политики СССР между двумя мировыми войнами. Условия возникновения Советского государства в рамках мировой и гражданской войн активного участия в этом процессе значительного числа иностранных государств и особенности большевистской идеологии с приоритетом в постановке задач общемировым устремлениям во многом обусловили цели и средства внешней политики СССР в 20 30х гг. С другой стороны СССР являлся наследником Российской империи с ее очевидными национальными и государственными интересами защита...
73998. Великая Отечественная война: крупнейшие военные операции 1941 – 1945 годов 21.99 KB
  Великой Отечественной войне первоначальный ход военных действий сложился крайне неблагоприятно для СССР. Суворовым идея неподготовленности СССР к войне оборонительной ввиду подготовки его к войне наступательной иными словами воскрешение еще Гитлером выдвинутой концепции превентивной вынужденной войны с целью обезопасить себя от нападения Красной Армии. Таким образом Советский Союз в упорной борьбе сумел одержать победу в Великой Отечественной и разделить успех с союзниками по антигитлеровской коалиции во II мировой войне. Полководческое...
73999. Деятельность тыла в Великой Отечественной войне. Партизанское движение в годы Великой Отечественной войны 17.77 KB
  Партизанское движение в годы Великой Отечественной войны. Благодаря высокому уровню централизации государственного хозяйства в первые же месяцы войны удалось обеспечить его перестройку на военномобилизационный лад. Успех во многом определялся удачной организацией управления страной в условиях войны: при всех своих издержках советская система как раз и была предназначена для действия в условиях чрезвычайных обстоятельств для быстрой и решительной мобилизации имеющихся ресурсов и их перераспределения в соответствии с первоочередными...
74000. СССР во 2-й половине 50 - 1-й половине 80-х гг. XX в. От попыток либерализации к всеобщему кризису 22.46 KB
  Первые послевоенные годы принесли мало изменений в функционирование политической системы СССР. Будучи отражением реальной потребности в мобилизации сил для быстрого завершения восстановительных работ централизация в то же время подошла к своему пределу за которым она теряла всякую эффективность что отчетливо проявилось в нарастании кризисных явлений во всех сферах жизни СССР в начале 50х гг. Все это подводило руководящие круги СССР к осознанию необходимости преобразований.
74001. Основные направления и этапы внешней политики СССР в годы «холодной войны» 19.09 KB
  Основные направления и этапы внешней политики СССР в годы холодной войны. Победа СССР в войне значительно изменило его международное положение. СССР принял участие в создании ООН где ему было определено место одного из постоянных членов Совета безопасности.президент США сформулировал доктрину Трумена меры против экспансии СССР.
74002. Перестройка 1985 – 1990 годов 22.31 KB
  Именно эти меры положили начало развалу политической системы СССР поскольку именно партийная вертикаль обеспечивала реальное функционирование политической системы; советские органы были властью сугубо номинальной а потому оказались не готовы к выполнению возложенных на них полномочий. когда оппозиции удалось добиться отмены 6й статьи Конституции СССР закрепляющей особую роль КПСС в государственной системе СССР и внушительного представительства в ряде...
74003. Становление новой российской государственности в 1990-е годах 18.55 KB
  Распавшийся Советский Союз оставил весьма сложное наследство России в виде экономического кризиса всеобщего социального недовольства и наконец отсутствия реальной российской государственности. В условиях краха умеренной и консервативной моделей периода перестройки вполне естественной была победа весьма радикальной для России концепции демократического либеральнорыночного государства с ориентацией на западные страны. В принципе основные направления реформ к моменту их осуществления в России были уже испытаны в ряде государств Восточной...
74004. Основные этапы развития исторической науки в России XVIII – начале XX веков 20.07 KB
  Главною заслугою Миллера было собирание материалов по русской истории; его рукописи так наз. И исследования Миллера имели значение он был одним из первых ученых заинтересовавшихся позднейшими эпохами нашей истории им посвящены его труды: Опыт новейшей истории России и Известие о дворянах Российских. видное место трудами по русской истории занял и М.