Informatyka

3

Jak intuicyjnie czuć, że język jest regularny

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 możliwe?

9 formal-languages regular-languages pumping-lemma intuition

1

Algorytmy uczenia maszynowego oparte na „strukturalnej minimalizacji ryzyka”?

Które algorytmy uczenia maszynowego (oprócz SVM) stosują zasadę strukturalnego minimalizowania ryzyka ?

9 reference-request machine-learning

1

Udowodnij to

Chciałbym skorzystać z Twojej pomocy przy następującym problemie: L = { ⟨ M⟩ ∣ L ( M) jest pozbawiony kontekstu }L={⟨M⟩∣L(M) is context-free}L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \} . Pokaż, że .L ∉ R E∪ C.o R EL∉RE∪CoREL \notin RE \cup CoRE Wiem, że aby udowodnić , wystarczy znaleźć …

9 formal-languages computability context-free turing-machines

1

Czy WPA2 z kluczem wstępnym jest przykładem dowodu braku wiedzy?

Podczas konfigurowania punktu dostępu i wybierania WPA2 należy ręcznie wprowadzić klucz współdzielony (hasło), PSK, zarówno do AP, jak i STA. Obie strony, AP i STA, muszą się uwierzytelnić. Ale muszą to zrobić bez ujawnienia PSK. Obaj muszą udowodnić drugiej stronie, że znają PSK, nie wysyłając go. Czy to przykład dowodu …

9 cryptography security authentication

3

Gdyby

Utknąłem, rozwiązując następne ćwiczenie: Argumentuj, że jeśli L.LL jest bezkontekstowy i RRR jest zatem regularny L / R = { w ∣ ∃ x ∈ Rśww x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} (tj. odpowiedni iloraz ) jest pozbawiony …

9 formal-languages context-free finite-automata closure-properties pushdown-automata

1

Poszukuje algorytmu rankingu, który faworyzuje nowsze wpisy

Pracuję nad systemem rankingowym, który uszereguje wpisy na podstawie głosów oddanych przez pewien czas. Szukam algorytmu, który obliczy wynik, który jest trochę jak średnia, ale chciałbym, aby faworyzował nowsze wyniki niż starsze. Myślałem o czymś w rodzaju: s c o r e1+ 2 ⋅ s c o r e2) + …

9 algorithms data-mining

4

Co oznaczają przerwania w kontekście systemów operacyjnych?

Latem postanowiłem przeczytać Koncepcje systemów operacyjnych autorstwa Silberschatz, Galvin Gagne (8. edycja). Dotarłem do tematu, który mnie dezorientuje - przerywa i ich rola związana z systemami operacyjnymi. Tekst mówi, że system operacyjny rozpocznie pierwszy proces, taki jak „init”, a następnie zaczeka na „zdarzenie”, a to zdarzenie jest zwykle sygnalizowane przez …

9 operating-systems computer-architecture process-scheduling

1

Pokrycie prostokąta przez linię przeciągnięcia

Dostałem ćwiczenie, niestety nie udało mi się. Istnieje zestaw prostokątów i prostokąt . Za pomocą algorytmu zamiatania płaszczyzny ustal, czy jest całkowicie objęte zestawem .R1..RnR1..RnR_{1}..R_{n}R0R0R_{0}R0R0R_{0}R1..RnR1..RnR_{1}..R_{n} Więcej informacji na temat zasady algorytmów linii przeciągnięcia znajduje się tutaj . Zacznijmy od początku. Początkowo znamy algorytm linii przeciągnięcia jako algorytm znajdowania skrzyżowań segmentów …

9 algorithms computational-geometry

3

Schemat T kompilatora krzyżowego

Studiuję Bootstrapping z Red Dragon Book Compilers i znalazłem schemat T dla kompilatora krzyżowego dość mylący. Nie rozumiem, co należy rozumieć przez „Uruchamianie kompilatora 1 do kompilatora 2”. Czy ktoś może podać jakieś lepsze wyjaśnienie, analogię lub przykład odnoszący się do jakiegoś kompilatora w świecie rzeczywistym? Najpierw notacja. Przez Znaczy …

9 compilers terminology

1

Atak na funkcje mieszające, które nie spełniają właściwości jednokierunkowej

Zastanawiam się nad kursem bezpieczeństwa komputerowego i utknąłem w jednym z poprzednich pytań. Tutaj jest to: Alice ( ) chce wysłać krótką wiadomość do Boba ( ) za pomocą wspólnego tajnego aby potwierdzić, że wiadomość od niej pochodzi. Proponuje wysłanie pojedynczej wiadomości z dwoma częściami: gdzie jest funkcją skrótu, a …

9 cryptography hash one-way-functions

1

Problem chińskiego listonosza: znalezienie najlepszych połączeń między węzłami nieparzystego stopnia

Piszę program, rozwiązując problem chińskiego listonosza (znany również jako problem z inspekcją trasy) w niedokierowanym drafcie i obecnie napotykam problem, aby znaleźć najlepsze dodatkowe krawędzie do łączenia węzłów o dziwnym stopniu, dzięki czemu mogę obliczyć obwód Eulera. Może istnieć (biorąc pod uwagę rozmiar wykresu, który chce zostać rozwiązany) ogromna kombinacja …

9 algorithms graph-theory graphs

1

Dolne granice obliczania funkcji zbioru

Posiadanie zestawu ZAAAz elementów, powiedzmy, że chcę obliczyć funkcję która jest wrażliwa na wszystkie części danych wejściowych, tj. zależy od samego elementu (tzn. można zmienić dowolny element na coś innego, aby uzyskać nowe wejście pierwsza wartość na i są różne).nnnfa( A )f(A)f(A)ZAAAZAAAZA′A′A'faffZAAAZA′A′A' Na przykład może być sumą lub średnią.faff Czy …

9 complexity-theory

1

Rozwiązywanie nawrotów za pomocą charakterystycznego wielomianu z wyobrażonymi korzeniami

W analizie algorytmów często trzeba rozwiązywać nawroty. Oprócz Twierdzenia Mistrza, metod podstawiania i iteracji, istnieje jedna z charakterystycznymi wielomianami . Powiedzieć, że stwierdzono, że wielomian charakterystyczny ma urojoną korzenie, mianowicie i . Więc nie mogę użyćx2−2x+2x2−2x+2x^2 - 2x + 2x1=1+ix1=1+ix_1 = 1+ix2=1−ix2=1−ix_2 =1-i c1⋅xn1+c2⋅xn2c1⋅x1n+c2⋅x2n\qquad c_1\cdot x_1^n + c_2\cdot x_2^n uzyskać …

9 algorithms algorithm-analysis recurrence-relation

4

Słowa, które mają ten sam prawy i lewy skojarzony produkt

Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący: Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej do lewej, mnożąc zgodnie z poniższą tabelą: ×zabdozazadobbzazadododobza×abcaaacbcabcbca\qquad \displaystyle\begin{array}{c|ccc} \times …

9 formal-languages automata regular-languages finite-automata nondeterminism

1

Wyrażanie arbitralnej permutacji jako sekwencji operacji (wstawianie, przenoszenie, usuwanie)

Załóżmy, że mam dwa ciągi. Nazywamy je i . Żaden ciąg nie ma powtarzających się znaków.AAABBB Jak znaleźć najkrótszą sekwencję operacji wstawiania, przenoszenia i usuwania, która zamienia w , gdzie:AAABBB insert(char, offset)wstawia charna podany offsetw ciągu move(from_offset, to_offset)przesuwa postać aktualnie przesuniętą from_offsetdo nowej pozycji, tak aby przesunęła sięto_offset delete(offset) usuwa …

9 algorithms combinatorics string-metrics