Informatyka

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

1
Generator losowych Sudoku
Chcę wygenerować całkowicie losowe Sudoku . Zdefiniuj siatkę Sudoku jako siatkę liczb całkowitych od 1 do 9, w której niektóre elementy można pominąć. Siatka jest poprawną łamigłówką, jeśli istnieje wyjątkowy sposób jej wypełnienia, aby dopasować ją do ograniczeń Sudoku (każda linia, kolumna i wyrównany kwadrat 3 × 3 nie ma …
1
Jak konsekwencja oznacza, że ​​heurystyka jest również dopuszczalna?
Funkcja heurystyczna to ...h(n)h(n)h (n) Spójne, jeśli szacowany koszt od węzła do celu nie jest większy niż koszt kroku do jego następcy plus szacowany koszt od następcy do celu.nnnn′n′n' Dopuszczalne, jeżeli nigdy nie przecenia rzeczywistych kosztów do stanu docelowego.h(n)h(n)h(n) Podręcznik mojego kursu sztucznej inteligencji stwierdza, że ​​spójność jest silniejsza niż …
1
Czy POSIX BRE może wyrażać wszystkie zwykłe języki?
Wygląda na to, że „podstawowe wyrażenia regularne” zdefiniowane w POSIX.1-2008 nie obsługują naprzemiennego działania a|b(chociaż niektóre implementacje grep rozpoznają wersję ucieczkową \|). Skoro zwykłe języki są z definicji zamknięte w unii, czy to oznacza, że ​​POSIX BRE ma mniejszą moc ekspresji niż automat skończony? Czy jest jakiś sposób na symulację …
2
Czy architektury procesorów są tendencyjne w stosunku do proceduralnych środowisk wykonawczych?
Czy są jakieś zmiany, które można wprowadzić w procesorach, aby działały lepiej w przypadku równoczesnych środowisk uruchomieniowych, takich jak Rust? Na przykład, czy są jakieś zmiany w implementacjach przewidywania gałęzi lub rozmiarach pamięci podręcznej, które pomogłyby w jednoczesnych uruchomieniach? Mam wrażenie, że obecne konstrukcje procesorów mogą być bardziej zoptymalizowane pod …
2
Co zyskujemy, mając „typy zależne”?
Myślałem, że dobrze rozumiem pisanie zależne (DT), ale odpowiedź na to pytanie: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Teoria typu B6f do tworzenia-intuicyjnego typu kazała mi myśleć inaczej. Po przeczytaniu DT i próbie zrozumienia, czym one są, zastanawiam się, co zyskujemy dzięki temu pojęciu DT? Wydają się być bardziej elastyczne i wydajne niż zwykły rachunek …
2
Udowodnienie, że DOUBLE-SAT jest NP-zakończone
Dobrze znany problem SAT został tu zdefiniowany dla odniesienia. Problem DOUBLE-SAT jest zdefiniowany jako DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\} Jak udowodnimy, że jest kompletny NP? Doceniony zostanie więcej niż jeden …
2
Kiedy mogę zastosować programowanie dynamiczne, aby zmniejszyć złożoność czasową mojego algorytmu rekurencyjnego?
Programowanie dynamiczne może skrócić czas potrzebny do wykonania algorytmu rekurencyjnego. Wiem, że programowanie dynamiczne może pomóc w zmniejszeniu złożoności czasowej algorytmów. Czy ogólne warunki są takie, że spełnienie algorytmu rekurencyjnego oznaczałoby, że zastosowanie programowania dynamicznego zmniejszy złożoność czasową algorytmu? Kiedy powinienem używać programowania dynamicznego?
4
Algorytm Dijsktry zastosowany do problemu sprzedawcy podróżującego
Jestem nowicjuszem (całkowicie początkującym w teorii złożoności obliczeniowej) i mam pytanie. Powiedzmy, że mamy „problem sprzedawcy podróży”, czy poniższe zastosowanie algorytmów Dijkstry rozwiąże ten problem? Od punktu początkowego obliczamy najkrótszą odległość między dwoma punktami. Idziemy do rzeczy. Usuwamy punkt źródłowy. Następnie obliczamy następny najkrótszy punkt odległości od bieżącego punktu i …
3
Czy istnieje abstrakcyjna maszyna, która może rejestrować zużycie energii?
Zgłaszając złożoność algorytmu algorytmu, zakłada się, że obliczenia leżące u jego podstaw są wykonywane na jakiejś abstrakcyjnej maszynie (np. RAM), która przybliża nowoczesny procesor. Takie modele pozwalają nam raportować złożoność algorytmów w czasie i przestrzeni. Teraz, przy rozproszeniu GPGPU , zastanawia się, czy istnieją dobrze znane modele, w których można …
1
Czym różni się zestaw od typu w Coq? [Zamknięte]
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem dotyczącym wymiany stosów w informatyce. Zamknięte 2 lata temu . Typami AFAIU może być element, Setktórego elementami są programy, lub propositionktórego elementami są dowody. Opierając się na tym zrozumieniu: …
1
Po co korzystać z SIMD, jeśli mamy GPGPU?
Myślałem, że to pytanie jest lepiej obsługiwane w części CS programu Stack Exchange. Teraz, gdy mamy GPGPU z takimi językami jak CUDA i OpenCL, czy rozszerzenia multimediów SIMD (SSE / AVX / NEON) nadal spełniają swoje zadanie? Niedawno przeczytałem artykuł o tym, jak można zastosować instrukcje SSE do przyspieszenia sortowania …
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.