Informatyka

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

3
Problem sterty d-ary z CLRS
Byłem zdezorientowany podczas rozwiązywania następującego problemu (pytania 1–3). Pytanie D -ary sterty jest jak stos binarny, lecz (z wyjątkiem jednej z możliwych) węzły nie liść ma d dzieci zamiast 2 dzieci. Jak byś stanowią d -ary sterty w tablicy? Jaka jest wysokość d -ary sterty n elementów pod względem n …
1
Matematyka dla TCS major
Szukam specjalizacji z informatyki teoretycznej; szczególnie interesuje mnie teoria złożoności i teoria automatów probabilistycznych. Kiedy kończę rok, jakie zaawansowane kursy matematyczne (jak na przykład teoria Galois lub analiza harmoniczna) są przydatne do przejęcia kolejnych dwóch semestrów? Dlaczego?
1
Odrębne zmienne dla różnych klauzul
W dowodzeniu twierdzenia o rozdzielczości zwykle przyjmuje się, że zmienne w różnych klauzulach są różne. To nie dzieje się automatycznie; do wdrożenia wymaga znacznego dodatkowego kodu i obliczeń. Biorąc to pod uwagę, szukam dla niego skrzynki testowej. Problem polega na tym, że we wszystkich testowanych dotychczas testach nie ma to …
2
Określanie konkretnej liczby w czasie i przestrzeni (najgorszy przypadek)
\newcommand\ldotd{\mathinner{..}} Biorąc pod uwagę, że A[1..n]A[1..n]A[1\ldotd n] to liczby całkowite takie, że 0≤A[k]≤m0≤A[k]≤m0\le A[k]\le m dla wszystkich 1≤k≤n1≤k≤n1\le k\le n oraz występowanie każdego liczba z wyjątkiem określonej liczby w A[1..n]A[1..n]A[1\ldotd n] jest liczbą nieparzystą. Spróbuj znaleźć numer, którego wystąpienie jest liczbą parzystą. Istnieje algorytm Θ(nlogn)Θ(nlog⁡n)\Theta(n\log n) : sortujemy A[1..n]A[1..n]A[1\ldotd n] …
2
Słaba funkcja haszująca dla niezapomnianych adresów IPv6
Adresy IPv6 w postaci 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0są znacznie trudniejsze do zapamiętania lub nawet transkrypcji niż 4 oktety IPv4. Tam nie było próby ograniczenia tego, co adresy IPv6 jakoś bardziej niezapomniany. Czy istnieje celowo słaba funkcja haszująca, którą można odwrócić, aby stwierdzić, że fraza mówi „Jest to względnie łagodne i łatwe do wykrycia, …
1
Wykazać, że funkcja boolowska obliczalna w T (n) przez maszynę RAM jest w DTIME (T (n) ^ 2)
Pytanie brzmi: ćwiczenie 1.9 z książki Arory-Barak Computational Complexity - A Modern Approach : Zdefiniuj maszynę RAM Turing jako maszynę Turinga, która ma pamięć o dostępie swobodnym. Sformalizujemy to w następujący sposób: Maszyna ma nieskończoną tablicę A, która jest inicjalizowana dla wszystkich spacji. Uzyskuje dostęp do tej tablicy w następujący …
2
Jaka jest średnia wysokość drzewa binarnego?
Czy istnieje formalna definicja średniej wysokości drzewa binarnego? Mam pytanie instruktażowe dotyczące znalezienia średniej wysokości drzewa binarnego przy użyciu następujących dwóch metod: Naturalnym rozwiązaniem może być przyjęcie średniej długości wszystkich możliwych ścieżek od korzenia do liścia avh1(T)=1# leaves in T⋅∑v leaf of Tdepth(v)avh1⁡(T)=1# leaves in T⋅∑v leaf of Tdepth⁡(v)\qquad \displaystyle …
1
Jak udowodnić, że pętle ε nie są konieczne w urządzeniach PDA?
W kontekście naszego dochodzenia w sprawie automatów sterty chciałbym udowodnić, że dany wariant nie akceptuje języków niewrażliwych na kontekst. Ponieważ nie mamy równoważnego modelu gramatycznego, potrzebuję dowodu, który wykorzystuje tylko automaty; dlatego muszę pokazać, że automaty sterty mogą być symulowane przez LBA (lub równoważny model). Oczekuję, że dowód zadziała podobnie …
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.