На головну

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

  1.  I. 1. 1. Поняття про психологію
  2.  I. 1. 3. Поняття про свідомість
  3.  I. Поняття про мови і її функціях
  4.  I. Поняття про інформацію. Загальна характеристика процесів збору, передачі, обробки та накопичення інформації
  5.  I. Поняття про інформацію. Загальна характеристика процесів збору, передачі, обробки та накопичення інформації
  6.  I. Поняття патристики. Короткий огляд патріотичної традиції. 1 сторінка
  7.  I. Поняття патристики. Короткий огляд патріотичної традиції. 2 сторінка

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

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

1. Масовість.

2. покрокова.

3. Елементарність окремих кроків (що таке «елементарно» кожен Ватсон розуміє по-своєму).

4. детермінованість (точно відомо, що потрібно робити після кожного кроку).

5. Ефективність (алгоритм повинен привести до вирішення за кінцеве число кроків).

Головне розчарування програмістів щодо теорії алгоритмів полягає в тому, що класична теорія алгоритмів не займається «правилами побудови алгоритмів». На законне питання, чому ж вона тоді займається, можна гідно відповісти: вона займається більш важливою проблемою - проблемою алгорітміческойразрешімості. Тобто займається визначенням того, чи можливо взагалі побудувати алгоритм для вирішення завдань даного типу.

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

неможливо побудувати функцію

F (х) = ? 1, якщо в числі p є послідовність з х поспіль цифр 5

i0, інакше.

Цікава у зв'язку із цим теорема:

теорема:Алгоритмічно нерозв'язних завдань більше, ніж алгоритмічно розв'язаних.

Доведення:Потужність безлічі функцій (якщо завгодно - завдань) навіть свідомо обмежена:

f

N ® N

Проте, ніж контінуум- A1

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

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

Таким чином, A1 - A0 = A1

 




 Повні графи і дерева |  дерева |  алгоритм Краскала |  Завдання про 4 фарбах |  Визначення шляхів в графі |  Приведення графа до ярусно-паралельній формі |  Внутрішня стійкість графа |  ядро графа |  Побудова Кліки. |  морфізм груп |

© um.co.ua - учбові матеріали та реферати