Teoretyczne informatyka

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

3
Gdzie mogę uzyskać pomoc w zakresie badań / publikacji?
Od jakiegoś czasu opracowuję algorytm SAT i doszedłem do punktu, w którym chciałbym się nim podzielić. Nie znam wielu ludzi informatyki i nie jestem pewien, dokąd się zwrócić. Zastanawiam się, jakie zasoby są dostępne dla kogoś z algorytmem, który rozważa publikację. Potrzebuję również pomocy w analizie czasu działania i poprawności …
1
Zdecydowanie zrównoważone deterministyczne listy pominięć
W sekcji 2.2 Cache-niepomny B-drzew , stanowczo Weight Balanced wyszukiwania Drzewa są zdefiniowane jako: Dla niektórych stałych , każdy węzeł na wysokości ma potomków .dddvvvhhhΘ(dh)Θ(dh)\Theta(d^h) Oni twierdzą: Drzewa wyszukiwania spełniające właściwości 1 i 2 obejmują zrównoważone pod względem masy drzewa B, deterministyczne listy pominięć i listy pominięć w oczekiwanym znaczeniu. …
5
Algorytmiczna teoria gier - niestandardowe koncepcje równowagi?
Zaczynam studia nad algorytmiczną teorią gier i wydaje się, że zwykle pojęcie równowagi jest oparte na punkcie stałym na wykresie. Jednak czy ludzie przyglądali się alternatywnym koncepcjom równowagi, takim jak cykle graniczne? Mogę sobie wyobrazić, że „ciasny” cykl graniczny - to znaczy cykl na wykresie o bardzo małej długości - …
2
Twardość separatorów wierzchołków
Dla danego wykresu problem separatora pyta, czy istnieje zbiór wierzchołków lub krawędzi o małej liczności (lub wadze), którego usunięcie dzieli G na dwa rozłączne wykresy o w przybliżeniu równych rozmiarach. Nazywa się to problemem separatora wierzchołków, gdy usunięty zestaw jest zestawem wierzchołków, a problemem separatora krawędzi, gdy jest zestawem krawędzi. …
3
Algorytmy randomizowane przy użyciu stosu
Opracowałem nową technikę derandomizacji, która ma na celu rekurencyjne algorytmy randomizowane (lub) bardziej ogólnie algorytmy randomizowane, które wykorzystują stos. Niestety nie mogłem znaleźć naturalnych, losowych algorytmów do zastosowania moich technik. Rekurencyjne łańcuchy Markowa i gramatyki stochastyczne są bardzo zbliżone do tego, czego szukam. Czy istnieją inne (bardziej naturalne) randomizowane algorytmy, …
3
Rozszerzenie problemu stabilnego małżeństwa?
To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54) „Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno stabilne małżeństwo. (Co ciekawe, nie dzieje się tak …
1
Czy ludzie patrzą na zagęszczenie pętli w obwodach boolowskich?
Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz, modulo kilka szczegółów technicznych dotyczących tego, czym jest pętla i co stanowi zagnieżdżoną pętlę, …
2
Czy norma śladowa różnicy między dwiema matrycami gęstości oznacza, że ​​te dwie macierze gęstości można jednocześnie diagonalizować?
Uważam, że odpowiedź na to pytanie jest dobrze znana; ale niestety nie wiem. W obliczeniach kwantowych wiemy, że stany mieszane są reprezentowane przez macierze gęstości. A norma śladowa różnicy dwóch macierzy gęstości charakteryzuje rozróżnialność dwóch odpowiadających stanów mieszanych. Tutaj definicja normy śladowej jest sumą wszystkich wartości własnych macierzy gęstości, z …
3
Jakie algorytmy można wyrazić za pomocą całkowitego języka funkcjonalnego z operatorami równoległych danych?
Wyobraź sobie funkcjonalny język programowania, którego jedynymi typami danych są skalary numeryczne i dowolne zagnieżdżenia tablic. W języku nie ma żadnych możliwości nieograniczonej iteracji, dlatego następujące elementy są niedozwolone: wyraźne pętle (i tak niewiele zużyć bez skutków ubocznych) rekurencja arbitralne funkcje pierwszej klasy (bez kombinatora y) Język ma jednak: funkcje …
1
Gry Ehrenfeucht-Fraïssé (w rzeczywistości Ajtai-Fagin) dla zwykłych języków.
Immerman (Complexity opisowa, 1999) przedstawia gry EF dla egzystencjalnej monadycznej drugiego rzędu (Gry Ajtai-Fagin) na stronie 127. Jak MSO na słowach jest odpowiednikiem zwykłych języków, gra może być napisany w sposób następujący.∃∃\exists Język jest regularny tylko wtedy, gdy Delilah nie ma strategii wygranej w następującej grze: 1. Samson wybiera , …
1
Używasz złożoności Kołmogorowa, aby ustalić dolne granice złożoności dowodu?
Motywacją tego pytania jest fakt, że większość ciągów n-bitowych jest nieściśliwa. Intuicyjnie możemy zaproponować przez analogię, że większość dowodów dla tautologii jest nieściśliwa dla wielkości wielomianowej. Zasadniczo, moja intuicja jest taka, że ​​niektóre dowody są z natury losowe i nie można ich skompresować. Czy istnieje dobre odniesienie do wysiłków badawczych …
1
Obliczanie maks. Zestawów wolnych od H
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że ​​nie indukuje on …
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.