Informatyka

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

2
Jest mocą obliczeniową sieci neuronowych związaną z funkcją aktywacyjną
Udowodniono, że sieci neuronowe o racjonalnych wagach mają moc obliczeniową uniwersalnej maszyny Turinga. Obliczalność Turinga z sieciami neuronowymi . Z tego, co otrzymuję, wydaje się, że użycie ciężarów o wartościach rzeczywistych daje jeszcze więcej mocy obliczeniowej, chociaż nie jestem tego pewien. Czy istnieje jednak korelacja między mocą obliczeniową sieci neuronowej …
1
Turing Recognizable => enumerable
Dostaję dowód przejścia z modułu wyliczającego do maszyny Turinga (kontynuuj działanie modułu wyliczającego i zobacz, czy pasuje on do danych wejściowych), ale nie widzę, jak działa inny sposób. Zgodnie z moimi notatkami i książką (Wprowadzenie do teorii obliczeń - Sipser), aby pobrać moduł wyliczający Turinga z maszyny Turinga, w zasadzie …
3
Powrócono do warunków Sums of Landau
Poprosiłem (nasion) pytanie o sumach Landau warunkach przed , próbując ocenić niebezpieczeństwa nadużywania notacji asymptotyka w arytmetyce, z mieszanym powodzeniem. Teraz, tutaj nasz guru ds. Nawrotów, JeffE , zasadniczo robi to: ∑i=1nΘ(1i)=Θ(Hn)∑i=1nΘ(1i)=Θ(Hn)\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n) Chociaż wynik końcowy jest prawidłowy, myślę, że to źle. Dlaczego? Jeśli dodamy całe …
2
Optymalny solver krótkowzrocznego labiryntu
Wygłupiałem się z prezentacją Google Blocky's Maze i przypomniałem sobie starą zasadę, że jeśli chcesz rozwiązać labirynt, trzymaj lewą rękę przy ścianie. Działa to dla każdego prostego połączenia labiryntu i może być zrealizowane przez skończony przetwornik. Niech nasz robot będzie reprezentowany przez przetwornik z następującymi czynnościami i obserwowalnymi: Czynności: idź …
2
NP-Kompletność problemu kolorowania wykresu
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do NP. Alternatywne sformułowanie wykorzystuje rozłączny zestaw przychodzących i wychodzących węzłów, co upraszcza definicję problemu. Biorąc pod uwagę …
4
Czy istnieje niezdecydowany skończony język skończonych słów?
Czy istnieje potrzeba, aby L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* była nieskończona, aby była nierozstrzygalna? Chodzi mi o to, że jeśli wybierzemy język L′L′L' jako ograniczoną skończoną wersję L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* , to znaczy |L′|≤N|L′|≤N|L'|\leq N ( N∈NN∈NN \in \mathbb{N} ), a L′⊂LL′⊂LL' \subset L . Czy jest możliwe, L′L′L' być język nierozstrzygalny? Widzę, że …
1
Jak udowodnić, że ograniczona wersja 3SAT, w której dosłowność nie może wystąpić więcej niż jeden raz, można rozwiązać w czasie wielomianowym?
Próbuję wypracować zadanie (zaczerpnięte z książki Algorytmy - S. Dasgupta, CH Papadimitriou i UV Vazirani , Rozdział 8, problem 8.6a), i parafrazuję to, co mówi: Biorąc pod uwagę, że 3SAT pozostaje NP-kompletny, nawet jeśli ogranicza się do formuł, w których każdy literał pojawia się co najwyżej dwa razy, pokaż, że …
2
Jak sprawdzić, czy wielokąt jest monotoniczny względem linii?
Powszechnie wiadomo, że wielokąty monotoniczne odgrywają kluczową rolę w triangulacji wielokątów . Definicja: Wielokąt w płaszczyźnie jest nazywany monotonicznym w odniesieniu do linii prostej L , jeśli każda linia prostopadła do L przecina P najwyżej dwa razy.P.PPL.LLL.LLP.PP Biorąc pod uwagę linię i wielokąt P , czy istnieje skuteczny algorytm do …
3
Czy łączenie wysp z pontonami NP-zupełne?
Mam w głowie problem, myślę, że jest to problem NPC, ale nie wiem, jak to udowodnić. Oto problem: Istnieje k wyspy w bardzo dużym jeziorem, a tam są n kształcie wachlarza pontony. Te pontony są tego samego rozmiaru, ale mają różne początkowe kierunki i znajdują się w różnych oryginalnych pozycjach …
2
Jak sklasyfikować problem optymalizacji wejścia emulatora i z jakim algorytmem powinienem do niego podejść?
Ze względu na charakter pytania muszę podać wiele podstawowych informacji (ponieważ moje pytanie brzmi: jak to zawęzić?) To powiedziawszy, można je streścić (o ile wiem): Jakie metody istnieją, aby znaleźć lokalne optimum na bardzo dużych kombinatorycznych przestrzeniach poszukiwań? tło W społeczności superplay wspieranych narzędziami staramy się zapewnić specjalnie spreparowane (nie …
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.