Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Wyjaśnienie rozgałęzień i granic
Mam test dotyczący gałęzi i związanego algorytmu. Rozumiem teoretycznie, jak działa ten algorytm, ale nie mogłem znaleźć przykładów, które ilustrują praktyczne zastosowanie tego algorytmu. Znalazłem kilka przykładów takich jak ten, ale nadal jestem tym zdezorientowany. Szukałem również problemu sprzedawcy podróży i nie mogłem go zrozumieć. Potrzebuję pewnych problemów i jak …
2
Czy dwuprocesowy algorytm wzajemnego wykluczania Petersona uwzględnia procesy umierania?
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 procesem 1 zostaną wykonane do miejsca, w …
3
Logarytmiczna vs podwójna logarytmiczna złożoność czasu
Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O (log( log( n ) )O(log⁡(log⁡(n))\mathcal{O}(\log(\log(n))O (log( n ) )O(log⁡(n))\mathcal{O}(\log(n)) Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych implementacji drzewa wyszukiwania binarnego. Ale na przykład, jeśli weźmiemy to w najlepszym przypadku …
2
Rozstrzygalność języka przedrostka
W połowie kadencji istniała odmiana następującego pytania: Dla rozstrzygalnego zdefiniuj Pokaż, że niekoniecznie jest rozstrzygalny.LLLPref(L)={x∣∃y s.t. xy∈L}Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}Pref(L)Pref(L)\text{Pref}(L) Ale jeśli wybiorę to myślę, że jest również , a zatem jest rozstrzygalne. Również daje ten sam wynik. A …
3
Unikalna ścieżka na ukierunkowanym wykresie
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 wierzchołka u, …
3
Minimalna liczba wskazówek, aby w pełni określić jakieś sudoku?
Wiemy z tego artykułu , że nie istnieje układanka, którą można rozwiązać, zaczynając od 16 lub mniej wskazówek, ale sugeruje, że istnieje układanka, którą można rozwiązać na podstawie 17 wskazówek. Czy wszystkie prawidłowe łamigłówki sudoku można podać w 17 wskazówkach? Jeśli nie, jaka jest minimalna liczba wskazówek, które mogą całkowicie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.