Informatyka

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

2
Znajdowanie najkrótszych i najdłuższych ścieżek między dwoma wierzchołkami w DAG
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu możliwych długości ścieżek w czasie wielomianowym. Ps., To pytanie jest …
7
Dlaczego ujemne wskaźniki tablicowe mają sens?
Natknąłem się na dziwne doświadczenie w programowaniu C. Rozważ ten kod: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Podczas kompilacji i uruchamiania nie otrzymuję żadnych błędów ani ostrzeżeń. Jak powiedział mój wykładowca, …
4
Samokształcenie informatyki
Jestem 16-letnim mężczyzną, który niedawno otrzymał od mojej dużej przyjaciółki encyklopedię informatyki. Zazwyczaj nie interesuję się komputerami i technologią, ale informatyka zaczęła mnie fascynować. Mam jednak zamiar studiować fizykę i / lub matematykę, a nie CS, więc moje pytanie brzmi: czy przydatne byłoby przeprowadzenie samodzielnej nauki informatyki? Oczywiście nie idę …
5
Powód, dla którego warto nauczyć się logiki zdań i predykatów
Rozumiem znaczenie, jakie informatycy lub inżynierowie związani z opracowywaniem oprogramowania powinni rozumieć jako podstawy badania logiki podstawowej. Ale czy są jakieś zadania / zadania, które wyraźnie wymagają wiedzy na ich temat, inne niż zadania wymagające jakiejkolwiek reprezentacji wiedzy przy użyciu Knowledge Base? Chcę usłyszeć rodzaje zadań, a nie koncepcyjne odpowiedzi. …
14 logic 
1
Monadyczna logika drugiego rzędu dla manekinów
Jestem programistą z automatami, ale nie logiką. Przeczytałem w artykułach, że te dwa są ze sobą ściśle powiązane. Deterministyczne automaty skończone (DFA), automaty drzewa i automaty z widocznym przesunięciem w dół są powiązane z logiką Monadic drugiego rzędu (MSO). Chociaż rozumiem automaty i ludzie (w dokumentach) próbowali mi wyjaśnić związek …
3
Czy ten algorytm nadal można uznać za algorytm wyszukiwania binarnego?
Podczas wykonywania drugiego kata kodu (który prosi pięć razy o zaimplementowanie algorytmu wyszukiwania binarnego, za każdym razem inną metodą), wpadłem na nieco inne rozwiązanie, które działa w następujący sposób: Jeśli mam posortowaną tablicę o długości 100 i widzę, że jej pole początkowe zawiera liczbę 200, a pole końcowe zawiera liczbę …
1
Co oznacza tylda w notacji big-O?
Czytam artykuł i w jego opisie złożoności czasowej napisano, że złożoność czasowa to .O~(22n)O~(22n)\tilde{O}(2^{2n}) Przeszukałem internet i wikipedię, ale nie mogę znaleźć tego, co oznacza tylda w notacji big-O / Landau. W samym artykule nie znalazłem też żadnych wskazówek na ten temat. Co oznacza ?O~(⋅)O~(⋅)\tilde{O}(\cdot)
1
Zaokrąglanie zmiennoprzecinkowe
Czy liczba zmiennoprzecinkowa IEEE-754 <1 (tj. Generowana za pomocą generatora liczb losowych, który generuje liczbę> = 0,0 i <1,0) może być kiedykolwiek pomnożona przez jakąś liczbę całkowitą (w postaci zmiennoprzecinkowej), aby uzyskać liczbę równą lub większą niż ta liczba całkowita z powodu zaokrąglenia? to znaczy double r = random() ; …
1
Czy wszystkie drzewa o minimalnej rozpiętości MST są osiągalne przez Kruskala i Prim?
Uważam, że to prawda, ale nie udało mi się uzyskać formalnego dowodu. Ale czy to prawda, że ​​każde minimalne drzewo opinające jest osiągalne dzięki zastosowaniu algorytmu Kruskala? Podobnie, czy dotyczy to algorytmu Prim? EDYCJA: Aby być bardziej precyzyjnym, chcę wiedzieć, czy otrzymując MST dla połączonego, niekierowanego, ważonego wykresu, czy jest …
1
Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością
Literatura jest dość jasna, że ​​jednostronne pamięci RAM z pierwotnym mnożeniem są nieuzasadnione, ponieważ są nie mogą być symulowane przez maszyny Turinga w czasie wielomianowym potrafi rozwiązać problemy związane z PSPACE w czasie wielomianowym Jednak wszystkie odniesienia, które mogę znaleźć na ten temat (Simon 1974, Schonhage 1979) obejmują również operacje …
3
Jaka jest różnica między rachunkiem a językiem programowania?
Myślę, że jestem dość zdezorientowany tym, co nazywa się rachunkiem różniczkowym i językiem programowania. Zwykle myślę, i można było powiedzieć, że rachunek różniczkowy jest formalnym systemem rozumowania na temat równoważności programów. Programy mają semantykę operacyjną określoną przez maszynę, która powinna (myślę?) Być deterministyczna. W ten sposób (poprawny) rachunek różniczkowy dla …
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.