Zawsze istnieje sposób na zastosowanie w tematach związanych z informatyką teoretyczną. Jednak podręczniki i kursy licencjackie zwykle nie wyjaśniają, dlaczego teoria automatów jest ważnym tematem i czy nadal ma zastosowania w praktyce. Dlatego studenci mogą mieć problemy ze zrozumieniem znaczenia teorii automatów i mogą myśleć, że nie ma ona już praktycznego zastosowania.
Czy teoria automatów jest nadal przydatna w praktyce?
Czy powinno to być częścią programu CS na studiach licencjackich?
soft-question
fl.formal-languages
automata-theory
teaching
Mroczny Templariusz
źródło
źródło
Odpowiedzi:
Czy kiedykolwiek używałeś narzędzia takiego jak grep / awk / sed? Wyrażenia regularne stanowią serce tych narzędzi.
Zdziwisz się, ile kodowania możesz uniknąć, stosując wyrażenia regularne oparte na zasadach - w „praktycznych projektach”, takich jak serwer e-mail.
Jeśli jesteś studentem CS-dur, na pewno napiszesz kompilator / tłumacz dla (przynajmniej małego) języka. Jeśli kiedykolwiek próbowałeś tego zadania i utknąłeś, docenisz, jak mała teoria (aka gramatyka bezkontekstowa) może ci pomóc. Ta teoria sprawiła, że kiedyś niemożliwe zadanie stało się czymś, co można zrealizować w ciągu weekendu. (I wygrał wynalazca nagrodę Turinga - Google BNF).
Jeśli jesteś studentem CS, w pewnym momencie musisz usiąść i pomyśleć o filozoficznych podstawach obliczeń, a nie tylko o tym, jak fajna jest kolejna wersja interfejsu API Androida. W związku z tym uniwersytet ma za zadanie nie przygotować cię na następne 5 lat życia, ale przygotować cię na następne 50 lat. Jedyne, co mogą zrobić w tym względzie, to pomóc ci myśleć - myśleć teorii automatów jako jeden z tych kursów.
źródło
Jednym z bardziej praktycznych przejawów CS jest budowa kompilatora. W 1965 roku Knuth rozpoczął badanie parserów LR. Szybko (w mniej niż dekadę) mieliśmy parsery LALR, które są podzbiorem deterministycznych automatów wypychających, które pozwalają nam implementować parsery shift / zmniejsz.
U podstaw wykonalności i wydajności parsowania LALR znajduje się dowód (autorstwa Knutha), że „prefiksy” języka okazują się regularne (twój skończony automat). To jest geneza automatycznych generatorów parserów, takich jak yacc / bison itp.
Można śmiało powiedzieć, że języki programowania, jakie znamy, zawdzięczają dużą część swojej wydajności kompilacji tym zmianom.
Oto inny przykład: sercem protokołu TCP / IP jest skończona maszyna stanu. O ile bardziej praktyczny może to być?
Każdy poważny student CS, szczególnie praktyczny, powinien zwrócić uwagę na teorię automatów. Jest to podstawa dużej części bogactwa informatyki.
źródło
Czy słyszysz ten hałas ? To dźwięk tysiąca genialnych twierdzeń, aplikacji i narzędzi śmiejących się w automatycznym niebie.
Języki i automaty to eleganckie i solidne pojęcia, które można znaleźć w każdej dziedzinie informatyki. Języki nie są suche, formalistyczne przekazy z prehistorii komputerowej. Perspektywa teorii języka rozdziela pozornie skomplikowane pytania o wyrafinowane, nieprzezroczyste obiekty w proste wypowiedzi na temat słów i drzew. Języki formalne odgrywają rolę w informatyce podobną do fundamentalnego i zmieniającego się punktu widzenia, który algebra i topologia wprowadziły do matematyki klasycznej. Oto kilka praktycznych, dość skomplikowanych, praktycznych problemów, które można rozwiązać za pomocą teorii języka.
Powyższa redukcja traktuje języki jako abstrakcyjne obiekty matematyczne. Aby zastosować te pomysły w praktyce, potrzebujemy struktury danych do reprezentowania języków i algorytmów do manipulowania tymi strukturami danych.
Wprowadź automaty. Automaty pozwalają nam zredukować pytania dotyczące abstrakcyjnych obiektów matematycznych, takich jak języki, do konkretnych, algorytmicznych pytań dotyczących graficznych etykiet. Teoria języków i automatów, oprócz szalonej liczby praktycznych zastosowań, zapewnia bardzo znaczącą obsługę intelektualną. Możemy pomyśleć o problemach, od formatowania kodów pocztowych po procedury decyzyjne dla logiki monadycznego drugiego rzędu w jednolitej i uporządkowanej przestrzeni pojęciowej. Jakie to niesamowite!
Nie mówiłem nic o logice i procedurach decyzyjnych. (Tak, mają praktyczne zastosowania). Zobacz autorytatywny przegląd odpowiedzi Kaveha.
źródło
Jak wyjaśniono w innych odpowiedziach, teoria automatów jest ważna koncepcyjnie jako prosty model obliczeniowy, który dobrze rozumiemy, a wyrażenia regularne i automaty mają wiele rzeczywistych zastosowań.
Oto mały przykład współczesnych badań, które sięgają teorii automatów, aby zrozumieć nowoczesną koncepcję. W tym artykule badacze udowadniają, że wszystkie zwykłe języki mają testerów właściwości: „Zwykłe języki można testować przy stałej liczbie zapytań”
źródło
To nie tylko automaty waniliowe. Poznajesz podstawy (akceptowanie stanów, przejścia epsilon, ...) modelu (obliczeniowego), który pomaga w rozumowaniu, co może, a co ważniejsze, czego nie można wyrazić za pomocą niektórych języków zapytań. Kilka interesujących wyników to:
(i oczywiście pomijam wiele innych zajęć)
Zasadniczo jest to bardzo ogólny model. Twoje zajęcia prawdopodobnie podkreślą związek między automatami, językami i logiką.
Gdybym zastanawiał się nad powiązaniem tego z konkretnymi „światowymi” narzędziami, spędziłbym wolny czas w bibliotece, czytając kilka części (AB?) Z Fundacji baz danych autorstwa Abiteboul i in. I próbując połączyć to z powrotem z materiałem klasowym . Oczywiście jest to tylko jeden z (wielu) sposobów poszukiwania aplikacji klasy automatów, i chyba nie jest to najbardziej oczywiste - ale właśnie dlatego jest to interesujące ćwiczenie.
źródło
Jak już wskazano w różnych odpowiedziach, teoria automatów na kursach UG stanowi jedną z podstawowych ram koncepcyjnych do wprowadzania bardziej zaawansowanych (i praktycznych) tematów, a także do wskazywania pomijanych połączeń; na przykład: Diagramy decyzyjne binarne (są zminimalizowane DFA; po nauczeniu DFA często uczę rozwiązywania zagadek opartych na BDD); skrypty, w tym w BioPerl i BioPython (i świetne ustawienie, w którym można wzmocnić liczbę niezamierzonych dopasowań, które mogą być ukryte w regexps skryptu w świecie rzeczywistym), formalne debugowanie (właściwości stanu jako zanegowane FA, przecinają się), a nawet programowanie VCR lub alarmów domowych intruzów (codzienna sytuacja stresowa słabo określonego automatu nauczana na niekompletnych przykładach; być może sformalizowana przy użyciu opartej na scenariuszach syntezy interfejsów użytkownika Harel). Korzystam również z tego ustawienia, aby uczyć Pythona
źródło
Wyrzucę inną odpowiedź z zupełnie innej praktycznej strony: maszyny stanów skończonych (lub przynajmniej niektóre ich proste uogólnienia / rozszerzenia) są często używane po stronie AI programowania. Okazały się doskonałym modelem do enkapsulacji zachowania postaci; na przykład wróg może mieć stany reprezentujące „patrol”, „poszukiwanie”, „podejście”, „atak”, „obronę”, „odwrót”, „śmierć” itp., z dobrze zdefiniowanymi przejściami między nimi. Nie obejmuje to żadnego z formalnych aspektów automatów, takich jak zwykłe języki i tym podobne, ale koncepcja automatu jest bardzo podstawowa.
źródło
- James Mill (pseudonim „PQ”), „Teoria i praktyka”, Londyn i Westminster Review , kwiecień 1836
źródło
Przeprowadzono wiele badań związanych z teorią automatów w sprawdzaniu modeli stosowanych w przemyśle. Sprawdź ostatnie wykłady Moshe Vardi w Fields Institute , w szczególności trzeci wykład „Logika, automaty, gry i algorytmy”, aby dowiedzieć się, dlaczego teoria automatów jest nadal ważna i przydatna.
Slajdy i pliki audio z wykładów są dostępne tutaj: 1 , 2 , 3 .
źródło
Powinniśmy wziąć pod uwagę semantykę słów „praktyczny” i „zastosowanie”. Dla niektórych studentów praktyczne jest wszystko, co pomoże im zdać egzamin; dla innych wszystko, co pojawi się w pracy. W obu przypadkach teoria automatów jest rzeczywiście bardzo praktyczna.
Jak podkreślają inni, będziesz używać gramatyki, na przykład, podczas nauki kompilatorów. Ale nawet więcej: zrozumienie całej koncepcji posiadania różnych stanów i reguł przejścia między nimi może uczynić cię lepszym programistą, gdy zdasz sobie sprawę, na przykład, że twój kod jest tu i tam zbędny, a kiedy go poprawisz, będziesz są stosowania w kodzie same konceptualnych idei tył minimalizacji DFA.
Podobnie w przypadku „aplikacji”. Co rozumiesz przez to słowo? Nawet jeśli jesteś „przyziemnym inżynierem”, zobaczysz i zastosujesz pomysły podobne do teorii Automaty w rzeczywistych projektach: kodowanie kodu, diagramy przepływu, a nawet prosta, ale genialna koncepcja stosu. W przypadku takich frajerów teorii jak ja rozważam zastosowanie teorii automatów w innych obszarach, takich jak logika, algebra i teoria modeli skończonych. Z pewnością prawdopodobnie nigdy nie będę musiał używać lematu pompującego podczas zakupów w supermarkecie, ale takie twierdzenia pomogły mi zrozumieć strukturę niektórych klas języków, nie wspominając już o logice i strukturach algebraicznych, z którymi się korespondują. I to jest coś, co cenię bardziej niż jakakolwiek praktyczność.
źródło
Rzucone razem z logiką automaty mogą oferować sposoby sprawdzania statystyk takich jak
źródło
Automaty skończone, często opisywane jako maszyny skończone w różnych kontekstach lub z ich wariantami probabilistycznymi Ukryte modele Markowa mogą być stosowane do rozpoznawania wzorów i kwantyfikacji struktury wzoru. Na przykład, jakie są najmniejsze stochastyczne automaty skończone, które będą generować łańcuchy mniej więcej zgodnie z danym rozkładem prawdopodobieństwa lub dopasowanie właściwości statystycznych próbki łańcuchów (lub szeregów czasowych) z pewnego rozkładu.
Zobacz na przykład CSSR , algorytm ślepej rekonstrukcji stanów ukrytych; jest bardziej wydajny i elastyczny niż ukryte modele Markowa.
źródło
Kolejnym bardziej praktycznym zastosowaniem teorii automatów jest rozwój sztucznej inteligencji. Sztuczna inteligencja została opracowana na podstawie koncepcji automatu skończonego. Sieć neuronowa robotów jest budowana na podstawie teorii automatów. W końcu wszystkie roboty są również automatami.
źródło
Niektórzy dali świetne odpowiedzi, jeśli chodzi o związek z przemysłem. Co powinno być ważne, to jego wartość naukowa, a teoria automatów jest często bramą do zrozumienia wyższego poziomu teorii obliczeń w studiach licencjackich. Teoria automatów ma wielki zestaw twierdzeń, które pojawiają się wszędzie w Teoretycznej Informatyce, a zwłaszcza gdy chce się mówić o aplikacjach takich jak Kompilatory. Jego wartość naukowa (jak nie jest przestarzała, jak może być? To podstawowa teoria w tej dziedzinie.) Jest praktyczna dla każdego naukowca, który jest zainteresowany obliczeniami. Jest to praktyczne, ponieważ wiedza jest przydatna dla tych, którzy rozumieją lub chcą zrozumieć naturę obliczeń. Jeśli nie możesz znaleźć w nim zastosowania, kwestionuję badania, a nawet zamiar studiowania CS, ponieważ to nie jest programowanie (że „
źródło