Informatyka

1

Znalezienie optymalnej sekwencji pytań w celu zminimalizowania całkowitego czasu studenta

Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k \}nnnS={s1…sn}S={s1…sn}S = \{ s_1 \ldots …

13 algorithms complexity-theory np-complete np-hard

2

Zliczanie permutacji, których elementy nie mają dokładnie swojego indeksu ± M

Ostatnio zostałem zapytany o ten problem w wywiadzie algorytmicznym i nie udało mi się go rozwiązać. Biorąc pod uwagę dwie wartości N i M, musisz policzyć liczbę permutacji o długości N (używając liczb od 1 do N), tak aby absolutna różnica między dowolną liczbą w permutacji a jej pozycją w …

13 algorithms permutations algorithm-design

7

Jak sprawdzić, czy dwa łańcuchy są wzajemnie permutacjami, używając dodatkowej spacji O (1)?

Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone. Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości alfabetu.

13 algorithms strings space-complexity

1

Algorytmy ze złożonością O (sqrt (N)) SPACE?

Czy są jakieś znane algorytmy dla sformułowanych problemów, które wymagają złożoności SPACE dla O (sqrt (N))? Wiem, że istnieją algorytmy o złożoności czasowej „wielkiej O”.

13 complexity-theory asymptotics space-complexity

2

Czy język jednoargumentowy jest regularny, jeśli wykładnikiem jest funkcja liniowa?

Wykonując bieżące zadanie dla moich kursów języków formalnych i automatów, w pewnym sensie utknąłem na ćwiczeniach obejmujących języki jednoargumentowe (mam nadzieję, że to właściwy termin), tj. Języki oparte na jednej literze. Nie chcę jednak pytać o konkretne ćwiczenia, ale raczej o bardziej ogólną hipotezę, którą wymyśliłem: Niech i . Moja …

13 formal-languages regular-languages

2

Jak słowo „produkcja” stało się synonimem słowa „reguła” w kontekście informatyki?

Studiuję języki formalne i systemy baz produkcyjnych (systemy baz reguł) i jestem trochę zdezorientowany, dlaczego te dwa słowa „produkcja” i „reguła” oznaczają to samo w tak wielu kontekstach w informatyce. W języku angielskim nie wydają się oznaczać tego samego. Nie jestem rodzimym językiem angielskim, ale wiem, że reguła odnosi się …

13 formal-languages terminology automata finite-automata formal-grammars

3

Czy zdefiniowanie przejść na każdym możliwym alfabecie jest obowiązkowe w deterministycznych automatach skończonych?

Jutro jest moja prezentacja i chcę wyjaśnić moje koncepcje… Przeczytałem to w DFA: „Dla każdego stanu należy zdefiniować przejście na wszystkie możliwe symbole (alfabet)”. Czy dla każdego stanu zdefiniowanie przejścia na wszystkie możliwe symbole jest obowiązkowe w DFA? Jeśli nie, proszę podać jakieś przykłady?

13 automata finite-automata nondeterminism

1

Czy to ogólny sposób na przekształcenie jakiejkolwiek procedury rekurencyjnej w rekurencję ogona?

Wygląda na to, że znalazłem ogólny sposób na konwersję dowolnej procedury rekurencyjnej na rekurencyjną: Zdefiniuj podprocedurę pomocnika z dodatkowym parametrem „wynik”. Zastosuj to, co zostanie zastosowane do wartości zwracanej przez procedurę do tego parametru. Zadzwoń do tej procedury pomocnika, aby rozpocząć. Wartość początkowa parametru „wynik” jest wartością punktu wyjścia procesu …

13 algorithms logic recursion lisp

1

Testowanie, czy arbitralny dowód jest okrągły?

Myślałem o dowodach i natknąłem się na ciekawą obserwację. Tak więc dowody są równoważne programom za pomocą izomorfizmu Curry'ego-Howarda, a dowody kołowe odpowiadają nieskończonej rekurencji. Wiemy jednak z problemu zatrzymania, że ogólne testowanie, czy dowolny program powróci na zawsze, jest nierozstrzygalne. Czy Curry-Howard oznacza, że nie ma „kontrolera dowodu”, który …

13 logic curry-howard

2

Żądanie referencyjne: Teoria kategorii w odniesieniu do układów typów

Ciągle słyszę o tym, jak należy nauczyć się teorii kategorii, aby naprawdę zrozumieć teorię języka programowania. Do tej pory nauczyłem się sporo PL bez wchodzenia w sferę kategorii. Uznałem jednak, że nadszedł czas, aby zrobić krok, aby zobaczyć, co straciłem. Niestety, żadne ze źródeł, które mogę znaleźć, nie wydają się …

13 reference-request programming-languages type-theory category-theory

1

Jakie funkcje mogą obliczać wyrażenia rachunku kombinatorycznego?

Wyrażenie kombinatora (powiedzmy na podstawie SK) można traktować jako funkcję, która odwzorowuje wyrażenia rachunku kombinatora na wyrażenia rachunku kombinatora. To znaczy, można myśleć o wyrażeniu jako funkcji X : L → L , gdzie L jest zbiorem wszystkich poprawnych pod względem składniowym wyrażeń kombinatorycznych w podstawie SK. To mapowanie jest …

13 lambda-calculus combinatory-logic

2

Jeśli P = NP, czy istnieją kryptosystemy, które wymagałyby n ^ 2 czasu, aby się złamać?

Jeśli P równa się NP, czy nadal będzie możliwe zaprojektowanie kryptosystemu, w którym optymalny algorytm kryptoanalizy zajmuje, powiedzmy, kwadrat czasu zajmowanego przez legalne algorytmy szyfrowania i deszyfrowania? Czy istnieją już takie algorytmy?

13 cryptography encryption

3

Czy jakiś skończony problem może występować w NP-Complete?

Mój wykładowca wydał oświadczenie Jakikolwiek problem skończony nie może być NP-Complete Mówił wtedy o Sudoku, mówiąc coś w stylu, że dla Sudoku 8x8 istnieje skończony zestaw rozwiązań, ale nie pamiętam dokładnie, co powiedział. Zapisałem notatkę, którą zacytowałem, ale nadal nie rozumiem. Sudoku są NP kompletne, jeśli się nie mylę. Problem …

13 np-complete np

3

Co oznacza pamięć Θ (1)?

Mam definicję algorytmu in-situ od profesora, ale nie rozumiem tego. Algorytmy in-situ odnoszą się do algorytmów działających z pamięcią Θ (1). Co to znaczy?

13 algorithms terminology landau-notation

1

Jeśli

Właśnie znalazłem to zdanie na stronie 6 „Komputerów i nienaruszalności” Garey i Johnsona. Każdy algorytm, którego funkcja złożoności czasowej nie może być tak ograniczona, nazywa się algorytmem wykładniczym w czasie (chociaż należy zauważyć, że ta definicja obejmuje pewne funkcje nieliniowej złożoności czasowej, takie jak , które zwykle nie są uważane …

13 algorithms terminology polynomial-time