Please enable JavaScript.
Coggle requires JavaScript to display documents.
Map of Computer Science - Coggle Diagram
Map of Computer Science
Theoretical Computer Science
Alan Turing
Turing Machine - a general purpose computer
An infinitely long tape
Tape is working RAM in today's computers
A head that can read and write symbols to the tape
CPU
A state register that stores the head and a list of instructions
computer's memory
Except Quantum computers all other computers are essentially turing machines
Other parts of modern computers
Monitor
Power
GPU
SSD
RAM
CPU
Motherboard
Input
Sound
Every problem is computed using - Lambda calculus
Basis of research in programming languages
Computability Theory
Attempts to classify what is and isn't computable
Some problems that cannot be solved by a computer?
due to the nature of the problem
Ex: halting problem
Computational complexity
Time - Amount of steps
Space - Amount of memory
P
Testing if prime
Graph connectivity
Are efficient for a computer
BQP
Discrete logarithm
Factoring
Efficient for a quantum computer to solve
NP
Graph Isomorphism
NP Complete
Travelling salesman
Map colouring
Does P is not equal to NP
N x N chess
PSpace
NxN Go
Algorithms
Set of instructions independent of hardware or programing language designed to solve a particular problem
Sorting
Efficiency based on algorithmic complexity
Information Theory
Study of information - how it can be measured, stored or communicated
Compression algorithms
Error correction
Coding theory
Cryptography
scramble data
encryption schemes
Public key hashes and private key converts back?
More
Logic
Graph theory
Computational Geometry
Automata theory
Quantum Computation
Parallel programming
Formal methods and Data Structures
Computer Engineering
Applications