Informatyka

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

1
Czy łamigłówki „Flow free” są trudne NP?
Układanka „Flow Flow” składa się z dodatniej liczby całkowitej i zestawu (nieuporządkowanych) par odrębnych wierzchołków na wykresie siatki tak że każdy wierzchołek zawiera co najwyżej jedną parę. Rozwiązaniem takiej układanki jest zestaw niekierowanych ścieżek na wykresie, dzięki czemu każdy wierzchołek znajduje się dokładnie na jednej ścieżce, a zestaw końców każdej …
2
Dlaczego MIPS zawiera shamt i rozróżnia funk / opcode?
Jestem zdezorientowany, dlaczego projektanci MIPS mieliby 5 bitów poświęconych przesunięciu i mieli osobne bity opcodu i funkcji. Ponieważ MIPS jest tak RYZYKO, zakładam, że tylko kilka przesunięć można by wykonać w kilku instrukcjach, więc te 5 bitów wydaje się marnować miejsce, gdy można je natychmiast wprowadzić. Zakładam, że opcodes i …
1
Testowanie, czy czworościan leży w wielościanie
Mam czworościanu oraz graniastosłupa . jest tak ograniczony, że zawsze dzieli wszystkie swoje wierzchołki z . Chcę ustalić, czy leży wewnątrz .ttt t p tppptttpppttt ppp Chciałbym dodać jeden szczegół do problemu, w przypadku gdy może on przyczynić się do rozwiązania: jest czworościanem Delaunaya, a ściany są trójkątne i silnie …
1
Konstruowanie nierównych macierzy binarnych
Próbuję skonstruować wszystkie nierówne macierze (lub n × n, jeśli chcesz) z elementami 0 lub 1. Operacją, która daje macierze równoważne, jest jednoczesna wymiana wiersza i i j ORAZ kolumny i i j. na przykład. dla 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) …
1
Jak działa TLB i pamięć podręczna danych?
Próbuję przygotować się do egzaminu i zdałem sobie sprawę, że nie jestem pewien, jak działa TLB i pamięć podręczna danych. Rozumiem, że TLB jest zasadniczo pamięcią podręczną ostatnio używanych adresów fizycznych. Jednak patrzyłem na diagram w moim podręczniku (pokazany poniżej) i nie rozumiem, co się w nim dzieje. Nagle dzieli …
1
Dlaczego współczynnik kompresji przy użyciu bzip2 dla sekwencji „a” jest tak zwariowany?
library(ggplot2) compress <- function(str) { length(memCompress(paste(rep("a", str), collapse=""), type="bzip2")) / nchar(paste(rep("a", str), collapse="")) } cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress)) ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) + geom_line() Stopień kompresji zaczyna się od 37 dla „a”, a osiąga próg rentowności przy 39 „a” s (stopień kompresji = 1). …
6
Jak zaimplementować dwa stosy w jednej tablicy?
Chciałbym zacząć od stwierdzenia, że ​​to NIE jest zadanie domowe. Czytam Wstęp do algorytmów - słynny tekst CLRS, aby stać się lepszym programistą. Próbuję samodzielnie rozwiązać problemy i ćwiczenia podane w książce. Próbuję rozwiązać Ćwiczenie 10.1-2 z rozdziału 10 Elementarne struktury danych z CLRS wydanie drugie. Oto, co jego stany: …
1
Wykładniczy podział między NFA i DFA w obecności związków
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami, przynajmniej wtedy, gdy wielkość alfabetu jest nieograniczona. W istocie, pod język nad alfabetu …
2
Problemy decyzyjne w
Jakie są przykłady trudnych problemów decyzyjnych, które można rozwiązać w czasie wielomianowym? Szukam problemów, dla których optymalny algorytm jest „wolny” lub problemów, dla których najszybszy znany algorytm jest „wolny”. Oto dwa przykłady: Rozpoznawanie idealnych wykresów. W swojej pracy FOCS'03 [1] Cornuéjols, Liu i Vuskovic podali algorytm czasowy dla problemu, gdzie …
1
Kim są ustawodawcy w Paxos?
W przełomowym dokumencie dotyczącym systemów rozproszonych The Part Time Parliament (protokół Paxos) Leslie Lamport wymienia fikcyjnych prawodawców, którzy są zaangażowani w protokół Parlamentu Paxon. Zgodnie z tym pismem zauważa, że: Nadałem greckim prawodawcom nazwiska informatyków pracujących w tej dziedzinie, w transliteracji z pomocą Guibasa na fałszywy grecki dialekt. Czy ktoś …
3
Minimalny rozmiar zawarcia DAG w nowy DAG
Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:fa: V→ N.F:V→NF\colon V\to \mathbb N Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)fa( x ) ≠ F.( y) ⇒ x′. Y′F(x)≠F(y)⇒x′≠y′F(x) \neq F(y) \Rightarrow …
6
Do czego służą kraty?
Wikipedia mówi : Kompletne sieci pojawiają się w wielu zastosowaniach w matematyce i informatyce Czy odnosi się to tylko do faktu, że standardowa algebra boolowska wykorzystywana w obliczeniach jest kompletną siecią? Czy coś zyskujemy dzięki pracy na abstrakcyjnym poziomie sieci, a nie logice logicznej? Wyszukiwarka Google nie znajduje wiele na …
4
Wykres ma dwa / trzy różne minimalne drzewa rozpinające?
Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i znalezienie całkowitej masy minimalnego drzewa opinającego. Później, usuwając krawędź z wykresu …
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.