Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Konstrukcja wykresów, w których każda para wierzchołków ma unikalnego wspólnego sąsiada
Niech będzie prostym wykresem na wierzchołkach bez wierzchołka stopnia . Załóżmy, że dla dowolnych dwóch wierzchołków istnieje unikalny wierzchołek przylegający do nich obu. Jest to ćwiczenie z Kursu kombinatoryki van Linta i Wilsona, aby udowodnić, że taki wykres jest regularny.GGGnnn(n>3)(n>3)(n > 3)n−1n−1n − 1GGG Moje pytanie brzmi jednak, czy w …
4
Parzystość i
Parzystość i są jak nierozłączne bliźniaki. Tak przynajmniej wyglądało przez ostatnie 30 lat. W świetle wyników Ryana wznowione zostanie zainteresowanie małymi klasami.AC0AC0AC^0 Furst Saxe Sipser do Yao do Hastad są ograniczeniami parzystości i losowymi. Razborov / Smolensky jest przybliżonym wielomianem z parzystością (ok, mod bramki). Aspnes i wsp. Stosują słaby …
1
Wizualizacja unikalnych gier
Jak zaprojektowałbyś zdjęcie ilustrujące unikalną hipotezę gier? Jest to prezentacja „bieżących wydarzeń” na temat unikalnych gier podczas następnego wspólnego spotkania AMS oraz broszura, która zostanie wydana. Przykłady tego rodzaju ilustracji wykonanych w przeszłości znajdują się na http://www.ams.org/meetings/lectures/current-events-bulletin a jeśli klikniesz na wydanie z 2006 roku, zobaczysz zdjęcie, którego Madhu Sudan …
1
Jakie są najlepsze możliwe kompromisy czas / błąd dla przybliżonego rozwiązania programów liniowych?
Dla konkretności rozważ LP za rozwiązanie gry dla dwóch graczy o sumie zerowej, w której każdy gracz ma akcji. Załóżmy, że każdy zapis macierzy wypłat ma najwyżej 1 wartość bezwzględną. Dla uproszczenia nie róbmy żadnych założeń sparity.nnnZAZAA Załóżmy, że środowisko wykonawcze jest dostępne w celu przybliżenia wartości tej gry.T.T.T Jedną …
2
Algorytm dla „k” najczęściej występujących liczb
Szukałem najbardziej wydajnego algorytmu (streaming?), Który mówi mi „k” najczęściej występujące elementy w strumieniu danych w dowolnym momencie. Ten post: Algorytmy strumienia danych „Dziel i rządź” zainteresowały mnie. Załóżmy na przykład, że istnieją liczby: (4,3,5,1,6,2,4,3,3,8,8,9,1) i szukam 3 najczęściej występujących liczb (powiedzmy), to powinienem otrzymaj (3,4,1) jako odpowiedź. Próbowałem szukać …
1
Wybór tematu badań z wykorzystaniem teorii gier
Ta ostatnia teoria gier pytanie dało mi do myślenia (to jest styczna, oczywiście): Czy jest możliwe, aby skutecznie zoptymalizować osobistą strategię wyboru pytania badawcze do pracy na wykorzystaniu teorii gier? Aby przejść do sformalizowania pytania, przyjmuję następujące (nieformalnie) założenia: Równie „lubię” każdy konkretny problem dostępny dla mnie do pracy (aby …
4
Gdzie większość implementacji REGEX przypada na skalę złożoności?
Większość współczesnych implementacji wyrażeń regularnych, takich jak Perl lub .NET, wykracza poza klasyczną informatyczną definicję REGEX z funkcjami takimi jak lookahead i lookbehind. Czy te funkcje umożliwiają analizowanie instrukcji, których nie można opisać za pomocą skończonego automatu bez odpychania? Jak bardzo zbliża się do ukończenia Turinga, jeśli to możliwe?
5
(Fałsz?) Dowód na obliczalność funkcji?
Rozważmy , funkcja, która zwraca 1 i zer pojawiających się kolejno w . Teraz ktoś dał mi dowód, że jest obliczalny:n π f ( n )fa( n )f(n)f(n)nnnππ\pifa( n )f(n)f(n) Albo dla wszystkich n, pojawia się w , lub jest st pojawia się w a nie. Dla pierwszej możliwości ; …
2
Żal wewnętrzny w Online Convex Optimization
„Optymalizacja wypukła” Zinkevicha ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) uogólnia algorytmy uczenia się „minimalizacji żalu” od ustawień liniowych do wypukłych i daje dobre „zewnętrzne pożałowanie” . Czy istnieje podobne uogólnienie wewnętrznego żalu? (Nie jestem do końca pewien, co to właściwie znaczy.)
3
Jakie algorytmy są znane z obliczania interpolantów Craiga?
Czy istnieje przegląd algorytmów obliczania interpolantów? Co z artykułami na temat tylko jednego algorytmu? Najbardziej interesuje mnie przypadek i C = q plus ograniczenie, że interpolant jest tak mały, jak to możliwe. (Znam pracę McMillana z 2005 roku , która opisuje, jak uzyskać interpolanty, unikając kwantyfikatorów.)A=¬p∧qA=¬p∧qA=\lnot p\land qC=qC=qC=q Tło: Interpolacja …
4
Jak leczy się skutki uboczne w semantyce?
W sekcji „Wprowadzenie do języków programowania” Anthony'ego Aaby'ego na temat semantyki dokonuje następujących obserwacji: Znaczna część pracy w semantyce języków programowania jest motywowana problemami napotkanymi przy próbie konstruowania i zrozumienia programów imperatywnych - programów z poleceniami przypisania. Ponieważ polecenie przypisania ponownie przypisuje wartości do zmiennych, przypisanie może mieć nieoczekiwane skutki …
22
Jakie algorytmy są najczęściej stosowane w praktyce?
Zablokowana . To pytanie i odpowiedzi są zablokowane, ponieważ pytanie jest nie na temat, ale ma znaczenie historyczne. Obecnie nie akceptuje nowych odpowiedzi ani interakcji. Które algorytmy są najczęściej używane? Napisz jeden algorytm na odpowiedź, staraj się, aby twoja odpowiedź była krótka (jedna lub dwie linie).
2
Czy istnieje niedeterministyczny algorytm liniowego czasu dla CNF-SAT?
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema taśmami . Uważam, że istnieje NTM, który rozwiązuje CNF-SAT etapami n⋅poly(log(n))n⋅poli(log⁡(n))n \cdot \texttt{poly}(\log(n)) …
2
Intuicyjny / nieformalny dowód na LP Duality?
Jaki byłby dobry nieformalny / intuicyjny dowód na „trafienie w sedno” na temat dualności LP? Jak najlepiej wykazać, że zminimalizowana funkcja celu jest rzeczywiście minimalna, z intuicyjnym sposobem rozumienia granicy? Sposób, w jaki mnie uczono, doprowadził do tego, że DUŻO ludzi, które znam, podziela jedno zrozumienie: jestem pewien, że dla …
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.