Pytania otagowane jako reference-question

Zarezerwowane - nie powinno być używane w przypadku większości nowych pytań. Pytania o szerokim zakresie dotyczące ogólnych metod i pojęć, takich jak metody sprawdzające, narzędzia do analizy algorytmów czy podstawy architektury komputera. Nie dotyczy to pytań o referencje, np. Książki lub artykuły.

3
Czy istnieje magia analizy algorytmów?
Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się być dostosowana do indywidualnych potrzeb. Z drugiej strony odpowiedzi na …
4
Jak przekonwertować skończone automaty na wyrażenia regularne?
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub …
11
Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb
W informatyce często musimy rozwiązywać relacje powtarzalności , to znaczy znaleźć zamkniętą formę dla rekurencyjnie zdefiniowanej sekwencji liczb. Rozważając środowiska wykonawcze, często jesteśmy zainteresowani głównie asymptotycznym wzrostem sekwencji . Przykładami są Czas działania funkcji rekurencyjnej ogona schodzącej w dół do 000 od nnn którego ciało wymaga czasu f(n)f(n)f(n) : T(0)T(n+1)=0=T(n)+f(n)T(0)=0T(n+1)=T(n)+f(n)\qquad …
5
Jak udowodnić, że język nie jest pozbawiony kontekstu?
Dowiedzieliśmy się o klasie języków bezkontekstowych . Charakteryzuje się zarówno gramatykami bezkontekstowymi, jak i automatami pushdown, dzięki czemu łatwo jest pokazać, że dany język jest pozbawiony kontekstu.CFLCFL\mathrm{CFL} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich gramatyk (lub automatów), że nie potrafią …
10
Jak udowodnić, że język nie jest regularny?
Dowiedzieliśmy się o klasie języków zwykłych . Charakteryzuje go dowolna koncepcja wśród wyrażeń regularnych, automatów skończonych i gramatyk lewostronnych, więc łatwo jest wykazać, że dany język jest regularny.REGREG\mathrm{REG} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich wyrażeń regularnych (lub dla wszystkich …
8
Jak udowodnić, że język jest regularny?
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L ′LLLL′L′L' L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}\qquad \displaystyle …
4
Jakie są typowe techniki wzajemnego ograniczania problemów?
W teorii obliczalności i złożoności (i być może w innych dziedzinach) redukcje są wszechobecne. Istnieje wiele rodzajów, ale zasada pozostaje ta sama: pokaż, że jeden problem jest co najmniej tak samo trudny jak jakiś inny problem poprzez odwzorowanie instancji z na równoważne z rozwiązaniem w . Zasadniczo pokazujemy, że każdy …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.