Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Czy mogą istnieć „martwe stany” w gramatyce bezkontekstowej?
Czy gramatyka bezkontekstowa może zawierać „martwe stany” z automatu, np G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? B→CB→CB\to CC→cCC→cCC\to cC will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at …
1
Wyrażenia regularne z odniesieniami wstecznymi do jednoznacznego alfabetu
Oprawa: wyrażenia regularne z referencjami wstecznymi język jednoargumentowy (alfabet 1-symbolowy) Czy w tym ustawieniu można rozstrzygać następujący problem: Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język? Na przykład (aa+)\1definiuje zwykły język, podczas gdy (aa+)\1+nie. Czy możemy zdecydować, który jest właściwy? Dla konkretności, „wyrażenia regularne z …
3
Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?
Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.) Nie mogę znaleźć algorytmów aproksymacyjnych dla takich problemów. Szukałem w szczególności SAT i na stronie …
7
Rachunek lambda nie wydawał się abstrakcyjny. I nie widzę sensu
Podstawowe pytanie: Co robi dla nas rachunek lambda , czego nie możemy zrobić z podstawowymi właściwościami funkcji i notacją ogólnie przyswojoną w algebrze gimnazjalnej? Przede wszystkim, co oznacza streszczenie w kontekście rachunku lambda? Moje rozumienie słowa abstrakcja jest czymś oddzielonym od maszynerii, konceptualnym streszczeniem pojęcia. Jednak funkcje lambda, usuwając nazwy …
2
„Minimalna” intuicyjna teoria typów?
Dziwi mnie, że ludzie ciągle dodają nowe typy do teorii typów, ale wydaje się, że nikt nie wspomina o teorii minimalnej (lub nie mogę jej znaleźć). Myślałem, że matematyk uwielbia minimalne rzeczy, prawda? Jeśli dobrze rozumiem, w teorii typów z impredykatywnym wystarczy Propλ-abstrakcja i Π-typy. Mówiąc wystarczająco, mam na myśli, …
2
W jakim sensie zestaw Mandelbrota jest „obliczalny”?
Zestaw Mandelbrota to piękne stworzenie w matematyce. Istnieje wiele pięknych obrazów tego zestawu stworzonych z dużą precyzją, więc oczywiście ten zestaw jest w pewnym sensie „obliczalny”. Jednak niepokoi mnie fakt, że nie można go nawet wyliczyć rekurencyjnie - po prostu dlatego, że zbiór jest niepoliczalny. Można to rozwiązać, wymagając pewnego …
7
Czy komputer bez pamięci RAM, ale z dyskiem, odpowiada komputerowi z pamięcią RAM?
Jak rozumiem, pamięć jest wykorzystywana do wielu rzeczy. Służy jako pamięć podręczna dysku i zawiera instrukcje programów oraz ich stos i stos. Oto eksperyment myślowy. Jeśli ktoś nie dba o szybkość lub czas, jaki zajmuje komputerowi wykonanie chrupnięcia, jaka jest minimalna ilość pamięci, jaką można mieć, zakładając, że ma on …
4
Czy „Eugene Goostman” naprawdę zdał test Turinga?
Mówi się, że „Eugene Goostman”, program komputerowy opracowany w celu symulacji 13-letniego chłopca, zdołał przekonać 33% sędziów, że był człowiekiem, i tym samym zdał Test Turinga. Program komputerowy, znany również jako chatbot, udawał 13-letniego ukraińskiego chłopca, dla którego angielski był drugim językiem - coś zupełnie innego. Dla mnie Eugene brzmi …
4
Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania
Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być O ( n2))O(n2)O(n^2) , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych …
2
Wydajne algorytmy dla problemu widoczności pionowej
Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie: Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku nnn którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również mmm segmenty poziome. Każdy segment ma całkowitą współrzędną yyy ( 0≤y≤n0≤y≤n0 \le …
4
Zdefiniowanie problemu zatrzymania dla niedeterministycznych automatów
Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna. Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych rodzajów automatów. Zauważyłem również, że determinizm jest często mniej lub bardziej dorozumiany w …
4
Symuluj uczciwą kość z tendencyjną
Biorąc pod uwagę stronniczą stronną matrycę, w jaki sposób można losowo wygenerować liczbę losową z zakresu ? Rozkład prawdopodobieństwa powierzchni matryc nie jest znany, wiadomo tylko, że każda powierzchnia ma niezerowe prawdopodobieństwo i że rozkład prawdopodobieństwa jest taki sam dla wszystkich rzutów (w szczególności rzuty są niezależne). Jest to oczywiste …
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.