Teoretyczne informatyka

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

1
Struktury danych w języku programowania z typami liniowymi
Załóżmy, że mamy do czynienia z językiem programowania obsługującym typy liniowe (terminy typu liniowego mogą być użyte najwyżej raz, że tak powiem). Pozwala to na traktowanie niektórych efektów obliczeniowych (takich jak mutacja, a nawet zmiana rodzaju operandu) w sposób problematyczny dla języków, których systemy typów działają tylko na „wiecznych prawdach”. …
1
Stałe twierdzenia punktowe dla konstruktywnych przestrzeni metrycznych?
Twierdzenie Banacha o punkcie stałym mówi, że jeśli mamy niepustą pełną przestrzeń metryczną AZAA , wówczas każda jednorodnie kurcząca się funkcja ma unikalny punkt stały . Jednak dowód tego twierdzenia wymaga aksjomatu wyboru - musimy wybrać dowolny element aby rozpocząć iterację , aby uzyskać sekwencję Cauchyego . μ ( f …
3
Teorie charakteryzujące klasy złożoności obliczeniowej
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że …
3
Wyprzedaż Boba (zmiana kolejności par z ograniczeniami w celu zminimalizowania sumy produktów)
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto również przyjrzeć …
2
Minimalna liczba transpozycji do sortowania listy
Próbując opracować własny algorytm sortowania, szukam optymalnego testu porównawczego, z którym mogę go porównać. W przypadku nieposortowanego uporządkowania elementów A i posortowanego uporządkowania B , jaki jest skuteczny sposób obliczenia optymalnej liczby transpozycji, które można uzyskać od A do B ? Transpozycja jest definiowana jako zmiana pozycji 2 elementów na …
1
Projektowanie i złożoność algorytmów - jak myśleć w ten „sposób”?
Moje pytanie jest ogólne: jak zacząć myśleć o projektowaniu i złożoności algorytmów? Mam zamiar podjąć kurs magisterski z projektowania algorytmów. Zapisałem się na to wcześniej, ale porzuciłem go później, ponieważ nie mogłem nadążyć. Muszę wziąć ten kurs jako wymóg. Czy istnieje „sztuczka” do myślenia w ten sposób? Wiem, że jest …
3
Super Mario płynie w NP?
Klasycznym rozszerzeniem problemu maksymalnego przepływu jest problem „maksymalnego przepływu w czasie”: otrzymujesz wykrój, którego dwa węzły są rozróżniane jako źródło i zlew, przy czym każdy łuk ma dwa parametry, wydajność na czas i opóźnienie. Jesteś również biorąc pod uwagę horyzont czasowy . Celem jest, aby obliczyć przepływ w czasie której …
3
Złożoność kolorowania krawędzi na wykresach płaskich
3 krawędzi barwienia wykresów sześcienny -Complete. Twierdzenie o czterech kolorach jest równoważne z tym, że „Każdy sześcienny płaski wykres bez mostka ma 3 krawędzie do pokolorowania”.N.P.N.P.NP Jaka jest złożoność 3-krawędziowego kolorowania sześciennych wykresów płaskich? Ponadto, przypuszcza się, że -edge barwiący N P -hard dla płaskich wykresów z maksymalnym stopniu hemibursztynianu …
4
Czy istnieją znane funkcje z następującą właściwością sumy bezpośredniej?
To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek (choć oczywiście nie mamy żadnych wyraźnych przykładów). Załóżmy, że chciałbym …
3
Zliczanie liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich?
Jest -hard znaleźć czynnik stały przybliżenie najdłuższego cyklu sześciennych Hamiltona wykresach. Sześcienne wykresy hamiltonowskie mają co najmniej dwa cykle hamiltonowskie.NPNPNP Jakie są najbardziej znane wartości górnej i dolnej granicy liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich? Biorąc pod uwagę sześcienny wykres hamiltonowski, jaka jest złożoność znalezienia liczby cykli hamiltonowskich? Czy …
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.