Informatyka

3

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 …

9 algorithms algorithm-analysis runtime-analysis landau-notation

1

Skuteczne usuwanie duplikatów przy niskim obciążeniu pamięci

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 \to S z podobno wieloma kolizjami (obrazy …

9 algorithms data-structures sorting

3

Czy Quicksort zawsze ma kwadratowy czas działania, jeśli jako element przestawny wybierzesz maksymalny element?

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 porządku rosnącym czy malejącym? Myślę, że jeśli zawsze wybierzesz najmniejszy …

9 algorithms time-complexity algorithm-analysis runtime-analysis sorting

3

Czy kodowanie Huffmana jest zawsze optymalne?

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 danych?

9 information-theory data-compression

3

Intuicja splotu w przetwarzaniu obrazu

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 bardziej liniowy. Myślę, że szybkie podsumowanie definicji …

9 terminology intuition graphics computer-vision

1

Wyrażenia arytmetyczne transformacja gramatyczna

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 …

9 formal-languages context-free formal-grammars left-recursion

2

Wprowadzenie do weryfikacji logicznej pierwszego rzędu

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 temporalną? Czy wykorzystuje dowody twierdzeń? Czy może również używać SAT? …

9 reference-request logic formal-methods sat-solvers software-verification

1

Czy algorytm sztucznej sieci neuronowej można wyrazić w kategoriach operacji zmniejszania mapy?

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ęźle i jakoś zintegrowania wyników, aby traktować siatkę jak pojedynczy byt …

9 parallel-computing artificial-intelligence neural-networks

5

Ile matematyki trzeba wiedzieć, aby zrozumieć odrębną matematykę / struktury dla informatyki?

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ę wszystkim za odpowiedzi. Uwaga: przepraszam, jeśli zostało to już zadane. po moim …

9 discrete-mathematics

3

Materiały do nauki online dla dyskretnej matematyki

Czy są jakieś dobre zasoby internetowe do nauki matematyki dyskretnej z zestawami problemów?

9 reference-request education discrete-mathematics

1

Dlaczego złożoność ujemnego anulowania cyklu ?

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 Bellman-Ford do odkrycia minimalnego cyklu i zwiększenia wzdłuż odkrytego cyklu. Niech będzie …

9 algorithms graph-theory algorithm-analysis runtime-analysis network-flow

1

Czy sprzężenia mogą być równoległe?

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 przypadki (np. …

9 complexity-theory time-complexity parallel-computing database-theory descriptive-complexity

4

Najkrótsza odległość między punktem A i punktem B

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 \in …

9 algorithms computational-geometry

3

Jaką gałąź informatyki bada działanie programów antywirusowych?

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 posiadania AV, ale tylko o to, jaką …

9 reference-request security

1

Obwody o głębokości 2 z bramkami OR i MOD nie są uniwersalne?

Dobrze wiadomo, że każdą funkcję boolowską można zrealizować za pomocą obwodu boolowskiego o głębokości 2 (ponad zmiennymi, ich negacją i stałymi wartościami) zawierający bramki AND na pierwszym poziomie i jedną pojedynczą bramkę OR na górnym poziomie; jest to po prostu przedstawienie DNF z .f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\}fff Innym rodzajem bramki, która jest …

9 complexity-theory logic circuits