Map of Computer Science

Theoretical Computer Science

Computer Engineering

Applications

Alan Turing

Turing Machine - a general purpose computer

An infinitely long tape

A head that can read and write symbols to the tape

A state register that stores the head and a list of instructions

computer's memory

CPU

Tape is working RAM in today's computers

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