Обчислюваність

Концепції комп'ютерних наук

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Що таке обчислюваність?

Обчислювана задача

  • Існує алгоритм: є чітка процедура.
  • Скінченний час: дає результат за обмежену кількість кроків.

Необчислювана задача

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

Автомати

Визначення автоматів

  • Уявні машини
  • Допомагають зрозуміти, як працюють обчислення
  • Мають стани
  • Мають правила переходу між станами

Зображення світлофора як аналогії автоматів

Концепції комп'ютерних наук

Скінченні автомати (FA)

Скінченні автомати (FA)

  • Прості машини
  • Фіксована кількість станів
  • Немає пам'яті поза поточним станом

Зображення світлофора і станів як аналогії скінченних автоматів

Концепції комп'ютерних наук

Автомати зі стеком (PDA)

Автомати зі стеком (PDA)

  • Потужніші
  • Мають стани
  • Мають пам'ять на основі стеку для складніших рішень

Зображення світлофора і станів як аналогії автоматів зі стеком

Концепції комп'ютерних наук

Підсумок

Скінченні автомати (FA)

  • Корисні для простих завдань

Автомати зі стеком (PDA)

  • Потужніші для складніших проблем

Важливість

  • Якщо задачу можна змоделювати автоматом, ми МОЖЕМО реалізувати алгоритм для її розв'язання
Концепції комп'ютерних наук

Давайте потренуємось!

Концепції комп'ютерних наук

Preparing Video For Download...