Teoretyczne informatyka

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

3
Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)
Odpowiedź: nieznana Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje. Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”. Preferowana jest nowsza wiki, ponieważ jej definicje …
5
Czy istnieje jakakolwiek technika polegająca na wyszukiwaniu absolutnego minimum (maksimum) funkcji w przestrzeni wielowymiarowej?
Znam algorytm spadku gradientu, który może znaleźć lokalne minimum (maksimum) danej funkcji. Czy jest jakaś modyfikacja spadku gradientu, która pozwala znaleźć absolutne minimum (maksimum), gdzie funkcja ma kilka ekstremów lokalnych? Czy istnieją jakieś ogólne techniki, jak ulepszyć algorytm, który może znaleźć ekstremum lokalne, w celu znalezienia ekstremum ekstremalnego?
2
Na
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie 4: wymiarową afinicznej kolektor jest do ekspresji w skończonej związek rozdzielaczy …
6
Jaki jest sens nazywania
Jaka jest różnica nazywania calculus algebrą zamiast rachunku różniczkowego? Podnoszę to pytanie, ponieważ gdzieś przeczytałem wiersz „ λ- rachunek nie jest rachunkiem, ale algebrą” (iirc, przypisane Danie Scott). O co chodzi? Dzięki.λλ\lambdaλλ\lambda
3
Znajdź najkrótszą parą odległość punktów w o (n log n)?
Studenci, których nadzoruję, otrzymali następujące ćwiczenie: Biorąc pod uwagę punktów na płaszczyźnie, opracuj algorytm, który znajdzie parę punktów, których odległość jest minimalna wśród wszystkich par punktów. Algorytm powinien działać w czasie .o ( N 2 )nnno(n2)o(n2)o(n^2) Istnieje (stosunkowo) prosty algorytm dzielenia i zdobywania, który rozwiązuje zadanie w czasie .Θ(nlogn)Θ(nlog⁡n)\Theta(n \log …
1
Decydowalność / algorytm sprawdzania uniwersalności zbioru bramek kwantowych
Biorąc pod uwagę skończony zestaw bram kwantowych , czy jest rozstrzygalne (w sensie teoretycznym obliczeń), czy G jest uniwersalnym zestawem bramek? Z jednej strony „prawie wszystkie” zestawy bram są uniwersalne, z drugiej strony nie-uniwersalne zestawy bram wciąż nie są dobrze zrozumiane (w szczególności oczywiście nie wiadomo, czy każdy nie-uniwersalny zestaw …
5
Jak znaleźć konkretny temat badawczy, na którym można się skoncentrować?
Niedawno rozpocząłem kurs magisterski. W ostatnim semestrze brałem udział w kursach z różnych dyscyplin, takich jak sieci, inżynieria oprogramowania, architektura itp. Ostatnio, po przejściu zaawansowanego kursu w zakresie algorytmów i struktur danych, myślę, że znalazłem kurs, który najbardziej mnie interesuje (w tym inne podobne tematy, takie jak języki programowania itp. …
1
Optymalne przetwarzanie wstępne dla niektórych rodzajów zapytań
Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na zapytania produktów on-line” Alon i Schieber udowadniają, że możemy odpowiedzieć na każde takie zapytanie w co najwyżej krokach (gdzie jest odwrotną funkcją Ackermanna), używając …
3
System typów oparty na naiwnej teorii mnogości
Jak rozumiem, w informatyce typy danych nie są oparte na teorii zbiorów z powodu takich rzeczy jak paradoks Russella, ale tak jak w prawdziwych językach programowania nie możemy wyrazić tak złożonych typów danych jak „zestaw, który nie zawiera siebie”, czy możemy powiedzmy, że w praktyce typ jest nieskończonym zbiorem jego …
3
Obliczanie odległości z przybliżeniem mniejszym niż 2 na ogólnych wykresach?
Biorąc pod uwagę ważony niekierowany wykres z krawędziami m = o ( n2))m=o(n2))m = o(n^2) , chciałbym obliczyć odległości aproksymacji mniejsze niż 2 między dowolną parą wierzchołków. Oczywiście chciałbym użyć przestrzeni subkwadratowej i podliniowego czasu zapytania. Jestem świadomy wyniku Zwicka, który wykorzystuje mnożenie macierzy, ale jestem ciekawy, czy znane są …
3
Wydajne porównanie DAG przez sieć
W rozproszonych systemach kontroli wersji (takich jak Mercurial i Git ) istnieje potrzeba skutecznego porównywania ukierunkowanych wykresów acyklicznych (DAG). Jestem programistą Mercurial i bardzo chcielibyśmy usłyszeć o pracy teoretycznej, która omawia złożoność czasową i sieciową porównywania dwóch DAG. Wspomniane DAG są tworzone na podstawie zarejestrowanych zmian. Wersje są jednoznacznie identyfikowane …
1
Jaka jest złożoność obliczania liczby rozwiązań problemu P-Space Complete? Co powiesz na klasy o wyższej złożoności?
Chyba nazywa się to # P-Space, ale znalazłem tylko jeden artykuł niejasno o tym wspominając. Co powiesz na liczącą się wersję problemów EXP-TIME-Complete, NEXP-Complete oraz EXP-SPACE-Complete? Czy są jakieś wcześniejsze prace, które można przytoczyć w odniesieniu do tego lub dowolnego rodzaju włączenia lub wyłączenia, takiego jak Toda's Torem?
2
Warianty galerii sztuki z widocznością parą?
Problem z tradycyjną galerią sztuki tworzy region i strażników z pewnym pojęciem widoczności i prosi o minimalną liczbę strażników, którzy muszą być umieszczeni, aby zobaczyć cały region. Czy ktoś kiedykolwiek oglądał warianty galerii sztuki, w których obszar widoczności jest definiowany przez parę strażników. Na przykład, jedną z formuł może być …
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.