Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

3
Czy są jakieś zbiory policzalne, których nie można wyliczyć?
Zbiór jest policzalny, jeśli ma bijectję z liczbami naturalnymi, i jest obliczalny (ce), jeśli istnieje algorytm, który wylicza jego elementy. Każdy nieskończony obliczalny zestaw wyliczalny musi być policzalny, ponieważ możemy zbudować bijection z wyliczenia. Czy są jakieś przykłady zbiorów policzalnych, których nie da się wyliczyć? Oznacza to, że istnieje bijection …
2
Jaki jest przykład niezadowalającej formuły 3-CNF?
Próbuję owinąć głowę wokół dowodu kompletności NP, który wydaje się obracać wokół SAT / 3CNF-SAT. Może jest późna godzina, ale obawiam się, że nie mogę wymyślić formuły 3CNF, której nie można spełnić (prawdopodobnie brakuje mi czegoś oczywistego). Czy możesz podać mi przykład takiej formuły?
1
Algorytm
Klika problem jest znany -Complete problemem przy czym wielkość wymaganej klika jest częścią wejścia. Jednak problem kliki k ma trywialny wielomianowy algorytm czasu ( O ( n k ), gdy k jest stałe). Interesują mnie najlepiej znane górne granice, gdy k jest stałe.NPNPNPO(nk)O(nk)O(n^k)kkk Czy istnieje algorytm z czasem wykonania ? …
3
Czy drzewo można przemierzać bez rekurencji, stosu lub kolejki, a jedynie garść wskazówek?
Pół dekady temu siedziałem w klasie struktur danych, w której profesor oferował dodatkowy kredyt, jeśli ktokolwiek mógł przemierzać drzewo bez użycia rekurencji, stosu, kolejki itp. (Lub innych podobnych struktur danych) i tylko kilka wskazówek. Wpadłem na to, co uważałem za oczywistą odpowiedź na to pytanie, które ostatecznie zostało zaakceptowane przez …
2
Sterta - Daj algorytmowi
Najprawdopodobniej pytanie to zostało zadane wcześniej. Pochodzi z problemu CLRS (2nd Ed) 6.5-8 - Podaj algorytm czasu O(nlgk)O(nlg⁡k)O(n \lg k) , aby połączyć kkk sortowanych list w jedną posortowaną listę, gdzie nnn jest całkowitą liczbą elementów na wszystkich listach wejściowych. (Wskazówka: użyj min-sterty do scalania -way.)kkk Ponieważ istnieje list posortowanych …
4
Jak opracować algorytm, który sugeruje możliwe przepisy kulinarne?
Kiedyś miałem na kursie weterana, który stworzył algorytm, który sugerowałby przepisy kulinarne. Na początku pojawiły się wszelkiego rodzaju szalone przepisy. Następnie trenowała algorytm gotowania z prawdziwymi przepisami i ostatecznie sugerowałaby te bardzo dobre. Wydaje mi się, że użyła czegoś związanego z Twierdzeniem Bayesa lub Clustering, ale już dawno jej nie …
2
Zdecydowane języki niewrażliwe na kontekst
Można argumentować, że większość języków stworzonych do opisywania codziennych problemów ma charakter kontekstowy. Z drugiej strony jest możliwe i nietrudno znaleźć niektóre języki, które nie są rekurencyjne, a nawet nie są wymienne. Pomiędzy tymi dwoma typami znajdują się rekurencyjne języki beztekstowe. Wikipedia podaje tutaj jeden przykład : Przykładem języka rekurencyjnego, …
3
Dlaczego nie przyjąć jednolitej reprezentacji liczb w algorytmach numerycznych?
Pseudo-wielomianowy algorytm czasu jest algorytmem, który ma wielomianowy czas działania na wartości wejściowej (wielkość), ale wykładniczy czas działania na wielkości wejściowej (liczba bitów). Na przykład sprawdzenie, czy liczba jest liczbą pierwszą, czy nie, wymaga przejścia przez liczby od 2 do i sprawdzenia, czy mod wynosi zero, czy nie. Jeśli mod …
6
Jakie części algebry liniowej są używane w informatyce?
Czytam Algebrę liniową i jej aplikacje, aby pomóc w zrozumieniu materiałów informatycznych (głównie uczenia maszynowego), ale martwię się, że wiele informacji nie jest użytecznych dla CS. Na przykład wiedza o tym, jak skutecznie rozwiązywać układy równań liniowych, nie wydaje się bardzo przydatna, chyba że próbujesz zaprogramować nowy układ równań. Dodatkowo, …
2
Jest uzupełnieniem {ww | …} Bez kontekstu?
Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?LLLL={a,b}∗−{ww∣w∈{a,b}∗}L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}LLLLLL Próbowałem przeciąć z , ale nadal nie mogę niczego udowodnić. Spojrzałem również na twierdzenie Parikha, ale to nie pomaga.LLLa∗b∗a∗b∗a∗b∗a∗b∗a^*b^*a^*b^*
5
Jakie jest znaczenie ujemnych krawędzi masy na wykresie?
Robiłem ćwiczenia programowania dynamicznego i znalazłem algorytm Floyda-Warshalla. Najwyraźniej znajduje wszystkie pary najkrótszych ścieżek dla wykresu, który może mieć ujemne krawędzie wagi, ale nie ma ujemnych cykli. Zastanawiam się więc, jakie jest rzeczywiste znaczenie ujemnych krawędzi wagi? Przydałoby się proste angielskie wyjaśnienie.
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.