Informatyka

4

Interesuje mnie złożoność czasowa kompilatora. Oczywiście jest to bardzo skomplikowane pytanie, ponieważ istnieje wiele kompilatorów, opcji kompilatora i zmiennych do rozważenia. W szczególności interesuję się LLVM, ale interesują mnie wszelkie przemyślenia i miejsca rozpoczęcia badań. Całkiem google wydaje się niewiele rozjaśniać. Domyślam się, że istnieją pewne kroki optymalizacji, które są …

54 compilers

8

Czy kod Morse'a bez spacji jest jednoznacznie rozszyfrowywany?

Czy wszystkie ciągi kodu Morse'a są jednoznacznie rozszyfrowalne? Bez spacji ......-...-..---.-----.-..-..-.. może być, Hello Worldale być może pierwsza litera jest 5- w rzeczywistości wydaje się bardzo mało prawdopodobne, aby dowolna sekwencja kropek i myślników miała unikalne tłumaczenie. Można użyć nierówności Krafta, ale dotyczy to tylko kodów prefiksów . Kod Morse'a …

54 information-theory coding-theory

7

Czy maszyna Turinga „z definicji” jest najmocniejszą maszyną?

Zgadzam się, że maszyna Turinga może „rozwiązać wszystkie możliwe problemy matematyczne”. Jest tak, ponieważ jest to tylko reprezentacja algorytmu na maszynie: najpierw zrób to, a następnie zrób to, a na końcu wyślij to. Chodzi mi o to, że wszystko, co można rozwiązać, może być reprezentowane przez algorytm (ponieważ jest to …

54 algorithms turing-machines automata computation-models

7

Dlaczego procesor ma 32 rejestry?

Zawsze zastanawiałem się, dlaczego procesory zatrzymały się przy 32 rejestrach. To zdecydowanie najszybszy element maszyny, dlaczego nie stworzyć większych procesorów z większą liczbą rejestrów? Czy nie oznaczałoby to mniejszego korzystania z pamięci RAM?

52 computer-architecture

2

Jak zdefiniować kwantowe maszyny Turinga?

W obliczeniach kwantowych jaki jest równoważny model maszyny Turinga? Jest dla mnie całkiem jasne, w jaki sposób można zbudować obwody kwantowe z bram kwantowych, ale jak możemy zdefiniować kwantową maszynę Turinga (QTM), która może faktycznie korzystać z efektów kwantowych, a mianowicie działać na układach wielowymiarowych?

52 quantum-computing turing-machines computation-models

4

Co to jest rekurencja ogona?

Znam ogólną koncepcję rekurencji. Zetknąłem się z koncepcją rekurencji ogona podczas studiowania algorytmu Quicksort. W tym filmie z algorytmem szybkiego sortowania z MIT o godzinie 18:30 profesor mówi, że jest to algorytm rekurencyjny ogona. Nie jest dla mnie jasne, co tak naprawdę oznacza rekurencja ogona. Czy ktoś może wyjaśnić tę …

52 algorithms reference-request recursion

5

Jak wygląda ten algorytm sortowania Θ (n³), a nie Θ (n²), w najgorszym przypadku?

Właśnie zaczynałem kurs na temat struktur danych i algorytmów, a mój asystent nauczycielski dał nam następujący pseudo-kod do sortowania tablicy liczb całkowitych: void F3() { for (int i = 1; i < n; i++) { if (A[i-1] > A[i]) { swap(i-1, i) i = 0 } } } To może …

52 algorithm-analysis asymptotics runtime-analysis sorting

2

Czy istnieją algorytmy czasu podwykładniczego dla problemów NP-zupełnych?

Czy istnieją problemy NP-zupełne, które dowiodły algorytmów podwykładniczych? Proszę o ogólne informacje na temat spraw, nie mówię tutaj o przypadkach specjalnych, które można zastosować. Pod wykładniczo rozumiem porządek wzrostu powyżej wielomianów, ale mniejszy niż wykładniczy, na przykład .nlognnlog⁡nn^{\log n}

51 complexity-theory np-complete np

6

Dlaczego niektóre gry są kompletne?

Przeczytałem wpis w Wikipedii na temat „ Listy problemów z NP-complete ” i odkryłem, że gry takie jak Super Mario, Pokemon, Tetris lub Saga Crush Candy są na przykład kompletne. Jak mogę sobie wyobrazić np. Kompletność gry? Odpowiedzi nie muszą być zbyt precyzyjne. Chcę tylko uzyskać przegląd tego, co oznacza, …

50 complexity-theory np-complete computer-games

3

Problem z plecakiem - NP-kompletny pomimo dynamicznego rozwiązania programistycznego?

Problemy z plecakiem można łatwo rozwiązać za pomocą programowania dynamicznego. Programowanie dynamiczne przebiega w czasie wielomianowym; dlatego to robimy, prawda? Przeczytałem, że jest to w rzeczywistości problem NP-zupełny, co oznaczałoby, że rozwiązanie problemu wielomianowego jest prawdopodobnie niemożliwe. Gdzie jest mój błąd?

50 complexity-theory np-complete dynamic-programming

6

Zachowanie sekretu łańcucha w (otwartym) kodzie źródłowym

Skończyłem opracowywać aplikację na Androida i zamierzam opublikować ją na GPL - chcę, żeby była open source. Jednak natura aplikacji (gry) polega na tym, że zadaje ona zagadki i ma zakodowane odpowiedzi w zasobie łańcucha. Nie mogę opublikować odpowiedzi! Powiedziano mi, żebym szukał bezpiecznego przechowywania haseł - ale nie znalazłem …

50 arrays security

4

Dlaczego czas wielomianowy nazywany jest „wydajnym”?

Dlaczego w informatyce jakakolwiek złożoność, która jest co najwyżej wielomianowa, jest uważana za wydajną? Dla każdego praktycznego zastosowania (a) algorytmy o złożoności są znacznie szybsze niż algorytmy działające w czasie, powiedzmy n 80 , ale pierwszy jest uważany za nieefektywny, a drugi jest wydajny. Gdzie jest logika ?!nlognnlog⁡nn^{\log n}n80n80n^{80} (a) …

50 algorithms complexity-theory terminology efficiency

2

Co dzieje się z zawartością pamięci podręcznej przełącznika kontekstu?

Co w procesorze wielordzeniowym, co dzieje się z zawartością pamięci podręcznej rdzenia (powiedzmy L1), gdy w tej pamięci podręcznej występuje zmiana kontekstu? Czy zachowanie zależy od architektury, czy jest to ogólne zachowanie stosowane przez wszystkich producentów układów?

50 computer-architecture operating-systems cpu-cache

3

Dlaczego wyszukiwanie binarne jest szybsze niż wyszukiwanie trójskładnikowe?

Przeszukiwanie tablicy elementów przy użyciu wyszukiwania binarnego zajmuje w najgorszym przypadku iteracje ponieważ na każdym kroku zmniejszamy połowę naszej przestrzeni wyszukiwania. Gdybyśmy zamiast tego użyli „wyszukiwania trójskładnikowego”, dwie trzecie naszej przestrzeni wyszukiwania przy każdej iteracji, więc najgorszy przypadek powinien zająć iteracji ...NNNlog2Nlog2⁡N\log_2 Nlog3N<log2Nlog3⁡N<log2⁡N\log_3 N < \log_2 N Wygląda na to, …

49 algorithms algorithm-analysis runtime-analysis search-algorithms binary-search

12

Jak zweryfikować numer z Bobem bez wiedzy Eve?

Musisz sprawdzić, czy twój przyjaciel, Bob, ma poprawny numer telefonu, ale nie możesz go zapytać bezpośrednio. Musisz zapisać pytanie na karcie, która zostanie przekazana Eve, która zabierze kartę do Boba i zwróci ci odpowiedź. Co musisz napisać na karcie oprócz pytania, aby Bob mógł zakodować wiadomość, aby Ewa nie mogła …

49 algorithms cryptography