Obliczalność

Pojęcia informatyki

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Czym jest obliczalność?

Problem obliczalny

  • Istnienie algorytmu: Istnieje jasna procedura.
  • Skończony czas: Wynik uzyskiwany w ograniczonej liczbie kroków.

Problem nieobliczalny

  • Brak algorytmu: Nie można rozwiązać dla wszystkich możliwych danych wejściowych.
  • Nieskończone obliczenia: Może nigdy nie osiągnąć wyniku.
1 Problemy nieobliczalne mogą stać się obliczalne po znalezieniu algorytmu i/lub zapewnieniu jego zakończenia w skończonym czasie.
Pojęcia informatyki

Automat

Definicja automatu

  • Wyobrażone maszyny
  • Pomagają zrozumieć działanie obliczeń
  • Posiada stany
  • Posiada reguły przejść między stanami

Obraz sygnalizacji świetlnej jako analogia reprezentująca automat

Pojęcia informatyki

Automat skończony (FA)

Automat skończony (FA)

  • Proste maszyny
  • Stała liczba stanów
  • Brak pamięci poza bieżącym stanem

Obraz sygnalizacji świetlnej i stanów jako analogia do automatu skończonego

Pojęcia informatyki

Automat ze stosem (PDA)

Automat ze stosem (PDA)

  • Większa moc obliczeniowa
  • Posiada stany
  • Pamięć stosowa umożliwia złożone decyzje

Obraz sygnalizacji świetlnej i stanów jako analogia do automatu ze stosem

Pojęcia informatyki

Podsumowanie

Automat skończony (FA)

  • Przydatny do prostych zadań

Automat ze stosem (PDA)

  • Większa moc dla złożonych problemów

Znaczenie

  • Jeśli problem można modelować automatem, MOŻLIWE jest zaimplementowanie algorytmu rozwiązania
Pojęcia informatyki

Czas na ćwiczenia!

Pojęcia informatyki

Preparing Video For Download...