Strategie utknięcia w zrozumieniu TCS

19

Jestem studentem kończącym kurs teorii teorii i mam poważne problemy z tworzeniem treści, gdy tylko o to poproszę. Potrafię śledzić podręcznik (Wstęp do teorii obliczeń Michaela Sipsera) i wykłady; jednak kiedy poproszono mnie o udowodnienie czegoś lub sformułowanie formalnego opisu konkretnej bazy TM, po prostu dusiłem się.

Co mogę zrobić w takich sytuacjach? Wydaje mi się, że mój problem polega na pełnym zrozumieniu abstrakcyjnych koncepcji do tego stopnia, że ​​mogę ich właściwie użyć. Czy istnieje ustrukturyzowany sposób podejścia do nowej, abstrakcyjnej koncepcji i zbudowania intuicji?

computability  education  intuition 
— trigoman
źródło
5
bije mnie. wydaje się to rozsądnym pytaniem dla tej witryny.
— Suresh
4
Głosowałem za zamknięciem. Głównym problemem, jaki widzę, jest to, że pytanie nie dotyczy tak naprawdę informatyki; chodzi o naukę informatyki. Ta ostatnia nie ma obiektywnej odpowiedzi, ponieważ każda osoba będzie miała swój najlepszy sposób. Trzy głosy do zamknięcia są przypisane do powodu „zbyt zlokalizowanego”, ale myślę, że to pytanie również nie jest tematem, ponieważ nie dotyczy informatyki.
— Carl Mummert
1
Myślę, że to pytanie ma sens i jest rodzajem pytania, z którym zmagam się intensywnie. Myślę, że uzyskanie wskazówek na temat tego rodzaju problemów od zaufanej społeczności to problem, z którym zmaga się wielu studentów CS. Rozumiem jednak sprzeciw wobec pytania. Wydaje mi się jednak, że pytanie jest dość trafne w stosunku do sekcji meta tej witryny.
— BrotherJack
6
@CarlMummert: Każde pytanie dotyczące informatyki jest pytaniem, jak się uczyć informatyki.
— JeffE
2
Pytanie jest zbyt ogólne w obecnej formie. Skoncentruj swoje pytanie, np. Poproś o zasoby (np. Książki problemowe), aby poprawić swoją zdolność do rozwiązywania pytań w trakcie kursu, lub jeśli masz konkretny przykład, skup się na tym problemie i zapytaj o intuicję lub metody rozwiązania podobnych problemów.
— Kaveh

Odpowiedzi:

15

Abstrakcja to właściwie chleb powszedni w informatyce, ale niestety trudno jest uczyć tego wprost.

Moim zdaniem zrozumienie pojęć jest ważniejsze niż umiejętność mechanicznego obliczania lub udowodnienia różnych rzeczy. Jasne, musisz znać swoje podstawowe metody, ale mięso leży gdzie indziej.

Przede wszystkim musisz w pewnym stopniu zrozumieć treść. W tym celu uznałem, że warto zadać następujące pytanie, gdy coś jest dla ciebie niejasne:

  • Dlaczego to robimy?
  • Do czego będziemy tego używać?
  • Jakie podobne rzeczy to dotyczy?
  • Jak wyjaśniają to inne źródła ?
  • Czego dokładnie nie rozumiem?

Po udzieleniu odpowiedzi na te pytania (lub odkryciu pytań uzupełniających i potraktowaniu ich w ten sam sposób) i nadal napotkaniu problemów, idź do nauczycieli (lub tutaj). Do tej pory powinieneś być w stanie sformułować skoncentrowane, precyzyjnie sformułowane pytanie; odpowiadanie na takie pytania jest zadaniem nauczycieli (i filozofii StackExchange).

Poza tym są to ćwiczenia i doświadczenie. Spróbuj odtworzyć dowody po ich przeczytaniu; staraj się nie uczyć ich na pamięć, ale wypisz z nich ważne pomysły. Po pewnym czasie powinieneś być w stanie odtworzyć wszystkie podstawowe dowody, wypełniając luki między głównymi krokami. Nawet później zaczniesz widzieć wzorce w oświadczeniach i dowodach. W ten sposób ludzie patrzą na stwierdzenie i mówią: „O tak, jasne, użyj metody X z twierdzeniem Y, a następnie po prostu użyj Z, aby uzyskać to, czego chcesz”. Jest to rozpoznawanie wzorców napędzane latami szkolenia. Bądź cierpliwy.

Jeśli chodzi o podstawowe ćwiczenia, idź i znajdź podręczniki z niektórymi. Z czubka głowy mogę odnieść się do konkretnej matematyki autorstwa Grahama, Knutha i Patashnika. Ta książka jest nie tylko cennym zestawem narzędzi dla informatyków, ale zawiera także mnóstwo ćwiczeń z rozwiązaniami (!). Pamiętaj, aby spróbować je rozwiązać przed wyszukaniem odpowiedzi i odtworzyć odpowiedzi, które musiałeś wyszukać.

Inną przydatną książką jest Wprowadzenie do algorytmów autorstwa Cormena, Leisersona, Rivesta i Steina. Zawarty jest spory rozdział na temat podstaw matematyki. Zawiera również wiele ćwiczeń; rozwiązania są dostępne poprzez link do strony (treść uzupełniająca). Jest też wykład wideo jednego z autorów, który może pasować do książki.

Aby zapoznać się z wykładami wprowadzającymi dotyczącymi dowodów, zobacz Algebra Linear Proofs w Khan Academy . Nie oglądałem ich, ale mam nadzieję, że są one zarówno podstawowe, jak i pomocne. Istnieje wiele innych dowodów na Khan Academy; Wydaje mi się, że dowody algebry liniowej najlepiej pasują do informatyki. Nie wahaj się też obserwować innych.

— Raphael
źródło
7
Zgadzam się, że zrozumienie pojęć jest ważniejsze niż umiejętność obliczania lub udowadniania rzeczy. Ale zrozumienie jest wynikiem praktyki z obliczeniami i dowodami, a nie substytutem tej praktyki.
— JeffE
Dziękuję za wgląd. Skorzystam z twojej rady i na tej podstawie postaram się ją ulepszyć.
— trigoman
Dla bardziej podstawowych potrzeb Księga Dowodu może być cennym odniesieniem.
— Raphael
8

Czasami dowiaduję się, że ludzie, którzy nie radzą sobie dobrze w teorii, po prostu mylą się z podstawami (podczas pierwszych 1-3 wykładów myśleli, że materiał jest bardzo łatwy, więc nie zwracali zbytniej uwagi, ale potem, na wykładzie 5-7 rzeczy przyśpieszają i jest za późno na podsumowanie).

Jak powiedział @fbernardo, dobrym pomysłem może być rozpoczęcie od początku. NIE tak dalece jak FLA (nie ma to sensu podczas nauki TC, IMHO), ale zdecydowanie otwórz Sipser i zacznij rozwiązywać pytania jeden po drugim, według ich kolejności. Dzięki temu zdobędziesz intuicję i podstawowe narzędzia, które są niezbędne w przypadku bardziej zaawansowanych koncepcji.

Jeśli nie potrafisz poradzić sobie z podstawowymi pytaniami Sipsera z pierwszego rozdziału (nie z rozdziałami automatów, jeśli studiujesz na bazach TM), być może brakuje Ci jeszcze bardziej podstawowych pojęć, takich jak podstawowe metody dowodzenia (indukcja itp.) Lub podstawowy zestaw teoria i dyskretna matematyka.

W każdym razie powodzenia!

— Ran G.
źródło
3

Moja jedyna rada jest taka, że ​​zaczynasz od początku. W moim kursie również korzystamy z książki Sipsera, moim zdaniem jest to dobra książka. Ale mamy kurs przed TC, nazwany FLA (Formal Languages ​​an Automaton), który dał lepszą intuicję i doświadczenie w TC. I znowu wszyscy uczą się w różnym tempie, a ty masz bardzo dobrą książkę. Wszelkie inne szczegółowe pytania zawsze znajdziesz tutaj. :)

— Fbernardo
źródło
2

W tytule zadajesz ogólne pytanie, a następnie co najmniej dwa podstawowe / konkretne punkty w pytaniu i myślę, że na każde z nich są dobre (osobne) odpowiedzi:

  • jak udowodnić rzeczy
  • stworzyć formalny opis zachowania bazy TM

Tutaj dotyczy tylko pierwszego przedmiotu (który z natury jest szeroki i zasługuje na niego) - swego rodzaju słonia w pokoju edukacji STEM (nauk ścisłych, technologii, inżynierii, matematyki), która szybko się kręci i jest często oszałamiana do oszałamiającego stopnia . Może się wydawać, że nikt tak naprawdę nie wie, jak uczyć budowania dowodów. Ta gra zaczyna się od klas geometrii, trygonometrii i rachunku różniczkowego, ale rzadko jest jej ścisłym elementem. większość nauczycieli traktuje to jako opcjonalne. Wydaje się, że cała klasa poświęcona „jak udowodnić rzeczy” byłaby doskonałym, a nawet krytycznym dodatkiem lub zmianą w edukacji STEM.

Oto kilka referencji, które znalazłem podczas szybkiego wyszukiwania, jak udowodnić różne rzeczy, i myślę, że istnieje wiele innych dobrych zasobów. W dzisiejszych czasach prawdopodobnie jest też wiele filmów na ten temat, które można by znaleźć za pomocą wyszukiwań, ale nie widziałem ładnej, kompleksowej organizacji filmów typu „jak udowodnić rzeczy”.

Kluczową częścią udowodnienia jest opanowanie podstaw matematyki i wykorzystanie jej jako narzędzi lub elementów budowlanych. Na przykład wiedz, czym jest zestaw, czym jest krotka, jaka jest różnica / podobieństwo, kiedy użyjesz jednego, ale nie drugiego itp.

Innym podejściem jest traktowanie go jak ćwiczenia. Zrób wiele próbnych prób samodzielnie, zaczynając od łatwych do trudnych (szkoda, że ​​nie znam więcej takich książek, wydaje się, że nie ma ich wiele).

— vzn
źródło
1
Dodaj klasyczny Pólya „Jak to rozwiązać”. Przydatne jest również (szczególnie dla absolwentów) rozglądanie się za pisaniem matematyki, np. Knuth i wsp. „Pisanie matematyczne”. Jest to umiejętność zbyt często brana za pewnik.
— vonbrand
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.