Jest to trywialne ćwiczenie w automatach skończonych, aby pokazać, że nie ma algorytmu, który mógłby wykryć wszystkie wirusy, ale wiele firm sprzedaje oprogramowanie antywirusowe. Czy jest jakaś część CS, która zajmuje się wirusami i antywirusami? PS: Nie pytam o niezwiązane z CS uzasadnienie...
Załóżmy, że chcemy połączyć dwie relacje w predykacie. Czy to jest w NC? Zdaję sobie sprawę, że dowód, że nie ma go w NC, będzie równoznaczny z dowodem, że , więc przyjmuję dowód, że jest to otwarty problem jako odpowiedź.P≠NCP≠NCP\not=NC Interesuje mnie zarówno ogólny przypadek, jak i konkretne...
Myślę, że w algorytmie Petersona dla wzajemnego wykluczenia , jeśli proces, który pierwszy wejdzie do sekcji krytycznej, umrze lub zostanie anulowany, drugi proces zapętli się na zawsze, czekając na wejście do sekcji krytycznej. Na zdjęciu, jeśli proces 1 zostanie zatrzymany, pozostałe procesy za...
Chcemy rozwiązać problem minimalnego przepływu kosztów za pomocą ogólnego algorytmu anulowania cyklu ujemnego. Oznacza to, że zaczynamy od losowego prawidłowego przepływu, a następnie nie wybieramy żadnych „dobrych” cykli ujemnych, takich jak cykle o średnich kosztach minimalnych, ale używamy...
Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?L = {zanbndon}L.={zanbndon} L= \{a^n b^n c^n\} Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest...
Czy są jakieś dobre zasoby internetowe do nauki matematyki dyskretnej z zestawami
Biorąc pod uwagę dwa zestawy i każdy zawierający rozłącznych punktów na płaszczyźnie, oblicz najkrótszą odległość między punktem w a punktem w , tj. .AAABBBnnnAAABBBmin { dist(p,q) | p∈A∧q∈B }min { dist(p,q) | p∈A∧q∈B }\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q...
Czy algorytm sztucznej sieci neuronowej można wyrazić w kategoriach operacji zmniejszania mapy? Interesuję się również bardziej ogólnie metodami paralelizacji stosowanymi do ANN i ich zastosowaniem do przetwarzania w chmurze. Sądzę, że jedno podejście wymagałoby uruchomienia pełnego ANN na każdym...
W artykule Parsing Expressions by Recursive Descent autorstwa Theodore Norvell (1999) autor zaczyna od następującej gramatyki wyrażeń arytmetycznych: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v co jest dość złe, ponieważ jest dwuznaczne i lewostronne. Zaczyna...
Zwykle uniwersytety uczą dyskretnej matematyki / dyskretnej struktury. Moje pytanie brzmi: ile matematyki trzeba wiedzieć, aby zrozumieć ten obszar? Czy rachunek różniczkowy jest konieczny, czy też przedskalicznik wystarczy? Czy trzeba wcześniej zrobić dowody, aby zrozumieć ten obszar? Dziękuję...
Próbuję nauczyć się różnych podejść do weryfikacji oprogramowania. Przeczytałem kilka artykułów. O ile się dowiedziałem, logika zdaniowa z temporalnym na ogół wykorzystuje sprawdzanie modelu za pomocą solverów SAT (w systemach trwających - reaktywnych), ale co z logiką pierwszego rzędu z...
Wymóg, aby kodowanie było wolne od prefiksów, skutkuje dużymi drzewami, ponieważ drzewo musi być kompletne. Czy istnieje próg, w którym niekodowane przechowywanie danych o stałej długości byłoby bardziej wydajne niż kodowanie
Przeczytałem wiele dokumentów na temat splotu w przetwarzaniu obrazu i większość z nich mówi o jego formule, kilku dodatkowych parametrach. Nikt nie wyjaśnia intuicji i prawdziwego znaczenia robienia splotu na obrazie. Na przykład intuicja wyprowadzania na wykresie sprawia, że jest on na przykład...
Jeśli masz algorytm szybkiego sortowania i zawsze wybierasz najmniejszy (lub największy) element jako element przestawny; czy mam rację zakładając, że jeśli dostarczysz już posortowany zestaw danych, zawsze uzyskasz najgorsze wyniki niezależnie od tego, czy twoja „już posortowana” lista jest w...
Chcę wydajnie filtrować listę liczb całkowitych dla duplikatów w taki sposób, że tylko wynikowy zestaw musi być przechowywany. Można to zobaczyć na jeden sposób: mamy szereg liczb całkowitych S={1,…,N}S={1,…,N}S = \{1, \dots{}, N\} z NNN duży (powiedzmy 2402402^{40}) mamy funkcję f:S→Sf:S→Sf : S...
Czy maszyna Turinga, która może odczytywać i zapisywać symbole z nieskończonego alfabetu, ma większą moc niż zwykła TM (to jedyna różnica, maszyna wciąż ma skończoną liczbę stanów)? Intuicja mówi mi, że nie, ponieważ potrzebujesz nieskończonej liczby stanów, aby odróżnić każdy symbol. Myślę więc,...
Dostałem zadanie domowe z Big O. Utknąłem z zagnieżdżonymi pętlami zależnymi od poprzedniej pętli. Oto zmieniona wersja mojego pytania do pracy domowej, ponieważ naprawdę chcę to zrozumieć: sum = 0; for (i = 0; i < n; i++ for (j = 0; j < i; j++) sum++; Część, która mnie wyrzuca, to j...
Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania MMM wykresu dwudzielnego G(U,V,E)G(U,V,E)G(U, V, E) jest zawsze równy min(|U|,|V|)min(|U|,|V|)\min(|U|,
Jeśli wykres ma cykl Eulera, to czy połączone elementy mają również cykle
Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka vvv tak, że dla każdego u ≠ vu≠vu \ne v jest co najwyżej jedna ścieżka z vvv do uuu. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego...