Skip to content

Latest commit

 

History

History
155 lines (111 loc) · 3.25 KB

map-of-cs.md

File metadata and controls

155 lines (111 loc) · 3.25 KB
Raw

Map of Computer Science

Theoretical Computer Science

  • Graph Theory
  • Automata Theory
  • Quantum Computation
  • Parallel Programming
  • Data Structure
  • Formal Methods
  • ......

Alan Turing -> Turing Machine

... 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 ... // Infinitely Long Type
                    |----^----|             // Head --> Read & Move
                111010(B) = 58(Decimal)
                                            // State Register
                                            // 1. Replace/Erase
                                            // 2. L/F/N
                                            // 3. Keep/Change to another state

Hardware

Input, Output and Calculation(Lambda Calculus).

  • RAM
  • CPU
  • GPU
  • SSD
  • Power
  • Mouse & Keyboard
  • Sound & Monitor

Computational Complexity

Which problems can you solve with a computer?

How problems Scale?

1. Amount of memory
2. Number of steps
P versus NP problem

If the solution to a problem is easy to check for correctness, must the problem be easy to solve?

  • P: Solving the task that runs in polynominal time;
  • NP: Nondeterministic Polynmomial Time.
  • NP-Complete

Eg. for P =? NP: 53308290611 % 224737 = 0;
Eg. for NPC: Subset sum problem --> O(2^n);

Analysis of Algorithms

  • Bubble Sort -> O(n^2)

  • Merge Sort -> O(n*log(n))

Information Theory

Relating to Coding Theory.

Eg. 458. Poor Pigs

There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?

Answer this question, and write an algorithm for the general case.

Computer Engineering

How to slove the problem by computers?

Scheduling

    Steam      Videos      Browser      Music      // Processes
[________________________________________________]
                        |
                    Scheduler --> CPU(1,2,3,4....) // Multiprocessing

Computer Architecture

Central Processing Unit.

Input --> CPU --> Output
           |
        Memory Unit

GPU --> Multiprocessors
FPGA --> Logic Block, Interconnection, Input/Output, Switch Box, Connect Block

Software and Programming Languages

Silicon --> BIOS --> Operating System --> Applications --> Browser --> Web Apps

Assembly     C     SQL     PERL     JavaScript
             C++   PHP     Python
             C##    Swift
             Java
Compliers

Translation from programming languages to mechine code(Binary).

Operating System
  • macOS
  • iOS
  • Linux
  • Windows
  • Android
  • ......
Software Engineering

Make the program possible to run.

Networking

Create Computer Graphics.

  • Concurrent/ Distributed/ Parallel/ Systems
  • Data Management
  • Performance

Applications

  • Optimisation
  • Boolean Satisfiability
  • Artifical Intelligence
  • Machine Learning
  • Computer Version
  • Natural Language Processing
  • Big Data
  • Hacking
  • Computational Science
  • Super Computing
  • Simulation
  • Virtual Reality
  • Augmented Reality
  • Teleprescence
  • Robitics