Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Поняття структури даних

План

1 Експоненційні алгоритми та перебір

2 Алгоритм із поверненнями назад

3 Машини Тьюринґа

4 Рекурсія та її використання

5 Теза Чорча. Алгоритмічно нерозв'язні проблеми

Основною оцінкою функції складності алгоритму f(n) є оцінка Θ (тета).

Кажуть, що f(n)= Θ (g(n)), якщо при g> 0 при n > 0 існують додатні с₁, с₂, n₀, такі, що

c₁g(n)≤f{n)≤c₂g(n)

при n > n₀. Тобто, можна знайти такі с₁, та с₂, що при достатньо великих n функція f(n) знаходитиметься між c₁g(n) та c₂g(n).

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

Виділяють такі основні класи алгоритмів:

ü логарифмічні: f(n) = Θ (log₂n);

ü лінійні: f(n) = Θ (n); якщо n=1, то отримуємо константі алгоритми;

ü поліноміальні: f(n) = Θ (n^m); тут m — натуральне число, більше від одиниці; при m=1 алгоритм є лінійним;

ü експоненційні: f(n) = Θ (аⁿ); а - натуральне число, більше від одиниці.

Експоненційні алгоритми часто пов'язані з перебором різних варіантів розв'язку.

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

Будемо називати часовою складністю задачі часову складність найефективнішого алгоритму для її розв'язання.

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

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

Приклад 1.7. Розглянемо алгоритм опрацювання елементів масиву. Нехай таким опрацюванням буде пошук заданого елемента.

For i:=1 to N do

Begin

If a[i]=k then

…

End;

Складність цього алгоритму (N), оскільки тіло циклу виконується N разів, і складність тіла циклу рівна (1).

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

For i:=1 to N do

For j:=1 to N do

Begin

…

End;

Складність цієї програми (N²).

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

Дамо тепер визначення складності класів задач Р і NP. Клас Р складається з задач, для яких існують поліноміальні алгоритми розв'язання. Клас NP складають задачі, для яких існують поліноміальні алгоритми перевірки правильності рішення (точніше, якщо є розв'язок задачі, то існує деяка підказка, яка дозволяє за поліноміальний час отримати цю відповідь). Неформально кажучи, клас Р складається зі задач, які можна швидко розв'язати, а клас NP - зі задач, розв'язок яких можна швидко перевірити.

Наведемо приклад задачі класу Р. Треба визначити, чи є у масиві дійсних чисел А[1..n] елемент зі значенням не меншим, ніж к. Очевидний у цьому випадку алгоритм перебирає всі елементи масиву за час (n).

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

Очевидним є також включення Р NP (для перевірки розв'язання задачі класу Р досить розв'язати її поліноміальним алгоритмом).

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

NP-повні задачі є найважчими у класі NP.

1 Експоненційні алгоритми та перебір

Експоненційні алгоритми часто пов'язані з перебором різних варіантів розв'язання.

Наведемо типовий приклад.

Приклад 1.8. Розглянемо задачу про виконуваність булевого виразу, яка формулюється так: для будь-якого булевого виразу від її змінних знайти хоча б один набір значень змінних х₁.. х_n, при якому цей вираз приймає значення 1.

Типова схема розв'язування цієї задачі може мати такий вигляд: спочатку надаємо одне з двох можливих значень (0 або 1) першій змінній х₁, потім другій і т.ін. Коли будуть розставлені значення всіх змінних, ми можемо визначити значення булевого виразу. Якщо він дорівнює 1, задача розв'язана. Якщо ні – треба повернутися назад і змінити значення деяких змінних.

Можна інтерпретувати цю задачу як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень х₁ ...,х_k. Ми можемо встановити змінну х_k₊₁ в 0 або 1, тобто маємо вибір з двох дій. Тоді кожній із цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Вершина х₁ ...,х_k має двох синів х₁ ...,х_k 0 і х₁ ...,х_k 1.

При n=3 дерево можливостей матиме вигляд, показаний на рисунку 2 (вершини позначені наборами значень змінних, а дуги - рішеннями, які приймаються па черговому кроці). Вершини, що відповідають розв'язкам задачі для виразу (x₁x₂) є х₃, зафарбовані.

З рис.2 видно, що розв'язування задачі зводиться до перебору листків дерева з метою виявлення, які з них відповідають наборам, що перетворюють заданий булевий вираз на 1. Для виразу (x₁x₂) є х₃, такими наборами будуть 000, 010, 111.

Якщо n=3, дерево має 2³= 8 листів. У загальному ж випадку кількість можливих варіантів дорівнює 2ⁿ. Цей вираз експоненційно залежить від n, і перебірний алгоритм має експоненційний характер.

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

Рисунок 2 – Пошук на дереві.

Звертаємо увагу на те, що не кожен перебірний алгоритм є експоненційним. (Наприклад, алгоритм пошуку в масиві. Незважаючи на його перебірний характер, він є лінійним, а не експоненційним).

Зі зростанням розмірності будь-який поліиоміальний алгоритм стає ефективнішим, ніж будь-який експоненційний. Дня лінійного алгоритму зростання швидкодії комп'ютера в 10 разів дозволяє за той самий час розв'язати задачу, розмір якої в 10 разів більший. Для експоненційного алгоритму з основою 2 цей самий розмір можна збільшити лише на 3 одиниці.

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

2 Алгоритм із поверненнями назад

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

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

{пошук одного вирішення}

procedure backtracking(k: integer); {k - номер ходу}

begin

{запис варіанту}

if {рішення знайдене} then

{виведення рішення}

else

{перебір всіх варіантів}

if { варіант задовольняє умови задачі} then

backtracking(k+1); {рекурсивний виклик}

{стирання варіанту}

end

begin

backtracking(1);

end.

3 Машини Тьюринґа

Машина Тьюринґа, що була описана А.Тьюринґом 193 6 року, є теоретичною моделлю обчислювальної машини. Машину Тьюринґа (МТ) (рисунок 3) слід розглядати як одну з можливих формалізацій поняття алгоритму. її робота може бути описана таким чином.

Рисунок 3 – Схема машини Тьюринґа.

Розглянемо стрічку, розділену на окремі комірки; ця стрічка є потенційно нескінченною в обидва боки. У кожній комірці може бути записаний певний символ з деякого заданого алфавіту А. Машина Тьюринґа в будь-який момент часу може перебувати в певному стані (множина станів S є скінченною) і вказувати на певну комірку.

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

Програма машини Тьюринґа є послідовністю інструкцій, кожна з яких має вигляд

a_is_j → a_ks_lI,

де a_i, a_kє A; s_l, s_j,S,I є {R,L,H}.

Цей запис читається так: якщо машина перебуває в стані s_l і зчитує символ a_i, вона повинна записати в поточну позицію символ a_k, перейти до стану s_j і зсунутися вправо (відповідає літері R), вліво (відповідає літері L) або зупинитися (відповідає літері H).

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

Приклад 1.9. Наведемо програму для машини Тьюринґа, яка обчислює функцію х+у, де х,у - натуральні числа. Необхідно домовитися про відображення цих чисел. Стандартним для машини Тьюринґа є подання натурального числа n послідовністю з n+1 одиниць.

Ідея реалізації такої програми могла б полягати у тому, щоб замінити крайній зліва та крайній справа символи ≪1≫ на ≪0≫, а роздільник ≪0≫ - на ≪1≫. Якби були доступні відповідні команди, це можна було б зробити просто і швидко, але ми обмежені жорсткими рамками машини Тьюринґа. За таких умов схема алгоритму полягає в такому: рухатися вправо до виявлення першої одиниці (початок першого числа); як тільки вона буде виявлена, замінити її на нуль і перейти в інший стан s₁. Потім рухатися вправо, поки 0, який розділяє два числа, не буде замінений на 1; при цьому знову змінити стан. Далі рухатися вправо до появи першого нуля (кінця другого доданку). Після цього зсунутися вліво, замінити останню 1 на 0 та зупинитися.

Програма може мати вигляд:

Наведений приклад показує, що машина Тьюринґа є дуже незручною для програмування. Ці незручності пов'язані з тим, що:

• немає довільного доступу до пам'яті; якщо, наприклад, машина вказує на першу комірку, а треба перейти до десятої, машина повинна послідовно переглянути другу, третю і т.ін. комірки;

• неструктурованють записів на стрічці; заздалегідь невідомо, де закінчується одне число і починається інше;

• дуже обмежений набір команд; відсутні, наприклад, основні арифметичні операції.

Універсальну машину Тьюринґа можна неформально визначити як машину, яка може сприймати програму для обчислення будь-якої функції, яку, в принципі, можна обчислити за допомогою спеціалізованої машини М1 і надалі працювати, як машина М1. Можна довести, що таку машину можна побудувати.

Багатство можливостей конструкції Тьюринґа полягають у тому, що якщо якісь алгоритми А та В реалізуються машинами Тьюринґа, то можна будувати програми машин Тьюринґа, які реалізують композиції алгоритмів А та В, наприклад, виконати А, потім виконати В або виконати А знову. Якщо в результаті утворилося слово ≪так≫, то виконати В. У протилежному випадку не виконувати В або виконувати по черзі А, В, поки В не дасть відповідь ≪ні≫.

У інтуїтивному сенсі такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Тьюринґа служить одним із засобів обґрунтування універсальності конструкції Тьюринґа.

Реалізованість таких композицій доводиться у загальному вигляді, незалежно від особливостей конкретних алгоритмів А та В. Доведення полягає в тому, що вказується засіб побудови з програм А та В програми требаї композиції. Нехай, наприклад, треба побудувати машину А \cdot В, еквівалентну послідовному виконанню алгоритмів А та В. Поки виконується алгоритм А, у програмі A\cdot В працює частина А без урахування частини В. Коли алгоритм А дійде до кінця, то замість зупинки відбудеться перехід у перший стан частини В, і потім частина В буде працювати звичайним чином, наче частини А й не було.

Аналогічно конструюють й інші композиції машин Тьюринґа; щораз будуються загальні правила, які визначають, що на що змінювати у вихідних програмах.

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

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

Тьюринґа.

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

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

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

усе, що реалізовано в одній з цих конструкцій, можна зробити і в інших.

Ці твердження доводяться строго, тому що в них мова йде вже про тотожність формальних схем.

4 Рекурсія та її використання

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

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

До базових примітивних рекурсивних функцій відносяться три функції:

1) нуль-функція Z(x)=0 при будь-якому х;

2) додавання одиниці: N(x) = х+1;

3) проектуючі функції: U_i(x_l,...,x_n)=x_i для всіх х₁,...,х_n.(визначає натуральне число з цієї множини).

Функція f(х₁,…,х_n) отримана з функцій g, h₁,...,h_m, за допомогою підстановки, якщо f(х₁,…,х_n) = g(h₁(х₁,…,х_n),...,h_m(х₁,…,х_n)).

Функція f(х₁,…,х_n,y) отримана за допомогою рекурсії, якщо:

f(х₁,…,х_n,y+1)=h(х₁,…,х_n,y, f(х₁,…,х_n,y));

f(х₁,…,х_n,0)=g(х₁,…,х_n) при n≠0;

f(y+1)=h(y,f(y)); f(0)=k, k – ціле невід'ємне число при n = 0.

Функція f(х₁,…,х_n) отримана за допомогою µ-оператора, якщо її значення дорівнює мінімальному значенню у, при якому g(х₁,…,х_n,y)=0.

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

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

Приклад 1.10. Визначення функції ≪факторіал≫ задаються виразом: 0!=1, n!=nх (n-1)!. Вони утворюють множину {1,2,6,...}: 0!=1, 1!=1, 2!=2, 3!=6, ... . Усі її елементи, крім першого, визначаються рекурсивно.

Отже, функція ≪факторіал≫ задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Загалом, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності є прикладом рекурсивного означення.

Приклад 1.11. Арифметичні вирази зі сталими та знаком операції ‘+’ у повному дужковому записі (ПДЗ) задаються таким означенням:

1) стала є виразом у ПДЗ;

2) якщо Е і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.

Для коректного виходу з рекурсії повинні виконуватися умови:

ü множина означуваних об'єктів є частково упорядкованою;

ü кожна спадна за цим впорядкуванням послідовність елементів закінчується деяким мінімальним елементом;

ü мінімальні елементи означаються нерекурсивно;

ü неміпімшіьні елементи означаються за допомогою менших від них елементів.

Глибина рекурсії – кількість викликів підпрограми, що реалізують рекурсію.

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

Наведемо приклад нерекурсивного та рекурсивного визначення значення функції.

Приклад. 1.12. Маємо функцію, що розкладається у ряд:

#include <stdio.h>

#include<math.h>

double func1 (int n); // прототип нерекурсивної функції ряду

double func2(int n); // прототип рекурсивної функції ряду

void main()

{

int n; // n - кількість елементів ряду

double s=1; // значення функції

scanf("%n", &n); // ввели кількість елементів ряду

printf("Nonrecursiv result is %6.2f", func1(n));

printf("Recursiv result is %6.2f", func2(n));

}

double func1 (int n)

{

double s=1;

int x; // x - поточний член ряду

for(x=1;x<=n;x++)

s*=x/(exp(x) - x*x)

return (s);

}

double func2(int n)

{

double s=1;

if (n<1) // умова виходу з рекурсії

return (s);

else

s*=n/(exp(n) - n*n)*func2(n-1);// виклик рекурсивної функції з

n-1

}

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

Найяскравіший приклад задачі такого плану- задача про ханойські вежі.

Легенда свідчить, що десь в Ханої знаходиться храм, в якому розміщена така конструкція: на підставці знаходяться З діамантових стержня, на яких при створенні світу Брахма нанизав 64 золотих диска із отвором посередині, причому внизу опинився найбільший диск, на ньому трохи менший і так далі, поки на верхівці піраміди не опинився найменший диск. Жерці храму зобов'язані перекладати диски за такими правилами:

1) за один хід можна перенести лише один диск,

2) не можна класти більший диск на менший.

Керуючись цими правилами, жерці повинні перенести початкову піраміду з 1-го стержня на 3-й. Як тільки вони впораються з цим завданням, настане| кінець світу.

Для розв'язання задачі спочатку спробуємо побудувати абстрактну модель процесу перенесення частини піраміди.

Отже, вирішуємо узагальнену задачу: як перенести піраміду з n кілець із стержня i на стержень j, користуючись стержнем k як допоміжним? Ця задача розв'язується таким чином.

1. Перенести (n-1) кільце i на k.

2. Перенести 1 кільце з i на j.

3.Перенести (n-1) кільце на j.

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

Реалізація алгоритму на мові С:

void Hanoj (int n, short і, short j , short k)

// перенесення піраміди з n дисків з стержня i

// на стержень j , використовуючи стержень k як допоміжний

{

//перевірка граничної умови - порожню піраміду не переміщувати

if (!n) return;

Hanoj (n-1, і, k,j);

// переносимо одне кільцо - фактично це Hanoj (1, і, j , k);

printf(≪%2d-%2d\n≫,i,j);

Hanoj (n-1, k, j , i);

}

5 Теза Чорча. Алгоритмічно нерозв'язні проблеми

Теза Чорча часто формулюється в еквівалентній формі, а саме: буць-який алгоритм в інтуїтивному розумінні цього слова може бути реалізований за допомогою деякої машини Тьюринґа. Іншими словами, за допомогою машини Тьюринґа можна розв'язати будь-яку задачу, для якої істгує алгоритм розв'язування в інтуїтивному розумінні.

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

Якщо ми визнаємо тезу Чорча, ми можемо прийняти машину Тьюринґа як основу для загального визначення алгоритму: алгоритм є послідовністю інструкцій, яка може бути виконана за допомогою машини Тьюринґа або еквівалентної їй обчислювальної моделі.

Тепер ми можемо дати більш чітке визначення універсального комп'ютера: універсальним називається комп'ютер, за допомогою якого можна промоделювати роботу машини Тьюринґа.

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

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

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

Контрольні питання

1. Яка різниця між поліноміальними та експоненційними класами алгоритмів?

2. Дайте визначення часової складності.

3. Дайте визначення класу задач Р та NP.

4. Поясніть принцип роботи машини Тьюринґа.

5. Дайте визначення рекурсивної функци.

6. Наведіть приклади частково рекурсивної функції.

7. Наведіть приклад примітивної рекурсії.

8. Дайте визначення терміну ≪глибина рекурсії≫.

9. Наведіть приклади рекурсивних функцій.

10. Сформулюйте тезу Чорча.

11. Вкажіть відмінність між інформацією та даними.

Тести для закріплення матеріалу

1. Оберіть визначення інформатики:

а) це наука про методи подання, накопичення, передавання та опрацювання інформації за допомогою електронно-обчислювальних машин;

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

в) це наука про відображення реальних об'єктів, процесів, подій тощо на комп'ютерних носіях;

г) це одних із видів програмування та проектування.

2. Визначте поняття загальної інформатики:

а) блок-схема;

б) задача;

в) функція мети;

г) алгоритм.

3. Визначте поняття алгоритму:

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

б) скінчена послідовність машинних команд для розв'язебання конкретної задачі;

в) записана на певній мові програмування послідовність операторів, що подає конкретну задачу;

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

д) скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.

4. Дати поняття виконавця:

а) пристрій, здатний виконувати дії із заданого набору дій;

б) команда на виконання окремої дії;

в) складається з пристрою керування і ≪робочого інструмента≫;

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

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

5. Способи описування алгоритмів:

а) словесний;

б) схематичний;

в) табличний;

г) формульний;

д) графічний;

о) алооритмічною мовою.

6. Властивість алгоритму ≪скінченність≫ інакше ще називають:

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

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

в) масовість;

г) дискретність;

д) правильність.

7. Перерахувати класи алгоритмів:

а) логарифмічні;

б) табличні;

в) лінійні;

г) прогресійні;

д) поліноміальні;

є) експоненційні.

8. Дати визначення рекурсїї:

а) формує наступне у прогресії значення;

б) підпрограма викликає саму себе;

в) задає елементи множини за допомогою інших елементів цієї ж множини;

г) використовується для розрахунків над матрицями.

ЛЕКЦІЯ № 3

Тема: Поняття структури даних

Ціль: розглянути різні типи структур даних, рівні структур даних та їх класифікація, особливості відображення структур даних у пам’яті комп’ютера

2 Рівні описування даних

3 Класифікація структур даних у програмах користувача й у пам'яті комп'ютера

4 Основні види складених типів даних

5 Структури даних у пам'яті комп'ютера

5.1 Структури даних в оперативній пам'яті

5.2 СД у зовнішній пам'яті

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Визначення алгоритму	\|	Поняття структури даних

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.024 сек.