-
Notifications
You must be signed in to change notification settings - Fork 2
/
contents
122 lines (94 loc) · 3.4 KB
/
contents
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
Table of Contents
=================
Incomplete chapter
Set theory, Turing machine, Graph theory, Encoding, Algorithms, Complexity and Non-determinism, Formal grammars
Topics in discussion
Combinatorics, more number theory such as prime numbers
01 Foundations of Computer Science
----------------------------------
* Term “computation” and “automation”.
* 4 parts of computer science.
02 Bits
-------
* Term “Bits” and “Bytes”. 1 byte = 8 bit.
* Bits & Bytes operations.
* Concept of number systems.
* How can we map numbers to bits of (non-)arbitrary precision?
* Arithmetic operations in other number systems.
* Modulo and ISBN-10 example?
* How many positions are necessary for an alphabet [a-zA-Z0-9]?
* Relation of positions and states.
* Shifts with negative numbers.
* Real numbers in IEEE 574.
* SI units.
03 Logic
--------
* The concept of logic. Cheatsheet for boolean operations.
* Definition “boolean operation” and “boolean function”: f: {0,1}^n -> {0,1}
* Definition of the formal grammar “propositional logic”.
* NAND is complete boolean function [0]_.
* Relation turnstile and double arrows.
* Negation of boolean functions.
* Term satisifiability and contradiction.
* Term Junctor, bijunction and tautology.
* Relation to set theory.
.. [0]_: Discrete Mathematics, Exercise 94.
04 Set theory
-------------
* Introduction to set theory and especially its notations.
* Set vs unique set.
* Injectivity, Surjectivity, Bijectivity.
05 Turing machine
-----------------
* The concept of Turing machines. Structure of a TM. n-tapes. n-dimensional.
* Simple algorithms for turing-computable functions.
* Concept “input, processing, output”.
* Cannot store integers directly, but in encoded form, because input alphabet is finite.
* A movement can be omitted “Stop”.
* Dining Philosopher's problem?
06 Graph theory
---------------
* Glossary / Terminology.
* Basic problems such as minimal span tree.
* Concept adjacency matrix.
07 Encoding
-----------
* The concept of encoding.
* (un)signed integers/floats/strings.
* The concept of encodings (mapping of alphabets).
* (un)signed integers. floating points numbers and fixed point numbers.
* Strings and Unicode.
* {Huffman, Gray} coding, Fano condition, shannon, entropy.
* little and big endian
08 Abstraction
--------------
* The concept of abstraction.
09 Landau notation
------------------
* Definition of Big-O, Theta and Omega.
* Start with constant and linear and introduce new runtimes one after another.
* Knuth's approach with A-notation?
10 Algorithms
-------------
* Term “Algorithm”.
* Algorithmic thinking.
* Variable swapping (3 ways).
* Explain several well-known algorithms.
11 Complexity and Non-determinism
---------------------------------
* Term complexity.
* Concepts in complexity theory.
* Concept “Proof by reduction”.
* Concept of non-determinism. Cannot be implemented. Decision pathes.
* How does randomization and parallelism differ from non-determinism?
* Show SAT Problem.
* MATCHING problem in bipartit graph equals REACH. MAX FLOW equals REACH.
12 Formal grammars
------------------
* Relation between decision problems and formal languages.
* Regular Expressions.
* Finite state machine.
* Define an infinite structure in Regex. CFL following. CSL following. Recursive enumerable languages following. Show relation to halting problem.
13 Computer scientists
----------------------
* Some non-exhaustive list.