Teoretyczne informatyka

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

2
Jak / dlaczego systemy liniowe są tak ważne dla informatyki?
Zainteresowałem się optymalizacją matematyczną całkiem niedawno i bardzo mi się podoba. Wydaje się, że wiele problemów związanych z optymalizacją można łatwo wyrazić i rozwiązać jako programy liniowe (np. Przepływy sieciowe, pokrycie krawędzi / wierzchołków, podróżujący sprzedawca itp.) Wiem, że niektóre z nich są trudne do NP, ale chodzi o to, …
1
Połączenie między PCP a L = SL
Książka Arory i Baraka zawiera uwagi do rozdziału na temat PCP Zauważamy, że ogólna strategia Dinura przypomina nieco zygzakowatą konstrukcję wykresów ekspanderów i deterministyczny algorytm przestrzeni logicznej Reingolda dla połączeń bezkierunkowych opisany w rozdziale 20, co sugeruje, że więcej połączeń oczekuje na nawiązanie między tymi różnymi obszarami badań. (str. 494) …
2
Odgadywanie niskiej wartości entropii przy wielu próbach
Załóżmy, że Alice ma rozkład μμ\mu w skończonej (ale być może bardzo dużej) domenie, takiej jak entropia (Shannon) μμ\mu jest górny ograniczony dowolnie małą stałą εε\varepsilon. Alice rysuje wartośćxxx od μμ\mu, a następnie pyta Boba (kto wie μμ\mu) zgadywać xxx. Jakie jest prawdopodobieństwo sukcesu dla Boba? Jeśli można mu tylko …
1
Jakie są możliwe implementacje klas typów Haskell i jakie są ich (nie) zalety?
O ile mi wiadomo, funkcja Haskella z ograniczeniami klas typów jest wewnętrznie kompilowana do funkcji z dodatkowymi argumentami, które otrzymują słowniki z niezbędnymi implementacjami poszczególnych klas typów. Czy istnieją inne możliwości kompilowania klas typów? Jeśli tak, jakie są ich (nie) zalety? A jakie kompilatory ich używają?
1
Jaka jest oczekiwana długość najkrótszej ścieżki hamiltonowskiej w losowo wybranych punktach z siatki planarnej?
kkk różnych punktów wybiera się losowo z siatki . (Oczywiście i jest daną stałą liczbą.) Na podstawie tych punktów budowany jest kompletny wykres ważony, tak że ciężar krawędzi między wierzchołkiem a wierzchołkiem jest równy odległości Manhattanu dwóch wierzchołków na pierwotnej siatce .p × qp×qp\times qk ≤ p × qk≤p×qk\leq p\times …
2
Proste zamykania dla typów indukcyjnych ze spacjami funkcyjnymi
Funkcje zbudowane z produktów i sum skończonych mają porządek zamknięcia ωω\omega, ładnie wyszczególnione w tym manuskrypcie Francoisa Metayera. tzn. możemy osiągnąć typ indukcyjnynat:=μX.1+Xnat:=μX.1+Xnat := \mu X. 1 + X przez iterację funktora 1+X1+X1 + X, który osiąga swój stały punkt po ωω\omega iteracje. Ale kiedy pozwolimy na stałe potęgowanie, takie …
1
Entropia głośnego rozkładu
Powiedzmy, że mamy funkcję f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R}takie, że a jest rozkładem, tzn. .∀x∈Zn2f(x)∈{12n,22n,…,2n2n},∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},fff∑x∈Zn2f(x)=1∑x∈Z2nf(x)=1\sum_{x\in \mathbb{Z}_2^n} f(x) = 1 Entropia Shannona dla jest zdefiniowana następująco: fffH(f)=−∑x∈Zn2f(x)log(f(x)).H(f)=−∑x∈Z2nf(x)log⁡(f(x)).H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) . Niech będzie niezmienny. Powiedzmy, że …
2
Problem ODD NAWET DELTA
Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA polega na obliczeniu , biorąc pod uwagę G i k .G = ( …
1
FO-uniform AC0 z pewnym orzeczeniem
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)FO(R) będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”. Chciałbym wiedzieć, czy jest jakakolwiek caracterization FO(&lt;,R)FO(&lt;,R)FO(<,R) z R dowolnym orzeczeniem NrNr\mathbb N^rdla jakiegoś r? Na przykład …
3
Przesyłanie pracy innych osób do arXiv
To delikatne pytanie mające na celu ustalenie, co ludzie uważają za najlepszą praktykę zawodową w zakresie nieoryginalnej pracy nad arXiv. Istnieje szkic artykułu [1] autorstwa Roberta Szelepcsényiego, opublikowanego w jego przestrzeni internetowej na Uniwersytecie w Chicago, najwyraźniej napisany ponad dziesięć lat temu podczas studiów podyplomowych. Praca wydaje się poprawna, modulo …
1
Jaki jest najgorszy przypadek losowego algorytmu triangulacji przyrostowej delauny?
Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale jak dotąd nie udało się.O(nlogn)O(nlog⁡n)\mathcal O(n \log n)Ω(n2)Ω(n2)\Omega(n^2) Jeden z tych prób było …
2
Zdarzenia o wysokim prawdopodobieństwie bez współrzędnych o niskim prawdopodobieństwie
Pozwolić XXX być zmienną losową przyjmującą wartości w ΣnΣn\Sigma^n (dla jakiegoś dużego alfabetu ΣΣ\Sigma), który ma bardzo wysoką entropię - powiedzmy, H(X)≥(n−δ)⋅log|Σ|H(X)≥(n−δ)⋅log⁡|Σ|H(X) \ge (n- \delta)\cdot\log|\Sigma| dla arbitralnie małej stałej δδ\delta. PozwolićE⊆Supp(X)E⊆Supp(X)E \subseteq \rm{Supp}(X) być wydarzeniem wspierającym XXX takie, że Pr[X∈E]≥1−εPr[X∈E]≥1−ε\Pr[X \in E] \ge 1 - \varepsilon, gdzie εε\varepsilon jest dowolnie …
1
Algorytm aproksymacji wypukłych ciał przez wypukły kadłub elipsoid
Pracuję w dziedzinie inżynierii budowlanej i chciałbym znaleźć skuteczny algorytm do konstruowania aproksymacji (w metodzie Hausdorffa) ciała wypukłego K.K.K przez wypukły kadłub nnn elipsoidy, dla niektórych naprawione nnn. Obecnie pracuję tylko w wymiarach 2 i 3. Moim pierwszym pomysłem była praca w podwójnej przestrzeni za pomocą funkcji wsparcia hK.hK.h_K z …
1
Czy istnieje odpowiedni algorytm do rysowania mieszanego wykresu okręgu / zależności w układzie współrzędnych?
Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne). Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to pytanie nie koliduje np. Z wymaganiami dotyczącymi tej …
1
Nauka z (podpisanymi) błędami
Background––––––––––––––Background_\underline{\bf Background} W 2005 r. Regev [1] wprowadził problem uczenia się z błędami (LWE), uogólnienie problemu parzystości uczenia się z błędem. Założenie o twardości tego problemu dla niektórych wyborów parametrów leży obecnie u podstaw dowodów bezpieczeństwa dla wielu kryptosystemów post kwantowych w dziedzinie kryptografii opartej na sieci. „Kanoniczne” wersje LWE …
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.