Informatyka

to jest fragment kodu asemblera section .text global _start ;must be declared for using gcc _start: ;tell linker entry point mov edx, len ;message length mov ecx, msg ;message to write mov ebx, 1 ;file descriptor (stdout) mov eax, 4 ;system call number (sys_write) int 0x80 ;call kernel mov...

Załóżmy, że . to klasa problemów w które nie są ani w ani w -hard. Listę problemów, które mogą być tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że jeśli wówczas istnieje nieskończona...

Czy istnieje jakiś „naturalny” język, który jest nierozstrzygalny? przez „naturalny” rozumiem język zdefiniowany bezpośrednio przez właściwości ciągów, a nie przez maszyny i ich odpowiedniki. Innymi słowy, jeśli język wygląda jak gdzie to TM, DFA (lub regularny exp), PDA (lub gramatyka) itp., To...

Wiele komplikuje się w kompilatorach JIT dla języków takich jak Java, Ruby i Python. Czym różnią się kompilatory JIT od kompilatorów C / C ++ i dlaczego kompilatory napisane dla Java, Ruby lub Python nazywane są kompilatorami JIT, podczas gdy kompilatory C / C ++ to tylko...

W poprzednim pytaniu była definicja drzew zrównoważonych pod względem masy i pytanie dotyczące drzew czerwono-czarnych. To pytanie dotyczy tego samego pytania, ale dotyczy drzew AVL . Pytanie brzmi, biorąc pod uwagę definicję drzew zrównoważonych jak w drugim pytaniu,μμ\mu Czy jest jakieś...

Rozumiem teorię leżącą u podstaw sieci bayesowskich i zastanawiam się, co trzeba zbudować w praktyce. Powiedzmy na przykład, że mam sieć bayesowską (ukierunkowaną) 100 dyskretnych zmiennych losowych; każda zmienna może przyjąć jedną z maksymalnie 10 wartości. Czy przechowuję wszystkie węzły w DAG...

To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . Szukam teorii matematycznych, które zajmują się opisywaniem języków formalnych (zestawu ciągów) w...

Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G ′G = ( V, E)G=(V,E)G=(V,E)sol′= ( V, E′)G′=(V,E′)G'=(V, E')miEEmi′E′E'Θ ( | V|...

Biorąc pod uwagę bezkontekstową gramatykę G, istnieje niedeterministyczny automat pushdown N, który akceptuje dokładnie język, który akceptuje G. (i odwrotnie) Nie może również istnieć deterministyczny automat ze stosem D, który akceptuje dokładnie język G akceptuje też. To zależy od...

Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica. Zastanawiam się jednak, które algorytmy...

Maszyna Turinga, która powróci do wcześniej napotkanego stanu z głowicą do odczytu / zapisu w tej samej komórce dokładnie tej samej taśmy, zostanie przechwycona w pętli. Taka maszyna się nie zatrzymuje. Czy ktoś może podać przykład ciągłej maszyny, która się nie...

Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich...

Czytając Uday Reddy za odpowiedź na Jaka jest relacja między funktorów w SML i teorii kategorii? Stwierdza Uday Teoria kategorii nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu. Pewnego dnia to zrobi. Ponieważ myślałem, że teoria kategorii może służyć jako podstawa matematyki,...

Programowanie funkcjonalne wykorzystuje trwałe struktury danych i niezmienne obiekty. Moje pytanie brzmi: dlaczego tak ważne jest posiadanie takich struktur danych? Chcę na niskim poziomie zrozumieć, co by się stało, gdyby struktura danych nie była trwała? Czy program często się...

Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że

Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie...

Chcę zmienić problem matematyczny, który mam, w logiczny problem satysfakcji (SAT), a następnie rozwiązać go za pomocą SAT Solvera. Zastanawiam się, czy ktoś zna instrukcję, przewodnik lub cokolwiek, co pomoże mi przekonwertować mój problem na instancję SAT. Chcę też rozwiązać ten problem w czasie...

Przy projektowaniu algorytmów często stosuje się następujące techniki: Programowanie dynamiczne Chciwa strategia Dziel i rządź Podczas gdy w przypadku dwóch pierwszych metod istnieją dobrze znane podstawy teoretyczne, a mianowicie zasada optymalności Bellmana i teoria matroidów (odpowiednio...

To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 5 lat temu . Wciąż uczę się programowania funkcjonalnego (z f #) i ostatnio zacząłem czytać o wyrażeniach obliczeniowych. Nadal nie...

Chciałbym rozpocząć pytanie od stwierdzenia, że ​​jestem programistą i nie mam dużego doświadczenia w teorii złożoności. Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do...