Teoretyczne informatyka

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

2
Co jest specjalnego
W małym algorytmie szyfrowania : Różne wielokrotności stałej magicznej służą do zapobiegania prostym atakom opartym na symetrii rund. Stała magiczna, 2654435769 lub 9E3779B9 16, jest wybrana jako , gdzie ϕ jest złotym współczynnikiem.232/ϕ232/ϕ2^{32}/ \phi Jakie właściwości ma , dzięki czemu jest przydatny w tym kontekście?232/ϕ232/ϕ2^{32}/ \phi
2
Odwołanie do szybkiego algorytmu dla najkrótszych ścieżek wąskich gardeł
Szukam dobrego odniesienia do najkrótszych ścieżek wąskich gardeł. W szczególności, biorąc pod uwagę wierzchołki si na grafie bezkierunkowym z wagami krawędzi, potrzebujesz najkrótszej ścieżki od s do t, gdzie długość ścieżki jest maksymalną krawędzią na tej ścieżce. Można to rozwiązać w czasie O (n + m), znajdując środkową masę krawędzi …
4
Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?
Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co …
2
Najlepszy protokół komunikacyjny dla obcych?
Załóżmy, że odkrywamy obce cywilizacje, które są w stanie wysyłać i odbierać wiadomości za pomocą międzygwiezdnego kanału komunikacji cyfrowej. (Powiedz, używając modulowanych fal radiowych, impulsów laserowych, zmiany położenia gwiazd na różnych orbitach, co masz). Załóżmy, że postanowiliśmy się z nimi skontaktować. Po zainicjowaniu dialogu, jak byśmy przystąpili do ustanowienia protokołu …
3
Trudne problemy NP na kartografach
To pytanie jest podobne do trudnych NP problemów na drzewach : Istnieje duża liczba problemów z NP, które można rozwiązać na kartografach . Czy są jakieś znane problemy, które pozostają NP-kompletne, gdy są ograniczone do kartografów? Mówiąc ściślej, interesują mnie przykłady, w których dane wejściowe składają się wyłącznie z niekierowanego, …
6
Dowód asystent do pisania matematyki
Chciałbym pisać matematyczne dowody przy pomocy asystenta dowodu. Wszystko zostanie napisane przy użyciu logiki pierwszego rzędu (z równością) i naturalnej dedukcji. Tłem jest teoria mnogości (ZF). Na przykład, jak mogę napisać następujący dowód? Aksjomat:∀ x ∀ y( x = y↔ ∀ z( z∈ x ↔ z. Y) )∀x∀y(x=y↔∀z(z∈x↔z∈y))\forall x\forall y(x=y\leftrightarrow\forall …
1
Jaki algorytm kryje się za akinatorem lub 20q?
Tytuł mówi sam za siebie. Oto Akinator i 20Q . Zasadą tych gier jest zadawanie użytkownikowi szeregu pytań związanych z wybraną przez niego jednostką. A następnie dowiedz się, co to za istota. Istotą algorytmu jest znalezienie „najbardziej użytecznego pytania” w każdej rundzie, przy jednoczesnym postępowaniu z użytkownikiem, który może nie …
2
Odwracanie listy przy użyciu dwóch kolejek
To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …
1
Mierzenie losowości wzorów CNF
Powszechnie wiadomo, że formuły CNF można z grubsza podzielić na 2 szerokie klasy: losowe i strukturalne. Strukturalne formuły CNF, w przeciwieństwie do losowych formuł CNF, wykazują pewien porządek, pokazując wzorce, które prawdopodobnie nie wystąpią przypadkowo. Można jednak znaleźć formuły strukturalne wykazujące pewien stopień losowości (tzn. Niektóre określone grupy klauzul wydają …
2
Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar S jest n …
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.