„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,...
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...
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,...
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...
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...
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...
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ę...
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...
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 ; Dla drugiego iff , w przeciwnym...
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...
Oto streszczenie problemu nauki online / bandyty, nad którym pracowałem latem. Nie widziałem wcześniej takiego problemu i wygląda całkiem interesująco. Jeśli znasz jakieś powiązane prace, byłbym wdzięczny za referencje. Problem Ustawienie dotyczy wielorękich bandytów. Masz N. broni. Każde ramię...
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)...
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...
DFA ma słowo synchronizujące, jeśli istnieje ciąg znaków, który wysyła dowolny stan DFA do jednego stanu. W „The Cerny Conjecture for Aperiodic Automata” AN Trahtmana (Discrete Mathematics and Theoretical Computer Science vol. 9: 2, 2007, s. 3–10) napisał: Cerny przypuszczał w 1964 r., Że każdy...
Poszukuję sposobów na utrzymanie względnie zrównoważonego drzewa opinającego wykresu, gdy dodam do niego nowe węzły / krawędzie. Mam nieukierunkowany wykres, który zaczyna się jako pojedynczy węzeł, „root”. Na każdym kroku dodaję do wykresu albo nowy węzeł i krawędź łączącą go z wykresem, albo...
EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych . UPUP\mathsf{UP}...
Zastanawiałem się, czy specyfikacja JSON definiuje zwykły język. Wydaje się to dość proste, ale nie jestem pewien, jak sam to udowodnić. Powodem, dla którego pytam, jest to, że zastanawiałem się, czy można użyć wyrażeń regularnych, aby skutecznie przetworzyć JSON. Czy ktoś z wystarczającą liczbą...
Czytałem gdzieś, że maszyna Turinga nie może tego obliczyć i dlatego jest nierozstrzygalna, ale dlaczego? Dlaczego komputer nie jest w stanie wygenerować parsowania drzewa i podjąć decyzji? Może się mylę i da się to
Moim ulubionym twierdzeniem w teorii złożoności jest twierdzenie o hierarchii czasu. Dokonano tego jednak w 1965 r. Chciałem wtedy wiedzieć, czy jest coś podobnego do obliczeń kwantowych. Jeśli nie, to jakie osoby / grupy pracują w tym
W teorii informacji kwantowej odległość między dwoma kanałami kwantowymi jest często mierzona za pomocą normy diamentowej. Istnieje również wiele sposobów pomiaru odległości między dwoma stanami kwantowymi, takich jak odległość śladu, wierność itp. Izomorfizm Jamiołkowskiego zapewnia dualność...