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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

б) задача;

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

г) алгоритм.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

б) табличні;

в) лінійні;

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

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

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

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

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

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

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

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

ЛЕКЦІЯ № 3

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

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

План

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

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

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

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

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

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

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

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

Структура даних (СД) - загальна властивість інформаційного об'єкта, з яким взаємодіє та або інша програма. Ця загальна властивість характеризується:

ü множиною допустимих значень цієї структури;

ü набором допустимих операцій;

ü характером організованості.

Найпростіші структури дацих називаються також типами даних.

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

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

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

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

Розрізняють наступні рівні описуваннявання даних:

• абстрактний (математичний) рівень;

• логічний рівень;

• фізичний рівень.

Логічний рівень (ЛСД) – подання структури даного на тій чи іншій мові програмування.

Фізичний рівень (ФСД) — відображення у пам'ять комп'ютера інформаційного об'єкту відповідно до логічного описування.

Оскільки пам'ять комп'ютера обмежена, то виникають питання розподілу пам'яті й керування нею.

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

Рисунок 4 – Зв'язок між логічним та фізичним рівнями подання СД.

Будь-яка структура на абстрактному рівні може бути подана у вигляді двійки <D,R>, де D - скінчена множина елементів, які можуть бути типами даних або структурами даних, a R - множина відношень, властивості якої визначають різні типи структур даних на абстрактному рівні.

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: