Pytania o skończone i nieskończone zbiory i multizbiory, powiązane struktury danych i pojęcia.
EDYCJA: Zadałem teraz podobne pytanie dotyczące różnicy między kategoriami i zestawami. Za każdym razem czytam o teorii typów (co prawda jest raczej nieformalny), naprawdę nie mogę zrozumieć, jak różni się od teorii mnogości, konkretnie . Rozumiem, że istnieje konceptualna różnica między...
Wdrażam zestaw algorytmów wyszukiwania ścieżek, takich jak Dijkstra's, Depth First itp. Początkowo korzystałem z kilku samodzielnie wykonanych wykresów, ale teraz chciałbym podjąć wyzwanie nieco dalej, dlatego szukam jednego z nich wykresy stosowane w testach porównawczych; wykresy miast świata...
Moja matka bierze udział w kursie internetowym, aby zostać bibliotekarką, w tym kursie obejmują wyszukiwania boolowskie, dzięki czemu mogą skutecznie przeszukiwać bazy danych, jednak pojawiło się pytanie brzmiące mniej więcej tak: Wyszukiwanie „x OR y” spowoduje 105 000 trafień, podczas gdy...
Czy jest jakaś struktura danych, która utrzymuje kolekcję zbioru (zbioru skończonego) obsługującą następujące operacje? Czy doceniony zostanie jakikolwiek podliniowy czas pracy? Zainicjuj pusty zestaw. Dodaj element do zestawu. Biorąc pod uwagę dwa zestawy, zgłoś, czy się...
Tytuł zawiera pytanie. Jako dane wejściowe mamy listę elementów, które możemy porównać (określić, która jest największa ). Żaden element nie może być równy. Kluczowe punkty: Porównanie nie jest przechodnie (pomyśl o papierowych nożycach): może to być prawda: A> B, B> C, C> A (zwróć...
Wiem, że od ~ 2004 r. Prawo Moore'a przestało działać na taktowanie procesora. Szukam wykresu pokazującego to, ale nie jestem w stanie go znaleźć: większość wykresów pokazuje liczbę tranzystorów lub pojemność rocznie. Gdzie mogę znaleźć dane pokazujące częstotliwość procesorów komputerów (wszystko...
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą...
Wikipedia ma następującą definicję lematu pompującego dla zwykłych języków ... Niech będzie zwykłym językiem. Następnie istnieje całkowita p ≥ 1 zależy wyłącznie od L , tak że każdy ciąg wagowych w L o długości co najmniej p ( p nazywany jest „pompowanie długość”) może być zapisane jako W = xyz...
Biorąc pod uwagę zestaw zestawów, chciałbym znaleźć zestaw takie, że każdy zbiór w zawiera co najmniej jeden element . Chciałbym również, aby zawierał jak najmniej elementów, jednocześnie spełniając to kryterium, chociaż może istnieć więcej niż jeden najmniejszy z tą właściwością (rozwiązanie...
Mam dwóch dużych zestawów liczb całkowitych i B . Każdy zestaw ma około miliona wpisów, a każdy wpis jest dodatnią liczbą całkowitą o długości co najwyżej 10 cyfr. AAABBB Jaki jest najlepszy algorytm do obliczania i B ∖ A ? Innymi słowy, jak mogę skutecznie obliczyć listę pozycji A , które nie są...
Mam problem z algorytmem. Biorąc pod uwagę macierz (lub zestaw) o nieujemne liczby całkowite. Znajdź maksymalny zestaw z tak że dla wszystkich ,.TT.TnnnSS.STT.Ta∈Sza∈S.a\in Sa⩾|S|za⩾|S.|a\geqslant |S| Na przykład: Jeśli TT.T = [1, 3, 4, 1, 3, 6], wówczas SS.S może być [3, 3, 6] lub [3, 4, 6]...
Załóżmy, że mamy 10 osób, każda z listą ulubionych książek. Dla danej osoby X chciałbym znaleźć specjalny podzbiór książek X, lubiany tylko przez X, tzn. Nie ma innej osoby, która polubiłaby wszystkie książki w specjalnym podzbiorze X. Uważam ten specjalny podzbiór za unikalny „odcisk palca” dla...
Istnieją wydajne struktury danych do reprezentowania ustawionych partycji. Te struktury danych charakteryzują się dużą złożonością czasową dla operacji takich jak Union i Find, ale nie są szczególnie efektywne pod względem przestrzeni. Jaki jest oszczędny przestrzennie sposób reprezentowania...
Muszę wiedzieć, pod którą klasą CFL jest zamknięty, tj. Jaki zestaw jest uzupełnieniem CFL. Wiem, że CFL nie jest zamknięty pod dopełnieniem i wiem, że P jest zamknięty pod dopełnieniem. Ponieważ CFL PI może powiedzieć, że dopełnienie CFL jest zawarte w P (prawda?). Pozostaje pytanie, czy...
W tym pytaniu zapytałem, jaka jest różnica między zestawem a typem . Odpowiedzi te były bardzo precyzyjne (np. @AndrejBauer), dlatego w pogoni za wiedzą poddaję się pokusie zadawania tego samego o kategorie: Za każdym razem, gdy czytam o teorii kategorii (co wprawdzie jest raczej nieformalne), nie...
Z mojego czytania wynika, że większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda...
Szukam implementacji ustawionego typu danych. To znaczy musimy utrzymywać dynamiczny podzbiór SSS (wielkościowy nnn) z wszechświata wielkości u zU={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\}uuu operacje insert(x)(dodaj element xdo SSS ) i find(x)(sprawdza, czy element xjest...