Informatyka

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

1
Analiza składni z przesunięciem - pytania
Ostatnio natknąłem się na artykuł opisujący technikę parsowania wspomnianą w tytule. Niestety terminologia zastosowana we wspomnianym artykule jest nieco poza moim zrozumieniem, więc starałem się zrozumieć algorytm konstrukcji bardziej intuicyjnie. Wierzę, że mi się udało ( ta prezentacja była źródłem momentu ah-ha), ale doceniona zostanie weryfikacja poprawności przez kogoś, kto …
1
Ekstrakt sterty binarnej funkcji potencjalnej max O (1)
Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody.O ( 1 )O(1)O(1) Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt wydobycia, i musi to dotyczyć wysokości stosu (jeśli podaje wysokość stosu, …
1
Maksymalizacja funkcji wypukłej z wiązaniem liniowym
maximize f(x)subject to Ax=bmaximize f(x)subject to Ax=b\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b} gdzie f(x)=∑i=1N1+x4i(∑Ni=1x2i)2−−−−−−−−−−−−−⎷,f(x)=∑i=1N1+xi4(∑i=1Nxi2)2,f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}}, x=[x1,x2,...,xN]T∈RN×1x=[x1,x2,...,xN]T∈RN×1\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1} i .A∈RM×NA∈RM×N\mathbf{A} \in \mathbb{R}^{M\times N} Widzimy, że jest wypukły i ma postać . Można również wykazać, że jest ograniczone w . Wiem, że problem maksymalizacji …
3
Rozważalne języki i nieograniczone gramatyki?
Maszyny Turinga i nieograniczona gramatyka to dwa różne formalizacje, które definiują języki RE. Niektóre języki RE są rozstrzygalne, ale nie wszystkie są. Możemy zdefiniować rozstrzygalne języki za pomocą maszyn Turinga, mówiąc, że dany język jest rozstrzygalny, jeśli istnieje TM dla języka, który zatrzymuje i akceptuje wszystkie ciągi w języku oraz …
3
anonimowe funkcje lambda (programowanie funkcjonalne)
Co to są funkcje anonimowe (lambda)? Jaka jest formalna definicja anonimowej funkcji w funkcjonalnym języku programowania? Mówiąc najprościej, kiedy programuję w schemacie / lisp, powiedziałbym, że funkcja anonimowa (lambda) jest funkcją niezwiązaną z identyfikatorem. Czy to wszystko, co możesz formalnie powiedzieć o funkcji lambda? Myślę, że do tej prostej definicji …
2
Teoretyczna minimalna liczba rejestrów dla nowoczesnego komputera?
Podczas studiów licencjackich wziąłem kurs na kompilatory, w którym napisaliśmy kompilator, który kompiluje programy źródłowe w zabawnym języku podobnym do języka Java z językiem montażu zabawek (dla którego mieliśmy tłumacza). W projekcie przyjęliśmy pewne założenia dotyczące maszyny docelowej ściśle związane z „prawdziwymi” natywnymi plikami wykonywalnymi, w tym: stos czasu wykonywania, …
4
Znalezienie rozmiaru najmniejszego podzbioru z GCD = 1
Jest to problem z sesji treningowej Polskiego Konkursu Programowania Uczelnianego 2012 . Chociaż mogłem znaleźć rozwiązania dla głównego konkursu, nie mogę nigdzie znaleźć rozwiązania tego problemu. Problem polega na tym: biorąc pod uwagę zbiór NNN wyraźnych liczb całkowitych dodatnich nie większych niż , znajdź rozmiar najmniejszego podzbioru, który nie ma …
7
Gdzie znaleźć opublikowane prace badawcze?
Pochodzi z POV kogoś, kto myśli o zdobyciu tytułu doktora informatyki. Mam problem z podjęciem decyzji, na czym skoncentruję swoje badania, kiedy doktoryzuję się. Zobacz także to pytanie na stronie academia.SE . Myślę więc, że czytanie / bieżące śledzenie prowadzonych badań i publikowanych prac badawczych jest dobrym źródłem… inspiracji? Plus …
1
Intuicja stojąca za relatywizacją
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka kolejnych zdań to pytania, a moje przemyślenia …
3
Dowód, że jeżeli
Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje. Jeżeli N T i m e ( n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000}) , a następnie P=NPP=NP\mathrm{P}=\mathrm{NP} . Tutaj NTime(n100)NTime(n100)\mathrm{NTime}(n^{100}) jest klasą wszystkich języków, o których decyduje niedeterministyczna maszyna Turinga w czasie wielomianowym i jest klasą wszystkich języków, o których decyduje deterministyczna maszyna Turinga w …
1
Problem przydziału na wiele dni
Mam problem, który można sprowadzić do problemu przydziału. (W poprzednim pytaniu dowiedziałem się, jak to zrobić.) Co oznacza, że ​​mamy zestaw ZAZAA agentów i zestaw zadań, a także funkcję kosztu . Musimy znaleźć zadanie, aby całkowity koszt był minimalny.c ( i , j )T.T.Tc ( i , j )do(ja,jot)c(i,j) Algorytm …
1
Unifikacja vs. solver SAT
Czytałem na Wikipedii, że zjednoczenie jest procesem rozwiązywania problemu satysfakcji. Jednocześnie wiem, że takie solwery nazywane są „solverami SAT” lub „solverami SMT”. Czy są to różne nazwy dla tej samej rzeczy? Jeśli powiesz, że się różnią, proszę wskazać wadę mojego leczenia.
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.