Informatyka

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

2
Nazwa tego problemu z przestawieniem / sortowaniem?
Otrzymujesz tablicę o długości . Każdy element tablicy należy do jednej z klas. Powinieneś zmienić układ tablicy za pomocą minimalnej liczby operacji wymiany, aby wszystkie elementy z tej samej klasy były zawsze pogrupowane razem, tj. Tworzą ciągłą pod-tablicę. Na przykład: Pozostały trzy inne ważne ustalenia.K.nnnKKK[2,1,3,3,2,2]⟶[2,2,2,1,3,3], or[2,1,3,3,2,2]⟶[1,2,2,2,3,3], or[2,1,3,3,2,2]⟶[3,3,2,2,2,1].[2,1,3,3,2,2]⟶[2,2,2,1,3,3], or[2,1,3,3,2,2]⟶[1,2,2,2,3,3], or[2,1,3,3,2,2]⟶[3,3,2,2,2,1]. \begin{align*} …
2
Dlaczego odtwarzanie dźwięku nie zatrzymuje innych zadań?
Jeśli procesory mogą wykonywać tylko jedną rzecz naraz, to dlaczego mogę ciągle odtwarzać muzykę i nadal móc wykonywać inne zadania? Rozumiem system przerwań, ale czy nie jest konieczne, aby procesor nieprzerwanie przetwarzał dźwięk, aby nie wydawał się roztrzęsiony / opóźniony? Pytam o implementację, czy to pytanie dotyczy wielowątkowości? W jaki …
3
Co oznacza „mapa”?
Termin ten spotkałem wiele razy w różnych materiałach edukacyjnych CS: L2 CS162 (UC Berkeley): We / wy mapowane na pamięć L4 CS162 (UC Berkeley): Pliki mapowane w pamięci L24 CS61 (UC Berkeley): „We / wy mapowane na pamięć”: Rejestry sterowania / danych mapowane na przestrzeń adresową procesora Nawet po „mapowaniu” …
1
Czy istnieje logiczna koncepcja „Turing Complete”?
Można wykazać, że dwa modele obliczeniowe są kompletne, jeśli każdy z nich może zakodować uniwersalny symulator dla drugiego. Można wykazać, że dwie logiki są kompletne, jeśli kodowanie reguł wnioskowania (i może aksjomatów, jeśli są obecne) każdego z nich jest twierdzeniem drugiej. W obliczeniach doprowadziło to do naturalnego pomysłu kompletności Turinga …
2
problem z wykresem sieci społecznościowej
Oto problem: Jest połączony wykres z węzłami reprezentującymi wiele osób. Każdy węzeł / osoba ma opinię na dany temat, np. Atut vs clinton, papierowe książki kontra kindle itp Celem jest, aby każdy węzeł na wykresie podzielał tę samą opinię, wybierając konkretny podzbiór węzłów, w określonej kolejności. Jeśli większość przyjaciół osoby …
1
Dlaczego typy rekurencyjne są potrzebne jako prymitywy dla prób w systemach typu zależnego?
Jestem stosunkowo nowy w teorii typów i programowaniu zależnym. Studiowałem rachunek różniczkowy konstrukcji (CoC) i inne systemy czystego typu. Szczególnie interesuje mnie wykorzystanie go jako pośredniej reprezentacji zabezpieczającej system kompilatora. Rozumiem, że typy (ko) rekurencyjne są reprezentatywne , obliczeniowo , przy użyciu jako jedynego konstruktora typów. Przeczytałem jednak, że nie …
1
Literatura na temat naiwnego podejścia do izomorfizmu grafów poprzez badanie wielomianów macierzy przylegania
Opisuję podejście do izomorfizmu grafowego, które prawdopodobnie ma fałszywie dodatnie, i jestem ciekawy, czy istnieje literatura wskazująca, że ​​to nie działa. Biorąc pod uwagę dwa przylegania macierzy , co prawda naiwne Sposób sprawdzania izomorfizmie jest sprawdzenie, czy dla każdego rzędu U z G , znajduje się wiersz V z G …
1
Typy jako obywatel pierwszej klasy
Pochodząc z języka C ++ nie rozumiem, dlaczego jako obywatel pierwszej klasy potrzebne są typy / wyrażenia typu? Jedynym znanym mi językiem obsługującym tę funkcję jest Aldor. Czy ktoś ma literaturę na temat typów jako obywatel pierwszej klasy lub wie, dlaczego jest to przydatne?
3
Traktowanie grafów niekierowanych jako podkategorii grafów ukierunkowanych
Z grubsza, wykres bezkierunkowy jest bardzo podobny do wykresu skierowanego, gdzie dla każdej krawędzi (v, w) zawsze jest krawędź (w, v). To sugeruje, że akceptowalne może być wyświetlanie nieukierunkowanych wykresów jako podzestawu kierowanych wykresów (być może z dodatkowym ograniczeniem, że dodawanie / usuwanie krawędzi można wykonać tylko w pasujących parach). …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać …
2
Czy badane jest następujące rozszerzenie automatów skończonych?
Rozważmy maszynę skończoną jak zwykle, ale przy każdym przejściu może ona także aktualizować licznik liczb całkowitych, dodając lub odejmując liczbę. Powiedzmy, funkcja przejścia w postaci δ(q,a)=(p,k)δ(q,a)=(p,k)\delta(q,a) = (p,k) przechodzi do nowego stanu ppp i dodaje kkk do licznika, gdziek∈Zk∈Zk \in \mathbb{Z} (więc może być dodatnia, ujemna lub zero).kkk Łańcuch jest …
2
Intuicja za bramą Hadamard
Próbuję nauczyć się o obliczeniach kwantowych i mam przyzwoite rozumienie algebry liniowej. Przeszedłem przez bramę NIE, co nie było takie złe, ale potem dotarłem do bramy Hadamard. I utknąłem. Głównie dlatego, że chociaż „rozumiem” manipulacje, nie rozumiem, co naprawdę robią ani dlaczego chcesz je robić, jeśli ma to sens. Na …
3
Próbuję zrozumieć ten dowód poprawności Quicksort
Ten dowód jest dowodem indukcyjnym i wygląda następująco: P (n) jest twierdzeniem, że „Quicksort poprawnie sortuje każdą tablicę wejściową o długości n”. Przypadek podstawowy: każda tablica wejściowa o długości 1 jest już posortowana (blokada P (1)) Krok indukcyjny: fix n => 2. Napraw niektóre tablice wejściowe o długości n. Trzeba …
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.