Jaki jest kawałek teorii komputerowej, którą powinienem znać? [Zamknięte]

27

Mówiąc jako ktoś z wykształceniem elektronicznym, a nie informatykiem, jaki jest kawałek informatyki, który powinienem wiedzieć, aby uczynić mnie lepszym programistą w świecie rzeczywistym ?

(W prawdziwym świecie mam na myśli coś, z czego zamierzam korzystać i czerpać korzyści w codziennej pracy jako programista - na przykład sugeruję, że zrozumienie normalizacji bazy danych jest bardziej praktyczne niż zrozumienie szybkiego sortowania, dla którego jest wiele bibliotek).

Jon Hopkins
źródło
42
1 (przepraszam, musiałem)
Haylem
5
och, lub najbardziej znaczący! (Pójdę teraz ...)
środa,
Wymiana stosów teoretycznych informatyki potwierdza to, o czym wspominają wszyscy inni: złożoność, struktury danych i algorytmy. cstheory.stackexchange.com/tags
chrisaycock
2
Czuję potrzebę sprzeciwienia się temu pytaniu. Nie ma „jednego bitu”, który byłby wystarczający do nauki, a ponadto nie ma (IMHO) jednego „najważniejszego” bitu. Istnieje kilka aspektów, które są (ponownie, IMHO) równie istotne dla CS. Myślę więc, że chociaż odpowiedzi na to pytanie mogą być interesujące, pytanie można sformułować lepiej.
Konrad Rudolph,
1
Gdybyś nie miał swojego eenga, powiedziałbym logikę boolowską i / lub teorię liczb dyskretnych. Prawie każde ifi loopkiedykolwiek napisane oświadczenie wykorzystuje podzbiór tych dwóch obszarów badań.
Steven Evers,

Odpowiedzi:

52

Jeśli mam do wyboru tylko jeden bit, która jest trudna decyzja, powiedziałbym przejść do notacji Big O . Zrozumienie implikacji O (n), O (ln n), O (n²), O (2 ^ n), O (n!) Pomaga uniknąć wielu kosztownych błędów, które działają dobrze w środowisko testowe, ale katastrofalnie zawodzi w produkcji.

użytkownik 281377
źródło
2
+1 i powiedziałbym, że ważniejsze niż sama wiedza, że ​​O (n ^ 2) jest gorszy niż O (lg n) (na przykład), to umiejętność wyprowadzenia Big-O dla danego fragmentu kodu.
Dean Harding,
3
Nie zgadzam się zdecydowanie. Te rzeczy są stosunkowo trywialne, aw CS jest więcej interesujących tematów. Sądzę też, że większość ludzi myśli o złożoności intuicyjnie, chociaż może nie nazwać go złożonością i nie nazwać go kwadratowym, wykładniczym itp.
Magnus Wolffelt
Magnus: Z mojego doświadczenia wynika, że ​​większość osób niebędących programistami wcale nie myśli o złożoności, intuicyjnie zakłada O (n) dla wszystkich problemów.
user281377,
Muszę jeszcze tego formalnie potrzebować.
CaffGeek,
1
Chad: W wielkim zapisie O nie ma nic, co byłoby zbyt formalistyczne, ale bez nazw rzeczy trudno o tym myśleć, a co dopiero rozmawiać o tym z rówieśnikami.
user281377,
19

To pytanie, na które każdy będzie miał inną odpowiedź. Powiedziałbym: teoria złożoności jest najważniejszym elementem, którego i tak nie uczysz się bezpośrednio jako programista (jak algorytmy i struktury danych), ale co może wpłynąć na twoją pracę. Pomaga, jeśli wiem, że problem ma złożoność sześcienną, wiem, że będzie źle skalowany, jeśli rozmiar problemu zostanie zwiększony.

Memento
źródło
Dodałbym, że bardzo pomaga wiedzieć, czy rozwiązujesz problem, który można łatwo odtworzyć w prostszym języku.
Philodad
Złożoność jest ważna jako koncepcja, ale w rzeczywistości jej obliczenie często nie jest. Ważne jest zrozumienie, co jest mniej złożone.
Bill
@Bill: Dokładnie. Ale ta część jest jedyną rzeczą, której niekoniecznie musisz przejść przez praktykę. Teoria jest bardzo pomocna z tej strony.
Mnementh,
12

Dowiedz się o strukturach danych, algorytmach i złożoności.

Nie za dużo, aby zrozumieć, że maszyna nie jest magicznym pudełkiem o nieograniczonej mocy. Nie możesz w to cokolwiek rzucić i spodziewaj się, że rozwali to w milisekundach. Ma ograniczenia, które znasz. Musisz nauczyć się nie testować ich za pomocą kodu.

Zapoznaj się również z powszechnymi podejściami do rozwiązywania konkretnych problemów projektowych w programowaniu. Wzory projektowe mianowicie. Nie czcij ich, po prostu weź pomysły, które przekazują.

Niezbędna jest również znajomość modelowania baz danych.

Potem są to tylko różne języki programowania, frameworki i biblioteki, które implementują lub umożliwiają implementację podstawowych pojęć. Wybieraj co chcesz i ćwicz z nimi.


źródło
Specyfika - istnieje wiele algorytmów i struktur danych.
Jon Hopkins,
Tylko te podstawowe, które pozwolą Ci zrozumieć rzeczy. Podnieś niezbyt grubą książkę i przeprowadź ją.
1
To trochę więcej niż jeden bit.
7

To trochę trudne pytanie.

Wszystkie aspekty informatyki są ważne w taki czy inny sposób.

Jeśli chodzi o to, co zyskasz na co dzień, prawdopodobnie ogólny przegląd tego, jak Twój kod działa „pod maską” od kodu do procesora.

Zrozumienie Big O Notation jest ważne, a także zrozumienie, w jaki sposób można wykonać kod, jest również bardzo ważne w rzeczywistych sytuacjach.

Ciemna noc
źródło
7

Tak, to zmusiło mnie do myślenia przez wiele godzin.

W trakcie tego procesu musiałem usunąć niektóre typowe odpowiedzi podane tutaj.

BRAK LISTY

  1. Duża notacja O (n) . Trudno to tutaj umieścić, ale nie, możemy intuicyjnie wypracowywać nieefektywności i porównywać różne zestawy procedur, nawet nie słysząc zdalnie o asymptotycznej analizie algorytmicznej.

  2. Języki funkcjonalne Nie, jedna rodzina języków to tylko jedno podejście do myślenia o problemach. Dlaczego tylko ten kawałek powinien mieć znaczenie?

  3. Zatrzymanie Problem Niektóre są po prostu zbyt specyficzne, a ludzie żyli życiem, nie wiedząc o ich istnieniu.

  4. Słuchaj Jeśli nie słuchasz, żyjesz w swoim własnym świecie. Niekoniecznie szkodliwe!

  5. Cykl rozwoju oprogramowania Nie! Nadal możemy natknąć się na niesamowite oprogramowanie lub heroiczny wysiłek solo.

  6. Teoria złożoności Chyba tak, ale bez formalności

Ten mały pomysł z Comp Science

Powiedziałbym - „ Abstrakcje Abstrakcje Abstrakcje ... ”. Dowiedz się o tym. Zobacz przykłady wokół niego i dowiedz się, jak budować z niego. To jest wszędzie. Całość informatyki, inżynierii i aplikacji wygląda jak warstwa po warstwie abstrakcji.

Gdy się o tym dowiesz, zaczniesz uczyć się dobrze rozglądać.

Gdy zobaczysz, że ktoś używa list insertionw pythoni not append, uśmiechasz się, ponieważ wiesz, że listy Pythona są tworzone przy użyciu abstrakcji tablic, w których wstawianie jest kosztowne i dołącza tańsze.

To tylko jeden przykład.

pyfunc
źródło
+1 za odpowiedź, którą oczywiście przemyślałeś.
Jon Hopkins,
tylko komentarz do twojego komentarza na temat problemu „Stop”: „Życie życiem bez wiedzy o istnieniu” jest prawdą dla KAŻDEGO tematu informatyki.
4

Teoria automatów i FSM. :-)

Prasoon Saurav
źródło
3

Konkurencyjne przypadki wykorzystania struktur danych.

Są sytuacje, w których mapa z czerwono-czarnymi drzewami jest wymagana, aby zagwarantować wydajność, i inne, w których nie można użyć tablicy, ponownie, aby zagwarantować wydajność. Wiedza, kiedy wybrać, która struktura danych jest nieocenioną umiejętnością.

Fanatyk 23
źródło
3

liczą się tylko trzy liczby:

  • zero
  • jeden
  • wiele
Steven A. Lowe
źródło
ale czy to nie oznacza, że ​​„3” też ma znaczenie?
Javier,
To ma być zero, jeden i nieskończoność: en.wikipedia.org/wiki/Zero_One_Infinity
Thomas Owens
@Javier: 3 to podzbiór wielu
Steven A. Lowe
@ Thomas: mówi kto?
Steven A. Lowe,
@Steven Nie rozumiem tutaj w 100%, ale myślę, że chodzi o to, że nie masz nic, ani jednej rzeczy, ani liczby rzeczy, które powinieneś mieć nieograniczony. Jeśli nie ograniczasz się do żadnej lub jednej instancji, nie powinieneś ograniczać instancji. Nie jestem jednak do końca pewien, DLACZEGO tak jest (jestem tylko niejasno zaznajomiony z koncepcją Zero / One / Infinity).
Thomas Owens
3

Najważniejszą rzeczą, której nauczyłem się w CS (i jako programista od wielu lat i jako architekt), jest umiejętność rozwiązywania problemu na podstawie zmienności, a nie funkcji. Wszystkie dobre projekty izolują i zamykają lotność. Wszyscy dobrzy programiści / architekci robią to intuicyjnie, nawet jeśli nie sformalizowali tego w swoich myślach. Ogromnym powodem niepowodzenia projektu jest niemożność rozwiązania problemu na podstawie zmienności i hermetyzacji. Brak enkapsulacji zmienności nieuchronnie prowadzi do ucieczki złożoności i niepowodzenia projektu.

JP Alioto
źródło
Co dokładnie rozumiesz przez zmienność?
amara
3

Problem zatrzymania

Fakt, że istnieją problemy związane z komputerem, których komputer po prostu nie może rozwiązać.


źródło
3

Powinieneś znać wystarczającą teorię automatów, aby wiedzieć, gdzie problem, z którym masz do czynienia, należy do hierarchii języków formalnych. Na tej podstawie możesz dowiedzieć się kilku ważnych praktycznych zastosowań, na przykład dlaczego nie powinieneś używać REGEX do analizowania HTML (HTML potrzebuje gramatyki bezkontekstowej, aby go opisać) i dlaczego kompilacja C ++ zajmuje dużo więcej czasu niż Java lub C # (C ++ wymaga maszyny Turinga, natomiast Java i C # można opisać za pomocą gramatyki bezkontekstowej).

Najważniejsze poziomy języków formalnych, od najsłabszych do najsilniejszych:

  1. Języki, które mogą być analizowane przez skończone automaty lub REGEX (implementacje REGEX z referencjami wstecznymi są potężniejsze niż ta kategoria, ale nadal nie mogą analizować wszystkiego w kategorii 2)

  2. Języki, które mogą być analizowane przez automaty z pamięcią stosu lub gramatyką bezkontekstową.

  3. Języki, które mogą być analizowane przez maszynę Turinga lub automaty z pamięcią o swobodnym dostępie.

Dan Monego
źródło
Yyy ... nie. Wyrażenie regularne analizuje gramatykę regularną. Jest to dokładnie kategoria gramatyki, którą mogą zaakceptować automaty skończone. A „Gramatyka Chomsky'ego” nie odnosi się wyłącznie do gramatyki bezkontekstowej, którą przetwarzają maszyny stosowe.
Philodad
@philosodad - Gramatyka bezkontekstowa jest bardziej precyzyjna i zaktualizowałem post, aby używał tego terminu. Nie rozumiem twojego problemu z tym, co powiedziałem o wyrażeniach regularnych.
Dan Monego,
@Dan - Moim problemem jest to, że wyrażenie regularne jest tak samo potężne jak automaty skończone i jeśli potrafisz analizować KAŻDĄ deterministyczną gramatykę bezkontekstową za pomocą maszyny, to nie możesz analizować WSZYSTKICH gramatycznych deterministycznych bezkontekstowych.
Philodad
Lub, mówiąc dokładniej: albo potrzebujesz stosu, albo nie. Jeśli potrzebujesz stosu do parsowania języka, musisz mieć stos do parsowania języka, a zatem, jeśli język wymaga stosu do parsowania go, możesz parsować ten język.
Philodad
@ philosodad - Istnieją dwa rodzaje wyrażeń regularnych - wyrażenia regularne w teorii i wyrażenia regularne zaimplementowane w oprogramowaniu. Masz rację co do teoretycznych wyrażeń regularnych, ale większość implementacji ma kilka funkcji wykraczających poza ich teoretyczne podstawy i może pasować do niektórych nieregularnych języków, takich jak ^ n dla liczb pierwszych. Ponieważ jest to wątek dotyczący teorii w praktyce, starałem się wspomnieć, że istnieje różnica między definicją formalną a definicją używaną w środowisku naturalnym.
Dan Monego,
2

Cóż, mógłbym dać tępą odpowiedź: teoria automatów i teoria informacji.

Albo mogę powiedzieć, czego nauczyłem się od konsultanta sprzętowego dawno temu:

  • „Good Enough” to za mało.
Mike Dunlavey
źródło
1

Cykl życia oprogramowania to coś, co sugeruję wiedzieć, jeśli jeszcze tego nie zrobiłeś. To prawda, że ​​wprowadzono go na drugim roku kursu informatyki i jest on wielokrotnie wykorzystywany w projektach oprogramowania. Może to być przydatne, aby uzyskać ogólne pojęcie o tym, jak przebiega projekt od początku do końca, ale jeśli chcesz bardziej dogłębnie, istnieją metodologie takie jak Waterfall lub Agile, które możesz studiować, aby uzyskać bardziej szczegółową wiedzę.

JB King
źródło
2
Prawo Murphy'ego: wszystko, co może pójść nie tak, pójdzie nie tak
Richard
To nie jest teoria CS, ale to doskonała odpowiedź.
justkt
1

Programowanie

Z Wydziału Matematyki i Informatyki Hobart i William Smith Colleges pochodzi informatyka 124 Wprowadzenie do programowania :

Tematy obejmują struktury kontrolne, obiekty, klasy, dziedziczenie, proste struktury danych oraz podstawowe pojęcia dotyczące tworzenia oprogramowania.

Jeśli nie umiesz programować, nie zajdziesz daleko w świecie komputerów.

I tak, zauważyłem, że jesteś programistą. Ma to na celu podniesienie ogólnej wiedzy na temat teorii programowania i innych dostępnych metod.

Czy programowanie informatyki w takiej formie, w jakiej ją znamy?

W odpowiedzi na komentarz @Thomas Owens, który zauważył (całkiem słusznie), że programowanie nie jest wyłącznie informatyką, chciałbym zacytować z artykułu z Wikipedii :

... informatyka koncentruje się bardziej na zrozumieniu właściwości programów wykorzystywanych do wdrażania oprogramowania, takich jak gry i przeglądarki internetowe, i wykorzystaniu tego zrozumienia do tworzenia nowych programów lub ulepszania istniejących ...

Tak więc, jak czytam, programując, demonstrujesz swoje zrozumienie teorii programowania. To z kolei powinno pomóc w stworzeniu prostego, eleganckiego kodu, z którym inni mogą się cieszyć.

Gary Rowe
źródło
Programowanie nie jest teorią CS. W rzeczywistości mogę łatwo argumentować, że programowanie wcale nie jest informatyką.
Thomas Owens
@Thomas Owens Zaktualizowałem moją odpowiedź, aby wykonać kopię zapasową mojego twierdzenia, że ​​jest ona ważna. Czy mógłbyś to przejrzeć i dać mi znać o swoich przemyśleniach?
Gary Rowe,
1
Nadal nie sądzę, że programowanie to CS. Programowanie MOŻE być przydatne dla informatyków, którzy chcą wdrożyć algorytm lub strukturę danych, ale tematy w teorii CS (od mojego Wstępu do książki CS Teoria, więc prawdopodobnie są też bardziej zaawansowane tematy) obejmują logikę, teorię automatów, teorię grafów , obliczalność, złożoność obliczeniowa i analiza algorytmów. Powiedziałbym również, że języki programowania (teoria projektowania i wdrażania języka) są również częścią informatyki. Nie musisz jednak być w stanie być dobrym informatykiem.
Thomas Owens
@Thomas Owens Rozumiem twój punkt widzenia i (wkłada purystyczny kapelusz) zgadzam się. Jednak OP prosi o odrobinę CS, która pomogłaby mu w prawdziwym świecie. Mocno uważam, że teoria programowania (zaimplementowana w dobrym kodzie) jest tym samym. Zredagowałem nieco odpowiednio.
Gary Rowe,
Tak. Z CS powiedziałbym, że zrozumienie języków programowania i paradygmatów może pomóc (zwłaszcza jeśli wdrażasz DSL, ale znajomość wielu paradygmatów, takich jak logika proceduralna, funkcjonalna, OO, tylko pomaga w rozwoju oprogramowania). Zrozumienie algorytmów i struktur danych pomaga również wybrać odpowiedni (e), aby rozwiązać problem w najbardziej efektywny sposób. Teoria automatów może pomóc (kiedyś pracowałem z systemem, który był gigantycznym FSM, ale nie wiem, jak często to jest). Powiedziałbym więc, że struktury danych, algorytmy i teoria PL byłyby najbardziej użytecznymi rzeczami do poznania z CS.
Thomas Owens
1

Nie mogę się zgodzić z Konradem Rudolphem. Jest „odrobina” informatyki, którą powinieneś wiedzieć, aby uczynić cię lepszym „prawdziwym programistą”. Jeśli nie odbierzesz nic więcej od odpowiedzi, które tu otrzymujesz, przynajmniej weź to pod uwagę - Spełnienie wymagań NIE jest tym samym, co zadowolenie klienta! Użytkownicy końcowi ZAWSZE będą starali się używać twojego programu w sposób, o jakim nigdy nie myślałeś ani nie kodowałeś. ZAWSZE, ZAWSZE, ZAWSZE.

Dlatego, aby być lepszym programistą, musisz najpierw SŁUCHAĆ. Słuchaj klienta. Słuchaj ich potrzeb. Słuchaj ich życzeń. A zwłaszcza, słuchajcie ich poziomu „techniki”. Nie mogę powiedzieć, ile razy widziałem zbudowany projekt, który był dokładnie tym, o co prosiliśmy, ale wcale nie tym, czego właściwie potrzebował klient. Wszystko dlatego, że programista zbierający wymagania naprawdę nie słuchał.

Jeśli nie masz doświadczenia w projektowaniu interfejsu użytkownika, poproś kogoś, kto zaprojektuje interfejs użytkownika. ZAWSZE mogę dostrzec aplikację, w której interfejs użytkownika został zaprojektowany przez programistę, a nie eksperta. To, co jest logiczne i ma dla ciebie sens, nie będzie miało sensu dla klienta. A jeśli twoi klienci nie są tech saavy (a kto to jest?), Wtedy twoje „funkcjonalnie poprawne, ale estetycznie brzydkie” rozwiązanie spotka się z ciepłem skunksa na przyjęciu.


źródło
3
Ta odpowiedź nie dotyczy teorii CS, o którą pytał Hopkins.
James
1

Języki funkcjonalne!

Nauka języków funkcjonalnych sprawia, że ​​myślisz raczej w kategoriach wyrażeń niż kroków i nazwanych stanów zmiennych (zmiennych). Ma to znaczący wpływ na twoją zdolność skutecznego radzenia sobie z codziennymi problemami programistycznymi - zwłaszcza teraz, gdy prawie każdy popularny język ma funkcje funkcjonalne.

Algorytmy i teoria złożoności są również ważne, ale są nieco mniej interesujące, ponieważ pozwalają na umieszczanie nazw na rzeczach, które zwykle już znałeś i mógłbyś wywnioskować.

Magnus Wolffelt
źródło
0

Że komputery są w zasadzie dobieraczami wzorów, niczym więcej. Wszystko sprowadza się do maszyny Turinga - klasycznej koncepcji nauki komputerowej wyjaśniającej obróbkę wzoru.

therobyouknow
źródło
-2

Rozwiązywanie problemów i chęć kontynuowania nauki!

Służą mi znacznie lepiej niż znajomość szybkiego sortowania i normalizacji bazy danych.

Bryan Harrington
źródło
6
To nie jest teoria informatyki, mają one zastosowanie w równym stopniu do inżynierii elektronicznej (lub niemal każdej innej formy).
Jon Hopkins,
Moim zdaniem, biorąc pod uwagę twój przykład, znajomość szybkiego sortowania po prostu nie pomaga. Wiedza o tym, że istnieje i co sprawia, że ​​jest wyjątkowa, jest pomocna, ale jest też jedno wyszukiwanie google, jeśli nic o tym nie wiem. Znajomość jednego algorytmu też nie jest pomocna. Jednak wiedza o tym, jak je stworzyć i zinterpretować! Być może gdybym mógł zmienić swoją odpowiedź, złożoność jest prawdopodobnie najważniejsza.
Bryan Harrington,
1
Nie możesz szukać czegoś, jeśli nie wiesz, że go potrzebujesz lub że istnieje. Twoja odpowiedź wymienia ważne cechy, które powinien posiadać programista, ale nie odpowiada na postawione pytanie.
Adam Lear