Елементи теорії алгоритмів

алгоритм - поняття, що відноситься до фундаментальних основ інформатики. Воно виникло задовго до появи комп'ютерів і є одним з основних понять математики.

слово «Алгоритм» походить від імені видатного середньовічного вченого Мухамеда ібн Муса Ал-Хорезмі(IXвек н.е.), скорочено Ал-Хорезмі. У латинському перекладі одного з праць Ал-Хорезмі правила виконання дій починалися словами DIXIT ALGORIZMI (Алгорізмі сказав), в інших латинських перекладах автор іменувався ALGORITHMUS (Алгорітмус).

У поняття «Алгоритм» немає чіткого, однозначного визначення в математичному сенсі. Можна дати лише опис (Пояснення) цього поняття. Для пояснення поняття «Алгоритм» велике значення має визначення поняття «Виконавець алгоритму» . Алгоритм формулюється в розрахунку на конкретного виконавця.

алгоритм - керівництво до дії для виконавця, тому значення слова «алгоритм» близьке за змістом до значення слів «вказівку» або «розпорядження».

алгоритм - зрозуміле і точне припис(вказівка) Виконавцю здійснити певну послідовність дій для досягнення зазначеної мети або вирішення поставленого завдання.

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

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

Основні властивості алгоритму

Масовість.

Алгоритм має деяке число вхідних величин - аргументів, що задаються до початку виконання. Мета виконання алгоритму - отримання результату (результатів), що має цілком визначене ставлення до вихідних даних. Алгоритм вказує послідовність дій по переробці вихідних даних в результати. Для алгоритму можна вибирати різні набори вхідних даних з безлічі допустимих для цього процесу даних, тобто можна застосовувати алгоритм для вирішення цілого класу задач одного типу, що розрізняються вихідними даними. Це властивість алгоритму зазвичай називають масовістю . Однак існують алгоритми, що застосовуються тільки до єдиного набору даних. Можна сказати, що для кожного алгоритму існує свій клас об'єктів, допустимих в якості вихідних даних. тоді властивість масовості означає застосовність алгоритму до всіх об'єктів цього класу.

Зрозумілість.

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

Дискретність.

Алгоритм представляється у вигляді кінцевої послідовності кроків (алгоритм має дискретну структуру) і його виконання розчленовується на виконання окремих кроків (виконання чергового кроку починається після завершення попереднього).

Кінцівка.

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

Визначеність.

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

Ефективність.

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

Наведені вище коментарі пояснюють інтуїтивне поняття алгоритму , Але саме це поняття не стає від цього більш чітким і суворим. Проте, в математиці довгий час використовували це поняття. Лише з виявленням алгоритмічно нерозв'язних завдань, тобто задач, для вирішення яких неможливо побудувати алгоритм, з'явилася нагальна потреба в побудові формального визначення алгоритму, відповідного відомому інтуїтивного поняття. Інтуїтивне поняття алгоритму в силу своєї невизначеності не може бути об'єктом математичного вивчення, тому для доказу існування або неіснування алгоритму розв'язання задачі було необхідно суворе формальне визначення алгоритму.

Побудова такого формального визначення було розпочато з формалізації об'єктів (операндів) алгоритму, так як в інтуїтивному понятті алгоритму його об'єкти можуть мати довільну природу. Ними можуть бути, наприклад, числа, показники датчиків, що фіксують параметри виробничого процесу, шахові фігури і позиції і т.п. Однак припускаючи, що алгоритм має справу не з самими реальними об'єктами, а з їх зображеннями, можна вважати, що операнди алгоритму - слова в довільному алфавіті. Тоді виходить, що алгоритм перетворює слова в довільному алфавіті в слова того ж алфавіту. Подальша формалізація поняття алгоритму пов'язана з формалізацією дій над операндами і порядку цих дій. Одна з таких формалізацій була запропонована в 1936 році англійським математиком А. Тьюрінг, який формально описав конструкцію деякої абстрактної машини ( машини Тьюринга ) Як виконавця алгоритму і висловив основну тезу про те, що всякий алгоритм може бути реалізований відповідної машиною Тьюринга. Приблизно в цей же час американським математиком Е.Постом була запропонована інша алгоритмічна схема - машина Посту , А в 1954 році радянським математиком А.А.Маркова була розроблена теорія класів алгоритмів, названих їм нормальними алгорифм , І висловлено основна теза про те, що всякий алгоритм нормалізуємо.

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

Логічні теорії алгоритмів цілком придатні для вирішення теоретичних питань про існування чи неіснування алгоритму, але вони ніяк не допомагають у випадках, коли потрібно отримати хороший алгоритм, придатний для практичних застосувань. Справа в тому, що з точки зору логічних теорій алгоритми, призначені для практичних застосувань, є алгоритмами в інтуїтивному сенсі. Тому при вирішенні проблем, що виникають у зв'язку зі створенням і аналізом таких алгоритмів, нерідко доводиться керуватися лише інтуїцією, а не суворої математичної теорією. Таким чином, практика поставила задачу створення змістовної теорії, предметом якої були б алгоритми, як такі, і яка дозволяла б оцінювати їх якість, давала б практично придатні методи їх побудови, еквівалентного перетворення, докази правильності і т.п.

Змістовна (аналітична) теорія алгоритмів стала можливою лише завдяки фундаментальним роботам математиків в області логічних теорій алгоритмів. Розвиток такої теорії пов'язано з подальшим і розширенням формального поняття алгоритму, яке занадто звужене в рамках логічних теорій. Формальний характер поняття дозволить застосовувати до нього математичні методи дослідження, а його широта повинна забезпечити можливість охоплення всіх типів алгоритмів, з якими доводиться мати справу на практиці.

Тема: Алгоритм. властивості алгоритму

алгоритм- це зрозуміле і точне розпорядження виконавцю, виконати кінцеву послідовність кроків, що приводить від вихідних даних до шуканого результату

властивості алгоритму

q Дискретність (переривчастість) - алгоритм повинен бути розбитий на
послідовність виконуваних кроків;

q Визначеність (детермінованість, точність) -алгоритм
повинен бути однозначно (точно) реалізований виконавцем.

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

q Кінцівка (результативність)- за кінцеве число кроків
повинен бути отриманий результат;

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

q зрозумілість – алгоритм повинен містити тільки ті команди,
які розуміє конкретний виконавець.

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

При всьому різноманітті алгоритмів розв'язання задач в них можна виділити три основних види обчислювальних процесів:

· Лінійний;

· Розгалужених;

· Циклічний.

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

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

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

Дайте відповідь на питання тесту

1. До основних властивостей алгоритму відносяться ...

а) стислість, визначеність, вірність, масовість, формальність

б) дискретність, важливість, результативність, вірність, формальність

в) достовірність, уривчастість, результативність, узагальненість, формальність

г) опеределения, важливість, результативність, масовість

2. Графічний опис алгоритму-це опис за допомогою ...

а) ... .діаграмм

б) ... блок-схем

в) ... графіків

г) ... всіх перерахованих вище способів

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

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

а) масовість

б) результативність

в) формальність

г) достовірність

4. Опис алгоритму на алгоритмічній мові - це засіб для запису алгоритму ..

а) ... в теоретичному вигляді

б) ... у вигляді схем

в) ... в аналітичному вигляді

г) ... в спеціальному вигляді

5. Властивість алгоритму, що визначає покроковий характер алгоритму називається ...

а) результативністю

б) однозначністю

в) дискретністю

г) масовістю

д) всі властивості визначають покроковий характер алгоритму

6. Алгоритм, називається лінійним, якщо ...

а) він складений так, що його виконання передбачає багатократне повторення одних і тих же дій;

б) послідовність виконання його команд залежить від істинності тих чи інших умов;

в) його команди виконуються в порядку їхнього природного дотримання один за одним незалежно від будь-яких умов;

г) він включає в себе допоміжний алгоритм;

д) його запис представлена ​​у вигляді одного рядка.

7.К основних властивостей алгоритму НЕ відноситься ...

а) коректність;

б) визначеність

в) масовість

г) результативність

ПОНЯТТЯ АЛГОРИТМУ. Властивості алгоритму. ВИДИ алгоритмів. СПОСОБИ ОПИСУ АЛГОРИТМІВ

Алгоритмом називається точний і зрозуміле предпісаніe виконавцю здійснити послідовність дій, спрямованих на вирішення поставленого завдання. Слово «алгоритм» походить від імені математика Аль Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над числами. Надалі це поняття стали використовувати взагалі для позначення послідовності дій, що призводять до вирішення всіх поставлених завдань. Говорячи про алгоритм обчислювального процесу, необхідно розуміти, що об'єктами, до яких застосовувався алгоритм, є дані. Алгоритм рішення обчислювальної задачі являє собою сукупність правил перетворення вихідних даних в результатні.

основними властивостями алгоритму є:

1. детермінованість (визначеність). Призів будуть однозначного результату обчислювального процecca при заданих вихідних даних. Завдяки цій властивості процес виконання алгоритму носить механічний характер;
2. результативність. Вказує на наявність таких вихідних даних, для яких реалізується за заданим алгоритмом обчислювальний процес повинен через кінцеве число кроків зупинитися і видати шуканий результат;
3. масовість. Це властивість передбачає, що алгоритм повинен бути придатний для вирішення всіх завдань даного типу;
4. дискретність. Чи означає розчленованість визначається алгоритмом обчислювального процесу на окремі етапи, можливість виконання яких виконавцем (комп'ютером) не викликає сумнівів.

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

Найбільшого поширення завдяки своїй наочності отримав графічний (блок-схемний) спосіб запису алгоритмів.

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

При всьому різноманітті алгоритмів розв'язання задач в них можна виділити три основні види обчислювальних процесів:

• лінійний;
• розгалужених;
• циклічний.

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

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

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

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

1. Виконання алгоритму розбивається на послідовність закінчених дій-кроків. Тільки виконавши одну дію (команду), можна приступати до виконання наступного. Це властивість алгоритму називається дискретністю. Провести кожну окрему дію виконавцю наказує спеціальна вказівка ​​в записі алгоритму (команда).

2. зрозумілість- алгоритм не повинен містити приписів, зміст яких може сприйматися виконавцем неоднозначно, тобто запис алгоритму повинна бути настільки чіткою і повною, щоб у виконавця не виникало потреби в ухваленні будь-яких самостійних рішень. Алгоритм завжди розрахований на виконання «не роздумуючи" виконавця. Алгоритм складається з команд, що входять в СКІ.

Розглянемо відомий приклад "побутового" алгоритму - алгоритм переходу вулиці: "Подивися наліво. Якщо машин немає, дійди до середини вулиці. Якщо є, почекай, поки вони проїдуть, і т.д. ". Уявіть собі ситуацію: машина зліва є, але вона не їде - у неї змінюють колесо. Якщо ви думаєте, що виконавець алгоритму повинен чекати, то ви зрозуміли цей алгоритм. Якщо ж ви вирішили, що вулицю переходити можна, вважаючи алгоритм підправленим зважаючи на непередбачені (на вашу думку!) Обставин, то ви не засвоїли поняття алгоритму.

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

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

Властивість результативності містить в собі властивість кінцівки- завершення роботи алгоритму за кінцеве число кроків.

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

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

поняття алгоритму

Узагальнивши вищесказане, сформулюємо наступне поняттяалгоритму.

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

Наведене визначення не є визначенням в математичному сенсі слова, тобто це не формальне визначення (формальне визначення алгоритму см. в статті " теорія алгоритмів”).

Відзначимо, що для кожного виконавцянабір допустимих дій (СКІ) завжди обмежений - не може існувати виконавця, для якого будь-яка дія є допустимим. Перефразований міркування І. Канта обґрунтовує сформульоване твердження наступним чином: "Якби такий виконавець існував, то серед його допустимих дій було б створення такого каменю, який він не може підняти. Але це суперечить допустимості дії «Підняти будь-який камінь» ".

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

З іншого боку, існують завдання, для яких взагалі неможливо побудувати процедуру вирішення. Причому даний факт можна строго довести. Про це ви можете прочитати в статті " Алгоритмічно нерозв'язні проблеми” 2.

Переймається тим знаходження максимального потоку в транспортній мережі. Алгоритм не є окремим випадком алгоритму Форда Фалкерсона. Реалізований без спеціальних удосконалень, алгоритм виконується за час. Деякі удосконалення ще ... Вікіпедія

Алгоритми локального пошуку група алгоритмів, в яких пошук ведеться тільки на підставі поточного стану, а раніше пройдені стану не враховуються і не запам'ятовуються. Основною метою пошуку є не знаходження оптимального шляху до ... ... Вікіпедія

Цей термін має також інші значення див. Mars (значення). MARS Створено: 1998 г. Опубліковано: 1998 г. Розмір ключа ... Вікіпедія

Цей термін має також інші значення див. Mars (значення). MARS Створено: 1998 р ... Вікіпедія

Цей термін має також інші значення див. Алгоритм (значення). Для поліпшення цієї статті бажано ?: Переробити оформлення відповідно до правил ... Вікіпедія

Ця стаття включає матеріал з цієї версії відповідної статті англійської Вікіпедії. Операциональное перетворення (ВП) являє собою технологію для підтримки цілого ряду функціональних можливостей співпраці в передових системах ... ... Вікіпедія

Алгоритми пошуку на графах A * B * Алгоритм Беллмана Форда Двохнаправлений пошук Алгоритм Дейкстри Алгоритм Джонсона Пошук в ширину Пошук в глибину Пошук з обмеженням глибини Пошук по першому найкращому збігу Алгоритм Флойда Уоршелла Пошук ... ... Вікіпедія

Це алгоритм для впорядкування елементів в списку. У разі, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в інших полях ... ... Вікіпедія

BMW (англ. BMW Blue Midnight Wish) криптографічний хеш функція (хф) з виходом в n біт, де n = 224,256, 384 або 512. Хеш функції призначені для створення «відбитків» або «дайджестів» повідомлень довільної бітової довжини. ... ... Вікіпедія

Цю статтю слід вікіфіціровать. Будь ласка, оформіть її згідно з правилами оформлення статей. Цей термін має також інші значення див. TEA (значення) ... Вікіпедія

книги

• Логіки Лукасевича і прості числа, А. С. Карпенко, Вперше у світовій літературі в монографічному дослідженні встановлюється прямий зв'язок між логікою і простими числами. Хоча багатозначні логіки Лукасевича з'явилися результатом спростування ... Категорія: Логіка Видавець: Либроком,
• Логіка в питаннях і відповідях. Навчальний посібник, Кобзар Володимир Іванович, Навчальний посібник написаний відповідно до програми курсу традиційної (загальною, філософської) формальної логіки. У ньому розглянуті основні форми і методи розумової діяльності, їх ... Категорія: