[re] GRE Subject Topics > 자료실

본문 바로가기
사이트 내 전체검색


새창에서 채팅하기
자료실

[re] GRE Subject Topics

페이지 정보

작성자 csuhak 작성일09-10-27 01:46 조회5,985회 댓글0건

본문

이쪽에 포스팅을 원하신 것 같아서 원본글 복사해옵니다.
-------------------------
GRE Subject - Computer Science

2009-05-13 10:11 pm | Uncategorized | none

지난 달 초에 본 시험 결과가 오늘 도착했다. 880점에 99%. 90%만 넘으려고 했었는데 뽀록이 정말 제대로 터져주었다 -_- 작년 8월 GRE General 시험에서 후기 못 타고 리딩 롱이 5번에 나올 때 비축되었던 운을 다 써버린 듯하다. 70문제 중에 3문제는 몰라서 답을 안 썼고 (틀리면 0.25점씩 감점이 있다) 답을 기입한 것 중에 4개 틀렸다. 지금 생각해도 아리까리해서 찍었던 게 4문제는 넘었던거 같은데 흠.

늦게 전산과로 전과를 했고, 아직 수강하지 못한 필수 전공 과목(OS, Network 등)이 몇 개 있어, 혹시 그것 때문에 불이익이 있지 않을까 하는 노파심에서 보게 된건데, 그 정도 목적은 달성한 거 같다. 지금 생각해보니 정말 부질없는 생각이다 -_- 뭐 한줄이라도 더 쓸게 생겼다는 데 의의를 둔다.

공부하려고 하는 분야인 AI 관련 강의노트나 논문 같은거 찔끔찔끔 보면서, 3년 동안 내 머리 속에서 사라져버린 수학 개념을 비롯하여, 그 ‘익숙하지 못함’에 상당히 좌절하고 있는 상황에서, 그나마 힘을 주는 결과가 날아와 줘서 다행이다. 조지아텍에서 박사과정 중이신 김민장 씨가 관련 글에 서 언급했듯이, 이 점수가 어드미션에 미치는 영향은 정말 미미할 것임을 알지만, 희미하고 얄팍하게 알고 있던 전공 관련 지식들을 한번에 정리할 수 있어서 좋았던 것 같다. 몇 달 뒤에 치를 고등교육재단 전공시험(그것도 별 변별력은 없다지만) 에 대한 대비도 되었고.

그런 의미에서, 성재와 김민장 씨가 그랬던 것처럼, 나도 후배들을 위해 관련 내용을 간단히 정리해보려고 한다. (스스로도 몇 달 후에 써먹을 수 있을 것도 같고 -_-)
준비

기본적으로 코드를 주고 결과값을 예상하는 문제가 5문제 정도는 된다. 머리 속에서 코드를 빠르고 ‘실수없이’ 돌리는 것이 중요하다. 나머지 문제들 중에서는 알고리즘, 오토마타, OS, Architecture가 상당 부분을 차지하고, 그외 토픽에서는 조금씩 골고루 출제된다. 모든 토픽에 대해 상세히 공부할 수는 없고 무엇보다 중요한 내용이 아닐 경우에 깊은 지식을 요구하는 경우는 드물기 때문에, 위에서 언급한 4개 부분에 대해서만 자세히 보고, 나머지는 토픽과 그 개념 정도만 이해하고 넘어가는게 효율적이다. 예를 들어 이번 시험에 Buddy Memory Allocation에 대해서 나왔는데, 뭔지 몰라서 찍지도 못했다 -_- 아마 이게 뭔지만 알고 갔어도 90% 맞출 수 있었을 거다.

실제 시험에서 가장 중요한 것은 ‘실수를 하지 않는 것’이다. 어려운 문제 푸느라 끙끙대는 것보다 쉬운 문제를 정확히 풀었는지 검산 한 번 더 하는게 이득일 수도 있다. GRE Subject 중 Computer Science가 통계상 평균이 가장 높고 분산이 상대적으로 작다. 그래서 평균 지점 근방에서는 1~2문제가 상당히 크게 작용할 수 있다. (각 문제당 배점이 모두 똑같다) 2시간 50분이 주어지지만 체감상 시간이 조금 부족하게 느껴지므로 미리 연습을 해보는게 좋다.

그리고 왠만하면 스터디를 구성해 공부하는 걸 추천한다. 나는 같이 할 멤버가 마땅치 않아 혼자 했지만(JP와 OS만 했음), 역시 혼자서 하는 건 자극도 덜하고 어려운 개념에 대한 이해도 느리다.
참고자료

GRE General과 가장 큰 차이점은 자료가 충분하지 않다는 것이다. 정확히 말하자면, 자료 자체는 널려있지만 ‘무엇을’ 공부해야 할지에 대한 감이 별로 없고, 그렇게 주먹구구로 공부한 것을 테스트할만한 문제셋이 충분하지 않다. 공식적으로 ETS에서 제공하는 모의고사 문제셋이 있긴 한데, 70문제 뿐이다.

기본적으로 학교 때 각 과목 수업에서 사용했던 교재들로 공부하면 무리가 없다. 최신 토픽이나 설명이 부족한 부분은 Google + Wikipedia ( + Wolfram) 조합으로 무조건 해결 가능하다.

위에서 언급한 성재와 김민장씨 포스팅에 링크되어 있는 것들이 우선 큰 도움이 된다.

    * http://csuhak.info : CS 유학 커뮤니티 사이트
    * http://www.cc.gatech.edu/~howardz/micellaneous/gre_cs_sub/ : ETS에서 공개한 토픽 출제 범위별로 링크 정리
    * http://titanium.bits.googlepages.com/ : CMU 대학원생이 만든 모의고사 문제 & 솔루션

3번째 링크의 자료는 개인이 만든 것 치고는 상당히 완성도가 높다. 아래는 내가 참고했던 자료를 이것저것 짬뽕한 것이다. 위 링크에서 받을 수 있는 자료 외에 렉처노트 등이 포함되어 있다.

    * http://mjipeo.net/study/GRE_Subject_CS.zip

주제

나름대로 중요하다고 (자주 출제되었다고) 생각되는 순서대로 정리했다. 개념만 공부해도 될 토픽과, 깊이 있게 이해해야 하는 토픽을 잘 구분하는 센스가 필요하다. 예를 들어 NP-Complete나 Turing Machine은 자세히 알고 있지 않으면 건드리지도 못할 문제가 꽤 있는 반면, RSA 알고리즘은 원리보다는 어떤 식으로 계산하는지만 알아도 된다.

    * Algorithm
          o Basic Data Structures
                + Linked List, Tree, Graph, Hash Table, Heap, Binary Search Tree
          o Advanced Data Structures
                + Binomial Heap, Fibonacci Heap, Red-Black Tree, AVL Tree, B-Tree, Disjoint Set
          o Analysis
                + Order of Growth (Big-O, Big-Theta, Big-Omega)
                + Recurrence Equation
                      # Master Theorem
          o Sorting
                + Bubble, Selection, Insertion, Shell, Heap, Merge, Quick, Bucket, Counting, Radix
          o Order Statistics
          o Dynamic Programming & Greedy Algorithm
          o Amortized Analysis
          o Graph
                + Representation
                      # Adjacency Matrix, Adjacency List
                + Traverse
                      # Inorder, Preorder, Postorder
                + DFS
                      # Edge Classification
                            * Tree, Back, Forward, Cross Edge
                + BFS
                + Minimum Spanning Tree
                      # Kruskal, Prim
                + Shortest Path
                      # Single Source
                            * Bellman-Ford, Dijkstra
                      # All Pair
                            * Floyd-Warshall, Johnson
                + Maximum Flow
                      # Ford-Fulkerson
                + Others
                      # SCC (Strongly Connected Component)
                      # Topological Sort
                      # Bipartite (Bigraph)
                      # Planar Graph (Euler’s Formula)
          o String Matching
                + Rabin-Karp
                + Finite State Automaton
                + KMP
          o NP Theory
                + P, NP, Co-NP, NP-Hard, NP-Complete, Reducibility
          o Matrix Algorithms
          o Approximation
          o Linear Programming
                + Simplex Method
    * Automata & Formal Language
          o Finite Automata
                + DFA, NFA, e-NFA
                + Regular Language & Expression
                + Pumping Lemma for RE
          o Pushdown Automata
                + DPDA, NPDA
                + Context Free Language & Grammar
                + Pumping Lemma for CFG
          o Turing Machine
                + NTM, DTM
                + Recursively Enumerable Language
                + Recursive Language
          o Reducibility
          o Computability (Recursively Enumerable)
          o Decidability (Recursive)
                + Rice’s Theorem
                + Halting Problem
          o Church-Turing Thesis
    * Operating Systems
          o Basics
                + Process
                      # Process Migration
                + Thread
                      # User Thread, Kernel Thread
          o Process Management
                + CPU Scheduling
                      # FCFS, SJF, RR, Priority, Multiple Priority Queues, Interitance
                            * Priority Inversion
                            * Spin-Wait
                + Concurrency
                      # Baker’s Algorithm
                      # Hardware Support
                            * Test-And-Set Instruction
                      # Semaphore, Monitor, Mutex
                      # Deadlock
                            * 4 Conditions for Deadlock
                            * Banker’s Algorithm
                            * Wait/Die & Wound/Wait
          o Memory Management
                + Addressing Modes
                      # Direct, Indirect, Register, Immediate
                + Page & Segment
                      # Page Fault
                      # Page (Table) Size & Multilevel Page Table
                + Swapping
          o Disk Management
                + Disk Scheduling
                      # FCFS, SCAN
                + Capability vs ACLs
    * Architecture
          o Number Representation
                + Floating Point (IEEE-754)
                + Arithmetic Overflow
          o Digital Logic
                + Flip-Flop Circuit
                + Karnaugh Map
          o RISC
          o Horizontal & Vertical Microarchitecture
          o Alignment (Data Structure Alignment)
          o Amdahl’s law
          o Parellelism
                + Hazard
                      # Data, Structural, Control
                + Out-of-Order
                + Superscalar
                + Register Renaming
                + Branch Prediction
          o Cache
                + Cache Misses
                      # Compulsory, Capacity, Conflict
                + Unified/Split Cache (Instruction, Data)
                + Multilevel Cache (L1, L2)
                + Cache Coherency
                      # MSI, MESI, MOSI, MOESI
                      # Directory-based & Snooping
    * Discrete Mathematics
          o Relation
                + Injection, Surjection, Bijection
                + Partial order, Total order, Equivalence relation
          o Countability
          o First Order Logic
          o Generating Function
          o Recurrence Equation
                + Master Theorem
          o Resolution Theorem
    * Information Theory
          o Hamming Distance
                + Error Detection & Correction
          o Graycode
          o Encoding (Compression)
                + Huffman Code
                + Run-length Encoding
                + Lempel-Ziv-Welch Encoding
    * Programming Language
          o Lambda Calculus
          o Continuation
          o Currying
          o Closure
          o Variable Scope
          o Parameter Passing
                + Pass By Value
                + Pass By Reference
                + Pass By Name
                + Pass By Value Result
          o Garbage Collection
                + Mark and Sweep
                + Stop and Copy
                + Reference Counting
    * Network
          o Circuit-Switched vs Packet-Switched
          o OSI Layer Model
                + Link Layer
                      # Ethernet
                            * Fast Ethernet
                            * Gigabit Ethernet
                + Network Layer
                      # IP
                            * IP Fragmentation
                      # ARP (Address Resolution Protocal)
                + Transport Layer
                      # TCP
                + Application Layer
                      # HTTP, FTP, DNS, SMTP, SNMP
    * Security
          o Public Key
          o OTP (One Time Password)
          o RSA
          o Integer Factorization
    * Database
          o Primary Key
    * Numerical Analysis & Probability Theory
          o Bayes’ Theorem
          o Euclidean Algorithm
          o Sieve of Eratosthenes
          o Root Finding Algorithm
                + Newton’s Method
                + Method of False Position
                + Bisection Method
                + Secant Method
    * Compiler
          o Top Down & Bottom Up Parsing
          o LALR, SLR, LR, LL
          o Left Recursion
    * Software Engineering
          o Design Patterns
                + Singleton, Factory, Adapter, Bridge, Composite, Decorator, Facade, Proxy, Command, Iterator, Observer, State, Strategy, Template Method






>안녕하세요.
>
>GRE Subject (CS) 관련해서, 이곳에서 많은 도움을 얻었던지라, 뒤에 준비하시는 다른 분들에게 조금이라도 도움을 드리고자 공부했던 내용을 정리해 보았습니다.
>
>자료실에는 보안코드 어쩌고 하면서 안써지고, 이곳은 HTML 이 잘 안먹네요 -_-a 그래서 제가 블로그에 썼던 포스팅을 링크해 드립니다.
>
>http://mjipeo.net/?p=338#topic
>
>그럼 모두 건승하십시오!

* csuhak님에 의해서 게시물 이동되었습니다 (2009-10-27 01:48)
추천 0

댓글목록

등록된 댓글이 없습니다.


접속자집계

오늘
107
어제
104
최대
442
전체
320,085
Copyright © 2000-2015. csuhak.info. All rights reserved.
상단으로
모바일 버전으로 보기