mathematics
#define mathematics: \
I-----------------------------------------------------------\
I-----------------------------------------------------------\
I-----------------------------------------------------------\
I /$$ /$$ /$$ /$$ \
I | $$$ /$$$ | $$ | $$ \
I | $$$$ /$$$$ /$$$$$$ /$$$$$$ | $$$$$$$ \
I | $$ $$/$$ $$ |____ $$|_ $$_/ | $$__ $$ \
I | $$ $$$| $$ /$$$$$$$ | $$ | $$ \ $$ \
I | $$\ $ | $$ /$$__ $$ | $$ /$$| $$ | $$ \
I | $$ \/ | $$| $$$$$$$ | $$$$/| $$ | $$ \
I |__/ |__/ \_______/ \___/ |__/ |__/ \
I-----------------------------------------------------------\
I-----------------------------------------------------------\
I-----------------------------------------------------------I
https://www.wolframalpha.com
TODO:
• function differences ???
• lu method
• Choleski method
MISC:
○
e ∈ Q*
∞ 1 / 1 \^n
. e := sum ─── == lim ( 1 + ─── ) ~= 2.71828
n=0 n! n->∞ \ n /
e^x >= x+1
— Prove that f(x) is convergent:
|f(x) - a| < e
○
(1+x)^k >= 1 + kx
○
lim nˇa = 1
x->∞
○
sin(x+y) == sin(x)*cos(x)+sin(x)*cos(y)
cos(x+y) == cos(x)*cos(y)-sin(x)*sin(y)
sin(2x) == 2sin(x)
cos(2x) == 2cos²(x) - 1 == cos²(x) - sin²(x)
sin²(x) == 1-cos(2x) / 2
cos²(x) == 1+cos(2x) / 2
logic
#define logic:: \
I-------------------------------\
I _ _ \
I | | (_) \
I | | ___ __ _ _ ___ \
I | | / _ \ / _` | |/ __| \
I | |___| (_) | (_| | | (__ \
I \_____/\___/ \__, |_|\___| \
I __/ | \
I |___/ \
I-------------------------------I
• see related AT "/Hardware/Logic_gates"
• in this section all (single quoted) chars mark a statement (see BELOW)
ORDERS: ORDERS:
all concept-s list-ed are defined and or detailed BELOW
Zeroth:
• just statements
• U := {true, false}
○ components
• bools
— operator-s
• negation
• conjunction
• disjunction
• exclusive disjunction
• implication
• equivalation
First:
○ components
• bools
• objects
• predicates
— operator-s
• negation
• conjunction
• disjunction
• exclusive disjunction
• implication
• equivalation
• quantifiers
BOOLEANS: BOOLEANS:
• "bool"
• after "George Boole"
• a value with is either true or false
• 0 eval-s to false, every other int eval-s to true
UNIVERSE: UNIVERSE:
U
• a set of all entities to be considered
• has to be assigned
{ U := {1, 2, 3} }
VARIABLE: VARIABLE:
• a symbol which may mean any value of the universe
• if the universe is not equal to {true, false} then
a variable taking up one of its values is called
an object
• on all mentions it means the same value
variables from now on are written as follows:
'<char>'
{ 'A' }
LITERAL: LITERAL:
• a bool variable/value or the negation of it
STATEMENT: STATEMENT:
• a declarative sentence which is unambiguously eval-s to a bool
{ 8 > 25
(You) can read. }
— interpretation:
• when all variables are decided to what value to hold
{
. U := {true, false}
'A' and 'B'
0 and 0 -> false
0 and 1 -> false
1 and 0 -> false
1 and 1 -> true
}
• a statement is called satisfiable or SAT for short if it has a true interpretation
• a statement is called unsatisfiable or UNSAT for short if it has no true interpretations
• a statement is called tautology or logikai törvény^HU if all of its interpretations are true
• a statement is a tautology if its negate is unsatisfiable
OPERATIONS: OPERATIONS:
Negation: Negation:
¬'A'
• not
• swaps logical value
○ table
------------------
| In || Out |
------------------
| false || true |
| true || false |
------------------
○ operational properties
¬(¬'A') == 'A'
Conjuction: Conjuction:
'A' ∧ 'B'
• and
• "logical multiplication"
○ table
--------------------------
| In1 | In2 || Out |
--------------------------
| false | false || false |
| false | true || false |
| true | false || false |
| true | true || true |
--------------------------
○ operational properties
'A' ∧ 'A' == 'A'
'A' ∧ 'B' == 'B' ∧ 'A'
'A' ∧ ('B' ∧ 'C') == ('A' ∧ 'B') ∧ 'C'
Disjunction: Disjunction:
'A' ∨ 'B'
• or
• "logical addition"
○ table
--------------------------
| In1 | In2 || Out |
--------------------------
| false | false || false |
| false | true || true |
| true | false || true |
| true | true || true |
--------------------------
○ operational properties
'A' ∨ 'A' == 'A'
'A' ∨ 'B' == 'B' ∨ 'A'
'A' ∨ ('B' ∨ 'C') == ('A' ∨ 'B') ∨ 'C'
'A' ∨ 'B' == ¬(¬'A' ∧ ¬'B')
Exclusive_disjunction: Exclusive_disjunction:
'A' ⊕ 'B'
• xor
○ table
--------------------------
| In1 | In2 || Out |
--------------------------
| false | false || false |
| false | true || true |
| true | false || true |
| true | true || false |
--------------------------
○ operational properties
'A' ⊕ 'B' == ('A' ∨ 'B') ∧ ¬('A' ∧ 'B')
¬('A' ⊕ 'B') == ¬'A' ⊕ 'B' == 'A' ⊕ ¬'B'
Implication: Implication:
'A' => 'B'
if <'A'> then <'B'>
• from a statement another follows
• asymmetrical, so it is its symbol
— theres nothing stopping one from mirroring the symbol to switch the operands:
'A' => 'B' == 'B' <= 'A'
• the former is what implication normally means,
but can be also referred to as right way implication
• the later is called a left way implication
○ table
--------------------------
| In1 | In2 || Out |
--------------------------
| false | false || true |
| false | true || false |
| true | false || true |
| true | true || true |
--------------------------
○ operational properties
'A' => 'B' == ¬'A' ∨ 'B'
Equalation: Equalation:
'A' <=> 'B'
○ table
--------------------------
| In1 | In2 || Out |
--------------------------
| false | false || true |
| false | true || false |
| true | false || false |
| true | true || true |
--------------------------
○ operational properties
('A' => 'B') ∧ ('B' => 'A') == 'A' <=> 'B'
Quentifiers: Quentifiers:
• "Kvantor"^HU
All: All:
∀'x'
• for all 'x'
○ eval in programming
{ ∀'x'(func('x'))
result = true;
for i in x:
if not func(x):
result = false;
break;
Any: Any:
∃'x'
• or "existential" kvantor
• for any 'x' || there exist an 'x' (for which the statement is true)
○ eval in programming
{ ∃'x'(func('x'))
result = false;
for i in x:
if func(x):
result = true;
break;
}
— skoleming:
• the act of removing existential kvantors from a formula
• if an existential kvantor stands to the immediate right of a for all kvantor
it can be removed by replacing all instances of its variable with a function
taking the for all kvantors variables as arguments
{ ∀'y'∀'z'∃'x'( P('x') ∧ 'y' => ¬('A' ∨ 'z') )
== ∀'y'∀'z'( P(Q('y', 'z')) ∧ 'y' => ¬('A' ∨ 'z') )
}
○ Precedence
1. ¬
2. ∧, ∨
3. ∀, ∃
4. =>
5. <=>
○ Complex operational properties
'A' ∧ ('B' ∨ 'C') == ('A' ∧ 'B') ∨ ('A' ∧ 'C')
'A' ∨ ('B' ∧ 'C') == ('A' ∨ 'B') ∧ ('A' ∨ 'C')
'A' ∧ ¬'A' == 0
'A' ∨ ¬'A' == 1
'A' ∨ 1 == 1
'A' ∨ 0 == 'A'
'A' ∧ 0 == 0
'A' ∧ 1 == 'A'
'A' ∨ ('A' ∧ 'B') == 'A'
'A' ∧ ('A' ∨ 'B') == 'A'
¬('A' ∧ 'B') == ¬'A' ∨ ¬'B'
¬('A' ∨ 'B') == ¬'A' ∧ ¬'B'
¬∀'x'( A('x') ) == ∃'x'( ¬A('X') )
¬∃'x'( A('x') ) == ∀'x'( ¬A('X') )
'A' ∧ ∀'x'( B('x') ) == ∀'x'( 'A' ∧ B('x') )
'A' ∨ ∀'x'( B('x') ) == ∀'x'( 'A' ∨ B('x') )
'A' ∧ ∃'x'( B('x') ) == ∃'x'( 'A' ∧ B('x') )
'A' ∨ ∃'x'( B('x') ) == ∃'x'( 'A' ∨ B('x') )
'A' => ∀'x'( B('x') ) == ∀'x'( 'A' => B('x')
'A' => ∃'x'( B('x') ) == ∃'x'( 'A' => B('x')
∀'x'( A('x') ) => 'B' == ∃'x'( A('x') => 'B' )
∃'x'( A('x') ) => 'B' == ∀'x'( A('x') => 'B' )
∀'x'(A('x')) ∧ ∀'x'(B('x')) == ∀'x'(A('x') ∧ B('x'))
∃'x'(A('x')) ∨ ∃'x'(B('x')) == ∃'x'(A('x') ∨ B('x'))
CLAUSE: CLAUSE:
• a finite number of literals either all disjuncted or conjuncted
{ 'A' ∨ 'B' ∨ 'C'
'D' ∧ 'E' ∧ 'F'
}
○ alternative writing
<char>ˇ1 ∨...∨ <char>ˇ<int>
{ lˇ1 ∨...∨ lˇ12
}
— empty clause:
• when a clause has 0 literals its called an empty clause and symbolized with '∅', '⊥' or '◻'
• an empty conjunctive clause always eval-s to true (ie. tautology)
• an empty disjunctive clause always eval-s to false (ie. unsatisfiable)
— Horn clause:
• a clause that contains 1 not negated literal at max
PREDICATE: PREDICATE:
<char>(<args>)
• parametered statement
• describes a relation
• in C terms (see AT "/C++") it could be described as a function taking at least 1 argument and return-ing a bool ( bool (*)( <class> ) )
{ M(x) := "\x is mortal."
M("Socrates") == true
}
NORMAL_FORMS: NORMAL_FORMS:
DNF: DNF:
• "Disjunctive Normal Form"
• disjunction of conjunctions of literals
{ ('A' ∧ 'B') ∨ ('C' ∧ 'D' ∧ 'E') ∨ 'F' }
CNF: CNF:
• "Conjunctive Normal Form"
• conjunction of disjunctions of literals
{ 'A' ∧ ('B' ∨ 'C' ∨ 'D' ∨ 'E') ∧ ('F' ∨ 'G') }
○ algorithm for converting an arbitrary statement to DNF or CNF
1. transform xor-s to and/or form
2. transform equivalences to and/or form
3. transform implications to and/or form
4. de Morgen all negations
5. transform and/or-s with assiciativity appropriately
<int>-[D | C]NF:
• a CNF or DNF whichs conjucted/disjuncted clauses are no long-er than <int>
{
'A' ∧ 'B'
('A' ∨ 'B' ∨ 'C') ∧ ('D' ∨ 'E' ∧ 'F') ∧ ('G' ∨ 'H' ∧ 'J') ∧ ('K' ∨ 'L' ∧ 'M')
'A' ∧ ('B' ∨ 'C') ∧ ('D' ∨ 'E' ∧ 'F')
}
PNF: PNF:
(<kvantor>*)<CNF>
• "Prenex Normal Form"
• a way of organizing a complex statement
• all quantors are present at the beginning of the statement, everything else is is written in CNF
{ ∀'x'∃'y'∀'z'( P('x') ∧ M('y') ∧ I('z')) }
SATISFIABILITY: SATISFIABILITY:
○ famous SAT solvers
○ DPLL
• MiniSat
• CaDiCat
• Glucose
○ SMT
• Z3
• CVC4
• Yices
Tseitin_transformation: Tseitin_transformation:
• a subformula is a subset of the formula which is
surrounded by meaningful parentheses or a negated variable
• every formula is a subformula of itself
• to evaluate subformulas separately for satisfiability
• linear with the number of subformulas
• a variable is substituted for every subformula then those and
the variable representing the whole are conjucted/disjuncted
• creates an expression which has the same satisfiability as the original
• for lengthy formulas its faster to test satisfiability this way,
rather than converting to DNF first
{
(( 'A' ∨ 'B' ) ∧ 'C') => (¬'D')
{( 'A' ∨ 'B' ),
(( 'A' ∨ 'B' ) ∧ 'C'),
( ¬ 'D' ),
(( 'A' ∨ 'B' ) ∧ 'C') => (¬'D')
}
'x'-1 <=> 'A' ∨ 'B'
'x'-2 <=> ('A' ∨ 'B') ∧ 'C'
'x'-3 <=> ¬'D'
'x'-4 <=> (( 'A' ∨ 'B' ) ∧ 'C') => (¬'D')
'x'-4 ∧ ('x'-1 <=> 'A' ∨ 'B') ∧ ('x'-2 <=> ('A' ∨ 'B') ∧ 'C') ∧ ('x'-3 <=> ¬'D') ∧ ('x'-4 <=> (( 'A' ∨ 'B' ) ∧ 'C') => (¬'D')
}
Plaisted_Greenbaum_transformation: Plaisted_Greenbaum_transformation:
• usually used along side with the Tseitin transformation
— given a formula, an equivalence can be converted to an implication without changing the satisfiability the following ways:
• if the literal on the left side of the equivalence is only used without negation in the rest of the formula, then
the equivalence can be changed to a right way implication
• if the literal on the left side of the equivalence is only used with negations in the rest of the formula, then
the equivalence can be changed to a left way implication
• else its not possible
Resolution: Resolution:
Rez(<clause-1>, <clause-2>)
• operates on a CNF
• used with 2 disjunctive clauses and contain exactly 1 opposing literal pair {'A', ¬'A'}
• yields a formula which has the same satisfiability as the previous
• if it can be used repeatedly to get an empty expression which proves
that the original CNF is unsatisfiable
• not efficient to check large clauses with
— unit propagation
• one of the resolvants is a single
{ the line ABOVE the resolution is always a CNF
('A' ∨ 'B') ∧ ¬'B'
Rez('A' ∨ 'B',
¬'B')
==
'A'
('A' ∨ 'B') ∧ (¬'A' ∨ ¬'B')
Rez('A' ∨ 'B',
¬'A' ∨ ¬'B')
('A' ∨ 'B' ∨ 'C') ∧ (¬'A' ∨ 'B' ∨ 'C')
Rez('A' ∨ 'B' ∨ 'C',
¬'A' ∨ 'B' ∨ 'C')
==
'B' ∨ 'C'
'A' ∧ ¬'A'
Rez('A',
¬'A')
==
◻
(¬'A' ∨ 'B') ∧ 'C' ∧ ¬'B' ∧ (¬'C' ∨ 'A')
C₁ := ¬'A' ∨ 'B'
C₂ := 'C'
C₃ := ¬'B'
C₄ := ¬'C' ∨ 'A'
C₅ := Rez(C₁, C₃) == ¬'A'
C₆ := Rez(C₂, C₄) == 'A'
C₆ := Rez(C₅, C₆) == ◻
('A' ∨ 'B') ∧ (¬'A' ∨ 'B') ∧ ('A' ∨ ¬'B') ∧ (¬'A' ∨ ¬'B')
C₁ := 'A' ∨ 'B'
C₂ := ¬'A' ∨ 'B'
C₃ := 'A' ∨ ¬'B'
C₄ := ¬'A' ∨ ¬'B'
C₅ := Rez(C₁, C₂) == 'B' ∨ 'B' == 'B'
C₆ := Rez(C₅, C₃) == 'A'
C₆ := Rez(C₆, C₄) == ¬'B'
C₇ := Rez(C₇, C₅) == ◻
}
Dimacs_format: Dimacs_format:
• format to represent CNF for an easy to type and read both by humans and machines
• goto for SAT solvers
{ (<header>)
<clause>*
}
Header:
p cnf <int-1> <int-2>
• optional
• specifies that this is a DIMACS file, using CNF
• clarifies that there is going to be <int-1> distinct variables used
• clarifies that the CNF consists of <int-2> clauses
Clauses:
<variable>*0
• no sign is needed between variables as logical or is the only option
• '0' terminates the clause
• clauses are usually separated by new lines
Variables:
(-)<int><whitespace>
• <int> is the variables name (must not be 0)
• the '-' sign signals negation
• trailing whitespace is necessary
{
p cnf 4 5
1 2 0
— 1 3 0
3 -2 0
— 4 -2 3 0
— 4 0
}
DPLL: DPLL:
• "Davis–Putnam–Logemann–Loveland"
• algorithm testing for satisfiability
• operates on CNF-s
• recursive
○ pseudo-prototype
bool DPLL(const Clause &c, Interpretation i);
• c is the whole, original clause, which is always passed unchanged
• i is a set variables from c with a value assigned
○ inner workings
— pure literal elimination
• when a literal occurs with only one polarity (always or never negated),
it doesnt affect satisfiability
• safely removed
• unit propagation
• backtracking
• creates a decision tree from assigning all literals a value; computes end result;
if false backtracks (reassigning a variable) and continue-s
if true the input CNF is proven to be satisfiable, searching can halt
○ step-by-step
do pure literal elimination;
Yellow( Build_tree:
if not all varibles are assigned do:
assign a variable to a value to which it has not yet been;
Yellow( Check:
do unit propagation; // if possible
do compute ${end};
if ${end}:
return true;
else:
pop i
SMT: SMT:
• "Satisfiability Modulo Theories"
• a formula in first order logic, but with NO kvantors
• concerned with deciding whether a mathematical formula is satisfiable
SMT_LIB:
• format for SMT solvers
• atomic operations are converted to Polish notation and parenthesized (see AT "/Theory/?!")
• comments start with ';'-s
— instructions:
set-logic <logic>
declare-const <name> <typename> : declares variable
assert <statement> : specifies statement (for other, later instructions)
check-sat : check satisfiability of the preceding asserts (see ABOVE)
get-model : returns the found true interpretation after a check-sat
— logics:
QF_LIA
— operator-s:
+
—
*
/
div
mod
=
distinct
<
•
<=
• =
and
or
not
=>
abs
ite
; Basic Boolean example
(declare-const p Bool)
(assert (and p (not p)))
(check-sat)
; returns unsat
sets
#define sets:: \
I------------------------\
I _____ _ \
I / ___| | | \
I \ `--. ___| |_ ___ \
I `--. \/ _ \ __/ __| \
I /\__/ / __/ |_\__ \ \
I \____/ \___|\__|___/ \
I------------------------I
• collection of things where everything can be judged to be or not to be a element
• not ordered
• marked with a single capital letter {'A'}
• its elements are marked with a single lower case letter {'a'}
NULL: NULL:
∅ || {}
• an/the empty set
• 0 elements
• is a subset of every set
Set_systems: Set_systems:
• "family of sets" || "set-family"
• a set composed of sets
{ 'A':={{0,1},{1,2},{6,8}} }
Operations: Operations:
_____
<set> : "complementer"; ¬<set>; <set>ᶜ; includes everything that is not an element of <set>
<set-1> \ <set-2> : "difference"; elements of <set-1> which are not elements of <set-2>
<set-1> U <set-2> : "union"; elements which are elements of <set-1> or <set-2>
<set-1> ∩ <set-2> : "intersection"; elements which are elements of <set-1> and <set-2>
<set-1> ⊇ <set-2> : "subset"; <set-1> contains <set-2>
<set-1> ⊆ <set-2> : "subset"; <set-2> contains <set-1>
<set-1> ⊃ <set-2> : "proper/strict subset"; <set-1> contains <set-2> amongst other elements
<set-1> ⊂ <set-2> : "proper/strict subset"; <set-2> contains <set-1> amongst other elements
<set-1> ⊅ <set-2> : not subset; <set-1> doesnt contains <set-2>
<set-1> ⊄ <set-2> : not subset; <set-2> doesnt contains <set-1>
<char> ∈ <set> : <char> is an element of <set>
<char> ∉ <set> : <char> is not an element of <set>
{
┌─────────────────────┐
│U │
│ .`````.`````. │
│ : A : : B : │
│ : : : : │
│ : : : : │
│ '.....'.....' │
│ │
└─────────────────────┘
┌──────────A──────────┐
│U │
│ .#####.`````. │
│ :##A####: B : │
│ :#######: : │
│ :#######: : │
│ '#####'.....' │
│ │
└─────────────────────┘
_
┌──────────A──────────┐
│U####################│
│####.`````.#####.####│
│###: A :####B##:###│
│###: :#######:###│
│###: :#######:###│
│####'.....'#####'####│
│#####################│
└─────────────────────┘
┌────────Union────────┐
│U │
│ .#####.#####. │
│ :##A#######B##: │
│ :#############: │
│ :#############: │
│ '#####'#####' │
│ │
└─────────────────────┘
┌─────Intersection────┐
│U │
│ .`````.`````. │
│ : A :#: B : │
│ : :#: : │
│ : :#: : │
│ '.....'.....' │
│ │
└─────────────────────┘
}
Set_square:
<set>^2 || P(<set>)
• set of all subsets of <set>
{ 'A':={2,3,6}
P('A') == {{∅},{2},{3},{6},{2,3},{2,6},{3,6},{2,3,6}}
}
Descartes_multiplication:
<set-1> × <set-2> := {(a,b): a ∈ A and b ∈ B}
<set> × <set> == <set>^2
• "direct multiplication"
• results in a set of ordered pairs where the first component is from <set-1>
and the second component is from <set-2>
— not commutative:
<set-1> × <set-2> != <set-2> × <set-1>
{ 'A':={2,3,6}
'B':={4,5,8}
'A'×'B' == {(2,4),(2,5),(2,8),(3,4),(3,5),(3,8),(6,4),(6,5),(6,8)}
}
Set_Builder_Notation: Set_Builder_Notation:
{ <superset> [':'|'|'] <equation> }
• defines a set by giving a schematic to calculate every number which is an element
○ <superset>
— usually either a char (marking all numbers) or
a char which is stated to be an element of a number set (see BELOW)
{ 'x'
'x' ∈ R
}
{ {x|x>0} }
— Sets of numbers:
+-+-----------------------------------------------------------------------+
|R| | R : real numbers
+-+ | Q : rational numbers
| +--+----------------------------+--+----------------------------+ | Q*: irrational numbers
| |Q | |Q*| | | Z : ints
| +--+ +--+ | | N : natural numbers
| | +-+---------------+ | | |
| | |Z| | | | | Q* == R \ Q
| | +-+ | | | |
| | | +-+----+ | | | |
| | | |N| 0 | | | | |
| | | +-+ | | | | |
| | | | 2 | | | | |
| | | +------+ | | | |
| | | -3 | | | |
| | 3 +-----------------+ | | |
| | - | | |
| | 2 | π | |
| +-------------------------------+-------------------------------+ |
| |
+-------------------------------------------------------------------------+
Rˇ+ := { 'x' ∈ R | 'x' > 0 }
Rˇ- := { 'x' ∈ R | 'x' < 0 }
Rˇb := R U {-∞, +∞}
Relations: Relations:
_R_
• any subset of [set-1] × [set-2]
○ element of _R_
[element-1][_R_][element-2]
where [element-1] ∈ [set-1]
where [element-2] ∈ [set-2]
• "[element-1] is in [_R_] relation with [element-2]"
— commutativity:
if [element-1] _R_ [element-2] == [element-2] _R_ [element-1]
{
3 + 2 == 5 == 2 + 3
}
— transitiveness:
where [element-1] _R_ [element-2]
&& [element-2] _R_ [element-3]
if [element-1] _R_ [element-3];
then _R_ is transitive
— symmetry:
if ([element-1] _R_ [element-2])
&& ([element-2] _R_ [element-1]);
then _R_ is symmetrical
— equilance:
if (_R_ is transitive)
&& (_R_ is symmetrical)
&& (_R_ is reflexive)
Cardinality: Cardinality:
|<set>|
• if the number of elements in <set> can be expressed as an unsigned int
then <set> is finite
• if the number of elements in <set> is equal to the number of elements
in the set of natural numbers (N)
then <set> is countably infinite
• if the number of elements in <set> is larger than the number of elements
in the set of natural numbers (N)
then <set> is uncountable
{
'A' := {0, 1, 2, 3}
|'A'| == 4
'A' is finite
}
Values_of_interest:
• in the bellow examples [*this] refers to the set depicted on the corresponding number line
— inner values:
<set>o
• values whichs all arbitrary sized surroundings are subsets of <set>
. { -3 -2 -1 0 1 2 3
. -------|---------|---------|---------|-----#=============#---------|-----
1 is an inner value as its surrounded by 0.9, 0.99, 1.1, 1.01, etc.
2 is not an inner value as its surrounded by 2.1, 2.01, 2.001 etc.,
which are not part of the set
[*this]o == ![0.6,2!]
}
— outer values
<set>k
<set>k == R \ H
• values whichs have an arbitrary sized surrounding which contain no values which are elements of <set>
• inner values of <set>s complementer
{ -3 -2 -1 0 1 2 3
-------|---------|---------|----#=================#----------------|-----
[*this]k={![-∞,-0.5!] U ![1.3,∞!]}
}
— border values:
d<set>
• values whichs all arbitrary sized surroundings contain both a value which is
a member of <set> and a value which is not
{ -3 -2 -1 0 1 2 3
-------|--#======O------#=============#--------#---------#---------|-----
0.1 is a border value as its surrounding includes
0.11, 0.101, 0.1001, etc. which are not elements of [*this] and
0.999, 0.99, 0.9, etc. which are elements of [*this]
2 is a border value as its surrounding includes
1.1, 1.01, 1.001, etc. which are not elements of [*this] and
2 which is an element of [*this]
— 2 is a border value as its surrounding includes
— 2, -1.9, -1.8, etc. which are not elements of [*this] and
— 2.1, -2.01, -2.001, etc. which are elements of [*this]
d[*this] == {-2.7 U -2 U -1.3 U 0.1 U 1 U 2}
}
— cluster values:
<set>*
• a value whichs all arbitrary sized surrounding contain a value which is
a member of <set> (and that value is not the same one as in question)
{ -3 -2 -1 0 1 2 3
-------#==O------|-#==================#--------#---------|---------|-----
— 3 is a cluster value as its surrounding includes -2.999, -2.99, -2.9, etc.
which are members of [*this]
1 is not a cluster value as 0.999, 0.99, 0.99, etc. and 1.1, 1.01, 1.001
are not members members of [*this] even tho 1 is member
[*this]* == {[-3,-2.7!] U [-1.8,0.1]}
}
— isolated values:
<set>i
• a value which is a member of <set> and has an arbitrary sized surrounding
which contain no other other member of <set>
{ -3 -2 -1 0 1 2 3
---#--#===========#---------|---#===========O--#--#-#----|---------#-----
[*this]i == {-3.5 U 1 U 1.3 U 1.5 U 3}
}
— bound values:
where [set-s] ⊂ [set-p]
• every 'x' ∈ [set-p] value is a lower bound value of [set-s] if ∀'y'('x' <= 'y') where 'y' ∈ [set-s]
• ie. a lower bound value is a value that is lesser than every value of a set and belong to the same set
of switch the formerly mentioned set is a subset of
• every 'x' ∈ [set-p] value is an upper bound value of [set-s] if ∀'y'('x' >= 'y') where 'y' ∈ [set-s]
• ie. a upper bound value is a value that is greater than every value of a set and belong to the same set
of switch the formerly mentioned set is a subset of
• a set lower bounded if there exists a lower bount value to it
• a set upper bounded if there exists a upper bount value to it
• a set is bounded if it is lower bounded ∧ upper bounded
— _Infimum_
inf <set>
• the greatest lower bount value of a set
• also called the exacpt lower bound
• if <set> is not lower bounded then inf <set> := -∞
— _Supremum_
sup <set>
• the least upper bount value of a set
• also called the exacpt upper bound
• if <set> is not upper bounded then sup <set> := +∞
matrixes
#define matrixes\
#define matrices:: \
I-----------------------------------------------\
I ___ ___ _ _ \
I | \/ | | | (_) \
I | . . | __ _| |_ _ __ _ ___ ___ ___ \
I | |\/| |/ _` | __| '__| |/ __/ _ \/ __| \
I | | | | (_| | |_| | | | (_| __/\__ \ \
I \_| |_/\__,_|\__|_| |_|\___\___||___/ \
I-----------------------------------------------I
• a block of elements where elements are organized into columns and rows;
each row has the same length as the others; positions are not interchangeable
○ syntax
• enclosed in parentheses
• elements are separated by whitespaces
{
┌ ┐
│ 1 2 3 │
│ │
│ 4 5 6 │
│ │
│ 7 8 9 │
└ ┘
┌ ┐
│ 42 33 │
│ │
│ 16 89 │
└ ┘
}
Operators: Operators:
operatorˇ and operator[]:
[matrix]ˇ[list]
• element access
• <list> is a list of coordinates
• in most programming languages this is done by specifying these values inside brackets,
separated by colons and 0 representing the first position
• for the sake of readability this document always uses the bracket notation
{
┌ ┐
│ 2 5 │
A := │ │
│ 4 40 │
└ ┘
A^1 1 == A[0, 0] == 2
A^1 2 == A[0, 1] == 5
A^2 1 == A[1, 0] == 4
A^2 2 == A[1, 1] == 40
}
operator+:
• only usable on matrices of the same size
• each element of the corresponding coordinates are added separately
{
┌ ┐ ┌ ┐ ┌ ┐
│ 1 3 │ | │ 5 10 │ _______ │ 6 13 │
│ │ ---+--- │ │ │ │
│ 16 4 │ | │ 7 4 │ ‾‾‾‾‾‾‾ │ 23 8 │
└ ┘ └ ┘ └ ┘
}
operator^T:
• "transponation"
• swapping the columns lines and columns
• the <int>th line becomes the <int>th column
{
┌ ┐
│ 13 6 21 │
A := │ │
│ 18 0 12 │
└ ┘
┌ ┐
│ 13 18 │
│ │
A^T = │ 6 0 │
│ │
│ 21 12 │
└ ┘
}
operator*:
• only usable on matrices where the number of columns match the number of lines of the other
• the second operand gets transponated then for every combination of lines corresponding values are multiplied together and added;
values resulting from the same row of the first matrix are written in the same row
{
┌ ┐ ┌ ┐ ┌ ┐
│ 1 0 5 │ │ 2 4 │ │ 17 34 │
│ │ \ / │ │ _______ │ │
│ 1 0 4 │ X │ 1 5 │ │ 14 28 │
│ │ / \ │ │ ‾‾‾‾‾‾‾ │ │
│ 2 1 1 │ │ 3 6 │ │ 8 19 │
└ ┘ └ ┘ └ ┘
}
— there is an intuitive alternative writing mode for writing matrix multiplication called the Falk scheme
• the two matrices are written in a table form along their matching long sides
{
┌ ┐
│ 2 │
┌ ┐ \ / │ │
│ 3 2 6 │ X │ 4 │
└ ┘ / \ │ │
│ 1 │
└ ┘
┌ ┐
│ 2 │
│ - │
│ 4 │
│ - │
│ 1 │
└ - ┘
┌ ┐+---+
│ 3| 2| 6 │| |
└ ┘+---+
}
• to each resulting empty cell the multiple of the corresponding spots are added together
{
┌ ┐
(3x2)------│ 2 │
| + │ - │
|(2x4)---│ 4 │
| | + │ - │
| |(6x1)│ 1 │
| | | └ - ┘
┌ | | | ┐+---+
│ 3| 2| 6 │| 20|
└ ┘+---+
}
operator||:
|[matrix]|
• "determinant"
• [matrix]s ${LINES} must match its ${COLUMNS}
○ tricks
• letters signals ints BELOW
— 2 by to matrices
| ┌ ┐ |
| │ a b │ |
| │ │ |
| │ c d │ |
| └ ┘ |
| ┌ ┐ |
| │ a b │ |
| │ \ │ |
| │ c d │ |
| └ ┘ |
| ┌ ┐ |
| │ a b │ |
| │ X │ |
| │ c d │ |
| └ ┘ |
• multiply the numbers connected
• subtract the product of the ones connected with '/' from the product of the ones connected with '\\'
(a * d) - (b * c)
— 3 by to matrices
| ┌ ┐ |
| │ a b c │ |
| │ │ |
| │ d e f │ |
| │ │ |
| │ g h i │ |
| └ ┘ |
a b c a b
d e f d e
g h i g h
a b c a b
\ \ \
d e f d e
\ \ \
g h i g h
a b c a b
\ X X /
d e f d e
/ X X \
g h i g h
• multiply the numbers connected
• subtract the product of the ones connected with '/' from the product of the ones connected with '\\'
(a * e * i) + (b * f * g) + (c * d * h) - ((g * e * c) + (h * f * a) + (i * d * b))
Identity_matrix: Identity_matrix:
┌ ┐
│ 1 0 0 ... 0 │
│ │
│ 0 1 0 ... 0 │
│ │
│ 0 0 1 ... 0 │
│ . . . . │
│ : : : : │
│ │
│ 0 0 0 ... 1 │
└ ┘
• a matrix with all 1s on its diagonal and all 0s else where
{
┌ ┐
│ 1 0 │
│ │
│ 0 1 │
└ ┘
}
• behaves similarly as 1 in arithmetics or 0 in logic
• a matrix times an identity matrix is the original matrix itself
{
┌ ┐
│ 1 0 │
* │ │
│ 0 1 │
└ ┘
||
┌ ┐ ┌ ┐
│ 9 7 │ │ 9 7 │
│ │ = │ │
│ 4 6 │ │ 4 6 │
└ ┘ └ ┘
}
Inversion: Inversion:
let ${A} be a matrix
let ${B} be the inverse of ${A}
let ${I} be a identity matrix
${A} * ${B} == I
Gaussian_ellimination: Gaussian_ellimination:
• application to equation systems:
• translate an equation system to a matrix by writing down the coefficents as the values and the results as their extension
{ ┌ ┐
2x + 3y - z = 32 │ 2 3 1 | 32 │
x + y - 4z = 16 => │ | │
│ 1 1 4 | 16 │
└ ┘
}
• lines become inter changeable
• by swapping lines, multiplying lines by a const and dividing lines by other lines a solution will be present
• ones tries to create a matrix where <int>th row has atleast <int> 0 values at its beginning
— the end result decides how many solutions the equation system has
{ I ### | # I
I 0## | # I => no solutions
I 00# | # I
I 000 | x I
I ### | # I
I 0## | # I => 1 solution
I 00# | # I
I #### | # I
I 0### | # I => ∞ solutions
I 00## | # I
}
Linear_regression:
{
x | 0 | 1 | 2 | 3 |
---+----------------
y | 2 | 3 | 3 | 5 |
┌ ┐
│ 2 │
│ │
│ 3 │
y = │ │
│ 3 │
│ │
│ 5 │
└ ┘
x₁ x₀
┌ ┐
│ 0 1 │
│ │
│ 1 1 │
A = │ │
│ 2 1 │
│ │
│ 3 1 │
└ ┘
┌ ┐
│ 0 1 2 3 │
A^T = │ │
│ 1 1 1 1 │
└ ┘
┌ ┐
│ 0 1 │
│ │
│ 1 1 │
* │ │
│ 2 1 │
│ │
│ 3 1 │
└ ┘
| |
┌ ┐ ┌ ┐
│ 0 1 2 3 │ │ a b │
│ │ = │ │
│ 1 1 1 1 │ │ b c │
└ ┘ └ ┘
a = 14
b = 6
c = 4
┌ ┐
│ 2 │
│ │
│ 3 │
* │ │
│ 3 │
│ │
│ 5 │
└ ┘
| |
┌ ┐ ┌ ┐
│ 0 1 2 3 │ │ d │
│ │ = │ │
│ 1 1 1 1 │ │ e │
└ ┘ └ ┘
d = 24
e = 13
┌ ┐ ┌ ┐ ┌ ┐
│ 14 6 │ │ a₁ │ │ 24 │
│ │ * │ │ = │ │
│ 6 4 │ │ a₀ │ │ 13 │
└ ┘ └ ┘ └ ┘
┌ ┐ ┌ ┐ ┌ ┐
│ 14 6 | 24 │ I-II*2 \ │ 2 -2 | -2 │ II-I*3 \ │ 2 -2 | -2 │
│ | │ ==========> │ | │ ==========> │ | │
│ 6 4 | 13 │ / │ 6 4 | 13 │ / │ 0 10 | 19 │
└ ┘ └ ┘ └ ┘
0*a₁ + 10*a₀ = 19
a₀ = 1.9
2*a₁ - 2*a₀ = -2
2*a₁ - 2*1.9 = -2
2*a₁ - 3.8 = -2
2*a₁ = 1.8
a₁ = 0.9
f(x) = 0.9x + 1.9
}
?!_regression
{
x |-2 |-1 | 1 | 2 |
---+----------------
y | 3 | 1 | 0 | 2 |
}
┌ ┐
│ 3 │
│ │
│ 1 │
y = │ │
│ 0 │
│ │
│ 2 │
└ ┘
x₂ x₁ x₀
┌ ┐
│ 4 -2 1 │
│ │
│ 1 -1 1 │
A = │ │
│ 1 1 1 │
│ │
│ 4 2 1 │
└ ┘
┌ ┐
│ 4 1 1 4 │
│ │
A^T = │ -2 -1 1 2 │
│ │
│ 1 1 1 1 │
└ ┘
┌ ┐
│ 4 -2 1 │
│ │
│ 1 -1 1 │
* │ │
│ 1 1 1 │
│ │
│ 4 2 1 │
└ ┘
| |
┌ ┐ ┌ ┐
│ 4 1 1 4 │ │ a b c │
│ │ │ │
│ -2 -1 1 2 │ = │ b d e │
│ │ │ │
│ 1 1 1 1 │ │ c e f │
└ ┘ └ ┘
a = 34
b = 0
c = 10
d = 10
e = 0
f = 4
┌ ┐
│ 3 │
│ │
│ 1 │
* │ │
│ 0 │
│ │
│ 2 │
└ ┘
| |
┌ ┐ ┌ ┐
│ 4 1 1 4 │ │ 21 │
│ │ │ │
│ -2 -1 1 2 │ = │ -3 │
│ │ │ │
│ 1 1 1 1 │ │ 6 │
└ ┘ └ ┘
┌ | ┐
│ 34 0 10 | 21 │
│ | │
│ 0 10 0 | -3 │
│ | │
│ 10 0 4 | 6 │
└ | ┘
graphs
#define graphs:: \
I-----------------------------------------\
I _____ _ \
I | __ \ | | \
I | | \/_ __ __ _ _ __ | |__ ___ \
I | | __| '__/ _` | '_ \| '_ \/ __| \
I | |_\ \ | | (_| | |_) | | | \__ \ \
I \____/_| \__,_| .__/|_| |_|___/ \
I | | \
I |_| \
I-----------------------------------------I
• a set of points and edges
• an edge is line connecting 2 points
{
E X
A X \ X D
\ \ |\
\ \|/
\ .---X C
X--^
B
A X----------X B
|^.
| ^.
| ^.
| ^.
| ^.
C X----------X D
}
• a simple graph is a graph where each point is connected max once
{
A X--------X B
|
|
|
|
X C
}
• a loop is when an edge connects a point to itself
{
A X------X B
/ \
| |
\___/
}
• the degree of a point is the number of times edges connect to it
{
(1) (1)
A X--------X B
|
|
|
|
X C
(1)
(3) (1)
A X----------X B
|^.
| ^.
| ^.
| ^.
| ^.
C X----------X D
(2) (2)
(3) (2)
A X------X B
/ \
| |
\___/
}
• a complete graph is a graph, whichs each point is connected to every other exactly once
{
A X----------X B
|^. .^|
| ^. .^ |
| :: |
| .^ ^. |
|.^ ^.|
C X----------X D
A X----------X B
/|^--.__.--^|\
/ |.-^. .^-.| \
F X:^|----::----|^:X C
\^|-..^__^.--|^/
\|.:--^^--:.|/
E X----------X D
}
Number_of_edges:
2m = ∑ deg(v)
• "handshake theorem"
• the sum of edges for all points is twice the number of edges
{
A X----------X B
/|^--.__.--^|\
/ |.-^. .^-.| \
F X:^|----::----|^:X C
\^|-..^__^.--|^/
\|.:--^^--:.|/
E X----------X D
(5) (5)
A X----------X B
/|^--.__.--^|\
(5) / |.-^. .^-.| \ (5)
F X:^|----::----|^:X C
\^|-..^__^.--|^/
\|.:--^^--:.|/
E X----------X D
(5) (5)
∑ deg(v) = 5 + 5 + 5 + 5 + 5 + 5 = 30
2m = 30 / :2
m = 15
}
sequances
#define sequances:: \
I------------------------------------------------------\
I _____ \
I / ___| \
I \ `--. ___ __ _ _ _ ___ _ __ ___ ___ ___ \
I `--. \/ _ \/ _` | | | |/ _ \| '_ \ / __/ _ \/ __| \
I /\__/ / __/ (_| | |_| | __/| | | | (_| __/\__ \ \
I \____/ \___|\__, |\__,_|\___||_| |_|\___\___||___/ \
I | | \
I |_| \
I------------------------------------------------------I
Summary:
<int-2>
∑ i = <calc>
i = <int-1>
• addition of numbers matching (calculated by) a rule
• i starts at <int-1> always increases by one until it reaches <int-2>
• for every value of i <calc> (being an equation) is calculated
• all <calc>s are added to get the result
{
4
∑ = 2^i == 2^1 + 2^2 + 2^3 + 2^4 == 30
i = 1
}
Product:
<int-2>
Π i = <calc>
i = <int-1>
• multiplication of numbers matching (calculated by) a rule
• i starts at <int-1> always increases by one until it reaches <int-2>
• if [int-1] starts at 0, the result is always 0; spotting it in a formula is most likely human error
• for every value of i <calc> (being a an equation) is calculated
• all <calc>s are multiplied together to get the result
{
10
Π i = 2 * i == 2*1 * 2*2 * 2*3 * 2*4 * 2*5 * 2*6 * 2*7 * 2*8 * 2*9 * 2*10 == 3715891200
i = 1
}
— factorial:
[int!]
<int>! == Π = i
i = 1
• the product of all numbers from <int> to 1
{ 4! == 4*3*2*1 == 24 }
{
unsigned long long factorial(int num){
int product = 1;
for(int i = 1; i <= num; i++){
product = product * i;
}
return product;
}
}
probability
#define probability\
#define combinatorics:: \
I------------------------------------------------------------------------\
I _____ _ _ _ _ \
I / __ \ | | (_) | | (_) \
I | / \/ ___ _ __ ___ | |__ _ _ __ __ _| |_ ___ _ __ _ ___ ___ \
I | | / _ \| '_ ` _ \| '_ \| | '_ \ / _` | __/ _ \| '__| |/ __/ __| \
I | \__/\ (_) | | | | | | |_) | | | | | (_| | || (_) | | | | (__\__ \ \
I \____/\___/|_| |_| |_|_.__/|_|_| |_|\__,_|\__\___/|_| |_|\___|___/ \
I------------------------------------------------------------------------I
### Decision tree for combinatorics ###
Is order important?
├── yes ── Do I have to use up ever element?
│ ├── yes ── "Permutation"
│ └── no ── "Variation"
└── no ── "Combination"
#
Permutation: Permutation:
Unique:
len(${elems})!
• number of possible orders for the set ${elems}
{
_______ _______ _______ _______
/ A /, / B /, / C /, / D /,
/ // / // / // / //
/______// /______// /______// /______//
(______(/ (______(/ (______(/ (______(/
└─────────┘ └─────────┘ └─────────┘ └─────────┘
Slot #1 Slot #2 Slot #3 Slot #4
4! == 4*3*2*1
}
Repetitive:
{
len(${elems})!
────────────────────────────
Π(sum_by_group(${elems}))
}
• Π is the mathematical notation for product
{
_______ _______ _______
/ 1984 /, / FUTU /, / A /,
/ //, / .RE //, / //|
2 x /______/// 2 x /______/// /______///|
(______(// (______(// (______(///| x 7
(______(/ (______(/ (______(///|
(______(///|
(______(///,
└─────────┘ └─────────┘ └─────────┘ (______(///
Slot #1 Slot #2 Slot #3 (______(//
(______(/
└─────────┘ └─────────┘ └─────────┘
Slot #4 Slot #5 Slot #6
└─────────┘ └─────────┘ └─────────┘
Slot #7 Slot #8 Slot #9
9!
─────────────────────────────
1! * 1! * 1! * 1! * 2! * 3!
9! / (1! * 1! * 1! * 1! * 2! * 3!)
9! / (2! * 3!) == 30240
}
Variation: Variation:
Unique:
{
len(${elems})!
─────────────────────────
(len(${elems}) - ${N})!
}
• num of possible orders of ${N} elements selected from ${elems}
{
10! / (10 - 3)! == (((10 * 9 * 8)))
}
Repetitive:
len(${alpha})^${N}
• num of possible order of len(${alpha}) elements on ${N} positions where one element can be used multiple types
{
2^8 == 256
26^3 * 10^3 == 17'576'000
}
Combination: Combination:
— for the following:
${a}!
────────────────────────
${b}! * (${a} - ${b})!
there is a short hand notation:
/ ${a} \
\ ${b} /
that's a elongated pair of parentheses outside of ascii;
its pronounced "${b} under ${a}" or "${a} choose ${b}"
Unique:
/ len(${elems}) \
\ ${N} /
• num of possible ways to select ${N} elements from the set of ${elems} with different elements
• selecting an ${N} elements and selecting len(${elems}) - ${N} elements yield the same results;
interpret this as selecting 1 book from 10 is mathematically the same as not selecting 9
${n}C${r} : alternative notation
• most calculators will have it denoted as "nCr" on a button
{
/ 100 \
\ 10 /
100!/(10! * 90!) == 17'310'309'456'440
}
Repetitive:
/ len(${elems}) + ${N} - 1 \
\ ${N} /
• num of possible ways to select ${N} elements from the set of ${elems}
where there is an unlimited supply of all elements
{
/ 6 + 3 - 1 \
\ 3 /
8! / ( 3! * (8 - 3)! ) == 56
}
Probability: Probability:
{
alias Probability=P
P(<event>)
<desired possibilities>
─────────────────────────
<all possibilities>
}
• for calculating the num of possibilities combinatorics are used
○ impossible event
• something that can never happen
• represented by '∅'
• P(∅) == 0
• if event-1 requires event-2 to happen then its possibility must be less then or equal to it; formally:
if A ⊂ B then P(A) <= P(B)
• a set containing every possible out come is called complete sample space
("teljes esemény rendszer"^HU)
joined_probability:
P(A ∩ B) := P(A) * P(B)
• "intersection"
• the probability of multiple events yielding desired outcomes
{
________ ________
/ o o o /| / o o o /|
/ o o o /O| / o o o /O|
/_______/ | /_______/ |
| o | | | o | |
| o |O/ | o |O/
| o |/ | o |/
'-------' '-------'
let A := 6 on dice one
let B := 6 on dice two
A = 1/6
B = 1/6
P(A ∩ B) =
1 1 1
─── * ─── = ────
6 6 36
}
union_probability:
P(A U B) := P(A) + P(B) - P(A ∩ B)
• the probability that A, B or both yield desired outcomes
• we add the probabilities and subtract what we "double counted"
{
________ ________
/ /| / /| .-------.
/ / | / / | \ |O O O|
/_______/ | /_______/ | -------> | |
| | | | | | / |O O O|
| | / | | / '-------'
| |/ | |/
'-------' '-------'
let A := 6 on dice one
let B := 6 on dice two
A = 1/6
B = 1/6
P(A U B) =
1 1 1
─── + ─── - ──── =
6 6 36
11
────
36
}
• this is often skipped as P(!A ∩ !B) == 1 - P(A U B)
conditional_probability:
• the probability of A given B
P(A ∩ B)
P(A|B) := ────────────
P(B)
— "teljes valószínűség tétele"^HU
|B|
P(A) := ∑ P(A|B₁)*P(B1)
i=1
bayers_theorem:
P(A) * P(A|B)
P(B|A) := ───────────────
P(B)
{
┐ ┌ ┐ ┌
│ @ & │ │ & @ │
│ @ │ │ @ &│
│ & │ │ & & │
│ & │ │ @ & @│
└───────┘ └───────┘
1st Draw 2nd Draw
.-----------. .----------.
/ \ / \
┐ / ┌ ┐ V / ┌ V
│ @ & │ │ & @ │ __
│ @ │ │ @ &│ ( )
│ & │ │ & & │ /
│ & │ │ @ & @│ |
└───────┘ └───────┘ o
B₁ : the 1st is '&'
B₁ : the 1st is '@'
A : the 2nd is '&'
3
B₁ == ───
5
2
B₂ == ───
5
5
.- B₁ == ────
.-' 10
A <|
'-. 4
'- B₂ == ────
10
P(A) = P(A|B₁)*P(B₁) + P(A|B₂)*P(B₂)
5 3 4 2
= ──── * ─── + ──── * ───
10 5 10 5
23
= ────
55
}
{
Mátyás's arrival 6'40
7 ▲ -- -- -- -- -- -+
│ -^\ \ \.|
│ -^\ \ \.'\
│ -^\ \ \.'\ |
│ -^\ \ \.'\ \
│ -^\ \ \.'\ \ -|6'40
│ -^\ \ \.'\ \ -^
│ -^\ \ \.'\ \ -^ |
6'20┼^\ \ \.'\ \ -^
│ \ \.'\ \ -^ |
│\ \.'\ \ -^
│ \.'\ \ -^ |
│.'\ \ -^
6 └───────┼───────────────➤ Bálint's arrival
6 6'20 7
Mátyás's arrival 6'40
7 ▲ -- -- -- -- -- -+
│\ \ \ \ \-^ .|
│ \ \ \ \-^ .'
│ \ \ \-^ .' |
│\ \ \-^ .'
│ \ \-^ .' -|6'40
│ \-^ .' -^\
│\-^ .' -^\ |
6'20┼^ .' -^\ \
│ .' -^\ \ \|
│ .' -^\ \ \
│ .' -^\ \ \ \ |
│.' -^\ \ \ \ \
6 └───────┼───────────────➤ Bálint's arrival
6 6'20 7
P(!A) = ((2/3 * 2/3)/2)*2
= 2/3 * 2/3
= 4/9
P(A) = 1 - P(!A)
= 1 - 4/9
= 5/9
}
Random_variable: Random_variable:
• a variable that denotes the random outcome of events
• too abstract to be calculated
• makes sense on the domain of asking what is its probability to be a specific value
• see also "../Statistics/Probability distribution"
binominal:
— obeys the following restrictions:
• trial outcomes are binary
• trials are independent
• fixed number of trials
{
let A := success
let bvar := the binominal random variable that denotes the number successes
let n := the number of trials
P(${bvar} == ${k}) :=
/ ${n} \
\ ${k} / * P(${A})^${k} * P(1-P(${A}))^(${n}-${k})
}
{
let A := heads
let bvar := the number of heads
let n := 8
let k := 3
P(${A}) := 0.5
1-P(${A}) := 0.5
P(${bvar} == 3) =
/ 8 \
\ 3 / * 0.5^3 * 0.5^5 =
7
────
32
}
poisson:
— obeys the following restrictions:
• there are no fixed trials, only a time window
• outcomes have a fixed probability to happen within a window
• outcomes are independent
{
let A := expected number of events per time unit
let T := number of time units in question
let λ := A * T
let pvar := poisson random variable that denotes the number of events
P(${pvar} == ${k}) :=
λᵏ
─── * e^(-λ)
k!
}
{
let A := 0.8 / 60 = 0.0133
let T := 90
let λ := 1.197
P(${pvar} == 2) =
1.197²
──────── * e^(-1.197) = 0.216
2!
}
statistics
#define statistics\
I---------------------------------------------\
I _____ _ _ _ _ _ \
I / ___| | | | (_) | | (_) \
I \ `--.| |_ __ _| |_ _ ___| |_ _ ___ ___ \
I `--. \ __/ _` | __| / __| __| |/ __/ __| \
I /\__/ / || (_| | |_| \__ \ |_| | (__\__ \ \
I \____/ \__\__,_|\__|_|___/\__|_|\___|___/ \
I---------------------------------------------I
• all statistical models are wrong, but some are useful
List_estimation:
○ problem:
• have a list of values
• wish to express it as a single value to estimate values encountered in the future
Mode:
• the most common value in the list
• all most common values are considered modes
{
[1, 2, 5, 6, 6, 6, 7, 7, 8] => 6
[1, 1, 2, 3, 4, 4] => [1, 4]
}
Median:
• choose the value(s) in the middle
{
[1, 2, 3]
^^^
[1, 2, 10'000]
^^^
[1, 1, 2, 2, 3, 3, 4, 9]
^^^^^^
}
Midpoint:
• "mid-range"
• assume future values fall between the minimum and maximum of previous values
• choose the point at equal distance from the two
{
let midpoint :=
max(data) + min(data)
───────────────────────
2
}
{
sum
max |
| |
| -+- midpoint
min | |
| | |
}
Mean:
• "average"
— improvement over midpoint:
• if the min or max is wildly different from the rest of the values,
the midpoint will be misleading
• same logic applied to the whole list
• the value that minimizes the combined distance from all values
{
let mean :=
μ =
sum(data) / len(data) =
1
─── * ∑ data
n
}
{
▲
│ x
│
│
│ midpoint
│- - - - - - - - - - - -
│ avg
│````x```````````````````
│ x x
│ x
│ x
│
┼────────────────────────▶
}
Variance:
• measure of how far values are spread out from their average
• we want to express how telling the mean is
• expresses entropy
• the higher the variance, the "riskier" your guess gets
{
let variance :=
σ² =
1
─── * ∑ (data - mean)²
n
}
{
▲ Matching averages
│
│ lower variance
│ /
│ ''/
│ ' ' higher variance
│ ' ' /
│ *'******'* /
│ ***' '***
│ ** ' ' **
│** .' '. **
│...' '...
┼────────────────────────▶
}
Bessels_correction:
• calculating the variance from a sample (and not a population),
the variance will come out under estimated
• over estimation is more useful than under estimation
• we intentianlly inflate with a modified formula
{
let bessels_variance :=
1
─── * ∑ (data - mean)²
n-1
}
Standard_deviation:
• the problem with variance is that because of the square operation,
the units are squared too
• no one knows what an IQ² or kg² looks like
{
let standard_deviation :=
σ =
√(variance)
}
Confidence_interval:
{
_
let X := sample mean
let z := magick number
_ σ
X ± z ───
√n
}
• an estimate of the over all mean, based on the mean of a sample
• a confidence level (percentage) is given to express how likely
the target mean is to be within our estimate
• "For example, suppose we want to estimate the mean weight \
of a certain species of turtle in Florida. \
Since there are thousands of turtles in Florida, \
it would be extremely time-consuming \
and costly to go around and weigh each individual turtle."
• z is a magick number for our ends and purposes;
there are table look ups for it
{
n = len([14.8 12.2 16.8 11.1]) = 4
σ = 22
sample_mean = sum([14.8 12.2 16.8 11.1]) / n
= 54.9 / 4
= 13.725
margin_of_error = z * (σ/√n)
= 1.96 * (22/√4)
= 21.56
confidence_interval = [sample_mean-margin_of_error, sample_mean+margin_of_error]
= [13.725-21.56, 13.725+21.56]
= [-7.835, 35.285]
margin_of_error = distance(confidence_interval) / 2
= 1.6 / 2
= 0.8
margin_of_error = z * (σ/√n)
0.8 = 1.96 * (22/√n)
0.8 = (1.96*22)/√n
√n*0.8 = 1.96*22
√n*0.8 = 1.96*22
√n*0.8 = 43.12
√n = 53.9
n = 2905.21
n ≥ 2906
}
Probability_distribution:
• the set of probabilities for every value of a random variable
• the sum of a probability distribution must always be exactly 1
binominal:
• if the variable is binominal, its called a binominal distribution
and is something that is easy to calculate and plot as there
are a fixed number of possible values for the random variable
{
let n_questions := 10
let success_rate := 1/4
let points := random variable of the amount of points gained
let k[] := 0..n_questions = 0..10
P(points == k[0]) := ?
P(1-success_rate) = 3/4
let is_success[n_questions] : bool := random variables denoting the succes
to each question accordingly
P(points == k[0]) := P(is_success[0] == false ∩ .. is_success[n_questions] == false)
= (3/4)¹⁰
= 0.056
P(points == k[1]) := P(is_success[0] == true)
∩ P(is_success[1] == false .. is_success[n_questions] == false)
= (1/4) * (3/4)⁹
= 0.019
P(points == k[1]) := P(is_success[0] == true)
∩ P(is_success[1] == false .. is_success[n_questions] == false)
* (10 choose 1)
= (1/4) * (3/4)⁹ * 10
= 0.188
1 ˣ 3 ¹⁰⁻ˣ
f(x)= ─── * ─── * 10Cx
4 4
x | y
---+---------
0 | 0.056
1 | 0.187
2 | 0.282
3 | 0.250
4 | 0.146
5 | 0.058
6 | 0.016
7 | 3.0*10⁻³
8 | 3.8*10⁻⁴
9 | 2.8*10⁻⁵
10 | 9.5*10⁻⁷
P(x == k) = aᵏ * bⁿ⁻ᵏ * nCk
0.3 +
| O
|
0.25 | O
|
|
|
0.2 |
| O
|
0.15 | O
|
|
0.1 |
|
|
| O
0.05 O
|
| O O O O O
0 +-------------------------------------------------------------------+
0 2 4 6 8 10
P(points > 4) = P(points = 5) + .. P(points = 10)
= 0.078
}
— uniform:
P₀(x) == ... == P(x)ₙ
• each outcome is equally likely
Probability_density_function:
n := the number of possible outcomes
Discrete:
1
f(x) := ───
n
Continous:
1
f(x) := ───────
b - a'
— normal:
• "bell curve"/"Gaussian distribution"
• continous by definition
• symmetrical by definition
1 / (x-mean)² \
f(x) := ───────── e^( - ────────── )
√(2πσ²) \ 2σ² /
— defined by a mean and a variance:
N(mean, σ)
• according to the central limit theorem, under appropriate conditions,
the distribution of a normalized version of the sample mean converges
to a standard normal distribution, even if the original variables
themselves are not normally distributed
— poisson:
• right skewed
expected_value:
• "mean of the variable"
• each outcome must be tokenized
• the value to which the random variable will converge on a large enough scale
• weighted sum of out comes
{
let n := number of outcomes
let o[${i}]'p := ${i}'th outcome probability
let o[${i}]'w := ${i}'th outcome weight
${n}
E(${v}) := ∑ o[${i}]'w * o[${i}]'p
i=1
}
{
let L := loosing our money
let D := doubling our money
let T := tripling our money
L := -1
D := 2
T := 3
P(L) := 4/6
P(D) := 1/6
P(T) := 1/6
E(X) := 4/6*-1 + 1/6*2 + 1/6*3 ~ 0.166
}
variance:
{
let n := number of outcomes
let o[i]'p := i'th outcome probability
let o[i]'w := i'th outcome weight
let E := expected value
${n}
V(${v}) := ∑ (o[${i}]-E)'w^2 * o[${i}]'p
i=1
O = √V(x)
}
Continous:
• is the x
if f(x) exists
x
such that F(x) = ∫ f(t) dt
— ∞
Hypothesis_testing:
H₀ : θ ∈ Θ₀
H₁ : θ ∈ Θ₁
• a hypothesis is a statement we wish to accept or reject
• the null hypothesis is the claim that an effect does not exists,
and its due to statistical noise;
denoted by H₀
• the alternative hypothesis is the claim that an effect does exists;
denoted by H₁
def T(x, rejection_region):
return x in rejection_region
F_test:
• preliminary test for t-tests when we cannot be sure
whether the variations are even comperable
{ we are compairing 2 samples }
{
max(s²-a, s²-b)
F(x) := ─────────────────
min(s²-a, s²-b)
(F(x) < F_critical(degrees_of_freedom))
? t-test
: welch-test
;
}
Z_test:
• note: rarely used as σ is usually unknown
{
_
X - μ
Z(x) := ────────
(σ / √n)
}
○ citical regions
Xᵣ = {X : z > uˇ(1-α) }
Xᵣ = {X : z < -uˇ(1-α) }
Xᵣ = {X : |z| > uˇ(1-α/2) }
— z table:
z_table(z) := p-value
• the p-value is the probability that a sample would be atleast
z value distance from the mean
• calculation of p-values require integration;
having a table handy is easier
T_test:
• Z test modified to use an approximated standard deviation
based on the sample data
{
let s := standard deviation of sample
_
X - μ
T(x) := ────────
(s / √n)
}
○ citical regions
Xᵣ = {X : t > tˇ(n-1, 1-α) }
Xᵣ = {X : t < -tˇ(n-1, 1-α) }
Xᵣ = {X : |t| > tˇ(n-1, 1-α/2) }
welch_test:
pass
chi_squared_test:
• "X² test"/"Pearson's chi-squared test"
• examines frequencies
{
let expected_frequency[outcomes] := E
n (Vᵢ-Eᵢ)²
Tₙ := ∑ ─────────
i=1 Eᵢ
}
{
===================================================
| Last months results |
===================================================
| Number of defects | 0 | 1 | 2 | 3 | 4 |
| Frequency | 80 | 113 | 77 | 27 | 3 |
===================================================
Eᵢ = ?
E₁ == E₂ == Eₙ
1 1
Eᵢ = n * ─────────── = 300 * ─── = 300 * 0.2 = 60
len(data) 5
(80 - 60)² (113 - 60)² (77 - 60)² (27 - 60)² (3 - 60)²
Tₙ = ─────────── + ──────────── + ─────────── + ─────────── + ──────────
60 60 60 60 60
= 130.6
df = len(data)-1 = 4
X₍₄;₀.₉₅₎ = 9.49
130.6 > 9.49 => H₀ is rejected
let n = 5
fails
estimated_fail_rate = ───────
all
(80 * 0) + (113 * 1) + (77 * 2) + (27 *3) + (3 * 4)
= ─────────────────────────────────────────────────────
300 * 4
= 0.3
probabilityₖ = (n choose k) * P(success)^k * P(1-success)^(n - k)
= (5 choose k) * 0.3^k * 0.7^(5-k)
probability = [0.168, 0.36, 0.3, 0.132, 0.028]
frequency = probability * 300
= [50.4 108 90 39.6 8.4]
(80 - 50.4)² (113 - 108)² (77 - 90)² (27 - 39.6)² (3 - 8.4)²
Tₙ = ──────────── + ──────────── + ────────── + ──────────── + ──────────
50.4 108 90 39.6 8.4
= 26.973
26.973 > 9.488 => H₀ is rejected
}
{
+----------+---------+-----+
| Age | Tea Cf | ∑ |
+----------+---------+-----+
| Under 30 | 50 30 | 80 |
| 30-50 | 40 60 | 100 |
| Over 50 | 20 50 | 70 |
+----------+---------+-----+
| Totals | 110 140 | 250 |
+----------+---------+-----+
row total * col total
Eᵢₕ = ───────────────────────
grand total
(Vᵢₕ-Eᵢₕ)²
Tₙ := ∑ ───────────
i h Eᵢₕ
V =
┌ ┐
│ 50 30 │
│ │
│ 40 60 │
│ │
│ 20 50 │
└ ┘
E =
┌ ┐
│ 35.2 44.8 │
│ │
│ 44 56 │
│ │
│ 30.8 39.2 │
└ ┘
|
| - V
|
V
┌ ┐
│ 14.8 -14.8 │
│ │
│ -4 4 │
│ │
│ -10.8 10.8 │
└ ┘
|
| square
|
V
┌ ┐
│ 219.04 219.04 │
│ │
│ 16 16 │
│ │
│ 116.64 116.64 │
└ ┘
|
| div Eᵢₕ
|
V
┌ ┐
│ 6.22 4.89 │
│ │
│ 0.36 0.29 │
│ │
│ 3.79 2.98 │
└ ┘
|
| ∑
|
V
18.53
Tₙ = 18.53
18.53 > 5.991 => H₀ is rejected; There is a connection.
}
geometry
#define geometry:: \
I--------------------------------------------------------\
I _____ _ \
I | __ \ | | \
I | | \/ ___ ___ _ __ ___ ___| |_ _ __ _ _ \
I | | __ / _ \/ _ \| '_ ` _ \ / _ \ __| '__| | | | \
I | |_\ \ __/ (_) | | | | | | __/ |_| | | |_| | \
I \____/\___|\___/|_| |_| |_|\___|\__|_| \__, | \
I __/ | \
I |___/ \
I--------------------------------------------------------I
Vectors:
• a struct which has a direction and a length
• for its definition 2 points and specifying direction is required
• an optimization of defining it is to have one of the points be the origin and the direction is always away from it;
this way a single point given is sufficient
{
v = (2;2)
Y ▲
| (2;2)
| P
| /
1 + /
|/
--------------+-+-------------➤
| 1 X
|
|
|
|
|
}
operator+:
• 2 vectors can be added by adding their coordinates
• graphically representing that means the second vector starts from the first and the end coordinate is the result
{
let v = (2;2)
let w = (4;0)
v + w:
Y ▲
| (2;2) (6;2)
| P-------D
| /
1 + /
|/
--------------+-+-------------➤
| 1 X
|
|
|
|
|
w + v:
Y ▲
| (6;2)
| P
| /
1 + /
| /
--------------+-|-----D-------➤
| 1 (4;0) X
|
|
|
|
|
visualization of commutativity:
Y ▲
| (2;2) (6;2)
| P-------B
| / /
1 + / /
|/ /
--------------+-|-----D-------➤
| 1 (4;0) X
|
|
|
|
|
}
operator||:
• start point
• end point
• Pythagoras theorem
• "length"
• a 1 dimensional vectors length is the distance between its start and end points
• for calculating an <int> dimensional vectors length <int>-1 applications of the Pythagoras theorem is needed
{
P (16;8)
/
/
/
/
/
/
/
(0;0) X
b P (16;8)
/:
/ :
C / :
/ : A
/ :
/ ,:
/ |.:
(0;0) X- - - -+
a B c
sizeof(A) = | a["y"] - b["y"] | = 8
sizeof(B) = | a["x"] - b["x"] | = 16
|C| = ˇ(sizeof(A)^2 + sizeof(B)^2) ~ 17.8
}
operator x([vector-1], vector-2):
• "scalar product" or "dot product"
let γ := (angle enclosed by the 2 vectors)
[vector-1] x [vector-2] == |[vector-1]| * |[vector-2]| * cos(γ)
or
let n := (number of dimension in question)
[vector-1] x [vector-2] == [x-1]*[x-2] + [y-1]*[y-2] + ... [?-1]*[?-2]
{
let |v| := 4
let |w| := 5
P
/
/ v
/
/ '.
/ .
/ 60° , w
+--------------------->
v x w ==
|v| * |w| * cos(γ) ==
4 * 3 * cos(60°) == 6
}
algebra
#define algebra:: \
I----------------------------------------\
I ___ _ _ \
I / _ \| | | | \
I / /_\ \ | __ _ ___| |__ _ __ __ _ \
I | _ | |/ _` |/ _ \ '_ \| '__/ _` | \
I | | | | | (_| | __/ |_) | | | (_| | \
I \_| |_/_|\__, |\___|_.__/|_| \__,_| \
I __/ | \
I |___/ \
I----------------------------------------I
where A, B, C ∈ C
(A + B)^2 = A^2 + 2*AB + B^2
(A - B)^2 = A^2 - 2*AB + B^2
(A + B)^3 = A^3 + 3*A^2*B + 3*A*B^2 + B^3
(A - B)^3 = A^3 - 3*A^2*B + 3*A*B^2 + B^3
(A + B)(A - B) = A^2 - B^2
Squre_root:
— B ± ˇ(B^2 - 4*AC)
A*x^2 + B*x + C = ────────────────────
2*A
calculus
#define calculus:: \
I------------------------------------------\
I _____ _ _ \
I / __ \ | | | | \
I | / \/ __ _| | ___ _ _| |_ _ __ \
I | | / _` | |/ __| | | | | | | / __| \
I | \__/\ (_| | | (__| |_| | | |_| \__ \ \
I \____/\__,_|_|\___|\__,_|_|\__,_|___/ \
I------------------------------------------I
{ [ !]
A
|
these -> ![ ]
— in this context- are equal to their closing counter parts, cause i dont want to forever fuck up my highlighting
}
• some subtopics are probably organized wrong
ASSIGNMENT: ASSIGNMENT:
[var] := [value]
• makes a variable hold a value
• since its asymmetrical (('A':='B') != ('B':='A') != ('A'=:'B')), it deserves an asymmetrical operator
• _MOST_ programming languages use '=' instead, always assigning to the left side;
there is a good reason for it: its much easier to type
ORDERED_PAIR: ORDERED_PAIR:
([...1],[...2])
([...1],[...2]) != ([...2],[...1])
• fixed order
• most commonly used when working with a matrix
• [...1] is called the first component
• [...2] is called the second component
{ (2,4) }
SIGNUM: SIGNUM:
• the naming refers to the sign
• useful for determining direction
def sgn(x):
if x > 0: return 1
if x == 0: return 0
if x < 0: return -1
○ formally
/ 1 if 'x' > 0
sgn('x') { 0 if 'x' == 0
\ -1 if 'x' < 0
where 'x' ∈ R
DISTANCE: DISTANCE:
def distance(x, y): return abs(x - y)
○ formally
d('x', 'y') := |'x' - 'y'|
where 'x', 'y' ∈ R
SURROUNDING: SURROUNDING:
{ S₂(36) == ![34, 38!] }
○ formally
Sˇ'r'('x') := { 'y' ∈ R | d('x', 'y') < 'r' }
Sˇ'r'('x') == !['x' - 'r', 'x' + 'r'!]
where 'x' ∈ R
INFINITY: INFINITY:
• concept, not a number
— defined operations:
{
(-∞) < 'x' < (+∞)
'x' + (+∞) := +∞ + 'x' := +∞
'x' + (-∞) := -∞ + 'x' := -∞
'x'
───── := 0
+∞
'x'
───── := 0
. -∞
'x'ˇ+ (+∞) := (+∞)'x'ˇ+ := +∞
'x'ˇ+ (-∞) := (-∞)'x'ˇ+ := -∞
'x'ˇ- (+∞) := (+∞)'x'ˇ- := -∞
'x'ˇ- (-∞) := (-∞)'x'ˇ- := +∞
(+∞) + (+∞) := +∞
(-∞) + (-∞) := -∞
. -(+∞) := -∞
. -(-∞) := +∞
(+∞)(+∞) := (-∞)(-∞) := +∞
(+∞)(-∞) := (-∞)(+∞) := -∞
where 'x' ∈ R
where 'x'₊ ∈ R₊
where 'x'₋ ∈ R₋
}
— significant undefined operations:
{
(+∞) + (-∞)
(-∞) + (+∞)
0(+∞)
0(-∞)
(+∞)0
(-∞)0
+∞/+∞
. -∞/-∞
+∞/-∞
. -∞/+∞
}
FUNCTIONS: FUNCTIONS:
<name> : <set-1> -> <set-2>
• any equation that associates any 'x' value with an 'y' value
• can be defined as a set of ordered pairs (see AT "../Ordered Pairs")
• can be defined as a relation (see AT "../Relations")
• we associate all elements of 'A' set with a element of 'B' set
• however, if we were to associate an element if 'A' with more than 1 element in 'B' that wouldn't be a function
(try to write a function without extern/static variables in any language that returns different values
when given the same parameters, to see why; good luck bro
)
{
F := {(1,2),(2,3),(3,4)}
int F(int x) {
return x+1;
}
G(x) := x+3
G := {(1,4),(2,5),(3,6)...}
( int G(int x) {
return x+3;
}
)
H(x) := √x
.
where x ∈ N
H(x) := √x
}
• can be visualized in a coordinate system
{
F := {(1,2)}
Y ▲
|
|
|
2 + o
|
--------------+--+------------➤
| 1 X
|
|
|
|
|
}
• a real function is a function whichs X and Y values are all real numbers
— nesting:
func1 o func2 := func1(func2())
(func1 o func2)('x') := func1(func2('x'))
• the end result of the later becomes the starting value of the former
{
R := {(1,2),(2,3),(3,4)}
S := {(2,1),(3,2),(5,1)}
RoS == R(S(x)) == {(2,2),(3,3),(5,2)}
SoR == S(R(x)) == {(1,1),(2,2)}
}
Inversion: Inversion:
func^-1
(func^-1 o func)('x') == (func o func^-1)('x') == 'x'
• the inverse of a function is function which if passed the original with a value
it always returns the same value
• the inverse of a function doesnt always exist { f('x') := x^2 has no inverse (cause g('x') := √x is not a funtion) }
### Inversion ###
{ F(x)=5+6x }
1. Replace the function part with a variable { y = 5+6x }
2. Swap that variable with 'x' { x = 5+6y }
3. Reorder to <var> { y = (x-5)/6 }
• now y == func^-1 { F(x)^-1 = (x-5)/6 }
— invertablility:
• function 'F' is invertible if 'F'^-1 is also a function
### Checking_process ###
1. Invert
2. Visualize in a coordinate system { fuck no }
3. if there're multiple 'y' values assigned to a single 'x' it is NOT a function and
the original is NOT invertible
Monotony: Monotony:
• if element number <int> is always lesser than <int>-1 then the function is strictly monotone decreasing
• if element number <int> is always greater than <int>-1 then the function is strictly monotone increasing
• if element number <int> is always lesser than or equal to <int>-1 then the function is monotone decreasing
• if element number <int> is always greater than or equal to <int>-1 then the function is monotone increasing
• a function is monotone if its monotone decreasing or monotone increasing
• a function is strictly monotone if its strictly monotone decreasing or strictly monotone increasing
— Real sequences:
f:N -> R
<[char]ˇn>
[char]ˇ<int> := f(<int>)
Limit: Limit:
Aproach:
x->y
• "x approaches y"
{
lim f(x) = L
x->[y]⁻
lim f(x) = L
x->[y]⁺
lim f(x) = L
x->[y]
}
• if left hand limit == right hand limit then limit := left hand limit := right hand limit
else limit := undefined
lim f(x) = L
x->y
if 0 < |x - y| < δ; then |f(x) - L| < ε
• the limit of a const function is always the const value it takes up
{ f(x):=2; lim f(x) = 2}
• the limit of a [function] at <int>; where [function](<int>) is valid is always [function](int)
{ f(x) := 4 x + 2
lim f(x) == (8*4 + 2) == 34
x->8
}
— extract from billiant.org/wiki/epsilon-delta-definition-of-a-limit
"In other words, the definition states that we can make values returned by the function f(x)\
as close as we would like to the value L by using only the points in a small enough interval\
around xˇ0.\
One helpful interpretation of this definition is visualizing an exchange between two parties, Alice and Bob.\
First, Alice challenges Bob, \"I want to ensure that the values of f(x) will be no farther than ε from L!\"\
If the limit exists and is indeed L, then Bob will be able to respond by giving her a value of δ,\
\"If for all points x is within a δ-radius interval of xˇ0, then f(x) will always be within an ε-interval of L.\"\
If the limit exists, then Bob will be able to respond to Alice's challenge no matter how small she chooses ε.
>when the tangent (the line that intersects a curve exactly once| of a function at a secific point
is in question, the limit is the second point of the tangent
{
F(x) = x²
lim x² = 1
x->1
Y ▲ / /
| | /
| . /
| / /
1 + |/
|.-ˇ
--V-/+--+---------➤
|/ 1 2 X
}
○ limits at infinity
• found by a series of algebraic operations
○ algebraic operations with limits
{
lim x := ∞ and lim x := -∞
x->∞ x->-∞
lim [num]/x := 0 and lim -[num]/x := 0
x->∞ x->-∞
• its easy to see that if we divide a number with increasingly larger numbers,
the result will always be increasingly smaller, but never 0
lim [num]/x := ∞ and lim [num]/x := -∞
x->0^+ x->0^-
where |[num]| > 1
lim [num]^x = ∞ and lim [num]^x = 0
x->∞ x->-∞
where |[num]| < 1
lim [num]^x = 0 and lim [num]^x = ∞
x->∞ x->-∞
}
○ policeman thesis
• if <aˇn> ≤ <bˇn> ≤ <cˇn> and lim <aˇn> == lim <cˇn>; then lim <bˇn> == lim <aˇn> ( and lim <bˇn> == lim <cˇn> )
x->∞ x->∞ x->∞ x->∞ x->∞ x->∞
___
lim <aₙ> := inf (<aₙ>*)
lim <aₙ> := sup (<aₙ>*)
‾‾‾
LHospitals_rule:
f(x) f'(x)
lim ────── == lim ───────
x->c g(x) x->c g'(x)
Derivative: Derivative:
f(x + h) - f(x)
f'(x) := lim ─────────────────
h->0 h
• measurement of the rate of change "in an instant"
• the process is called differentation
• the result of differentation is the derivative
• if the limit doesnt exist then the derivative doesnt exist either
○ easy mode
• the derivative of const-s is always 0
const -> none
• the derivative of <var> raised to the power of <num> is always
<num> times <var> raised to the power of <num> minus 1
xʸ -> y * xʸ⁻¹
• the derivative of an exponential function <func> is
<func> times ln(<func>)
aˣ -> aˣ * ln(a)
{
y ▲
│ X
│ /
│ /
│ /
│ /
│ /
│ /
│ /
│ X
│ /
│/
┼────────────────────────▶ x
y ▲
│ /
│ /|
│ / |
│ / |
│ / | △y
│ / |
│ / |
│ / |
│ /_______|
│ / △x
│/
┼────────────────────────▶ x
△y := 8
△x := 4
△y 8
──── == ─── == 2
△x 4
y ▲ .
│ .'
│ .'
│ .'
│ .'
│ '
│ f(x) '
│ '
│ .---. ,'
│ .' ''`
│ .
│.
┼────────────────────────▶ x
y ▲ .
│ .'
│ .'|
│ .' | △y
│ .' |
│ '___|
│ f(x) ' △x
│ '
│ .---. ,'
│ .' ''`
│ .
│.
┼────────────────────────▶ x
_.-^---....,-
_-- ^--_
< >.
| |
△y 0 \._ _./
──── == ─── == ``-. . , ; --''
△x 0 | | |
.=|| | |-.
`=#$%&%$#-'
| ; :|
____.,#%&$@%#&~,.____
f'(x) := the slope of the point corresponding to f(x)
simply the distance of y values
calculated as the result difference
at x and x + <our approximation of 0>
for our current function
/
△y f(x + △x) - f(x)
f'(x) := ──── == ──────────────────
△x △x
f(x + h) - f(x)
f'(x) := lim ─────────────────
h->0 h
}
{
f(x) := 2x² - 16x + 35
2(x+h)² - 16(x+h) + 35 - (2x² - 16x + 35)
f'(x) = lim ──────────────────────────────────────────────
h->0 h
2x² + 4xh + 2h² - 16x - 16h + 35 - 2x² + 16x - 35
= lim ───────────────────────────────────────────────────────
h->0 h
4xh + 2h² - 16h
= lim ──────────────────
h->0 h
h(4x + 2h - 16)
= lim ─────────────────
h->0 h
= lim 4x + 2h - 16
h->0
= 4x - 16
t
g(t) := ───────
t + 1
g(t + h) - g(h)
g'(t) = lim ─────────────────
h->0 h
(t+h) t
─────────── - ───────
(t+h) + 1 t + 1
= lim ─────────────────────────
h->0 h
1 / t + h t \
= lim ─── ( ─────────── - ─────── )
h->0 h \ t + h + 1 t + 1 /
1 / (t + h)*(t + 1) - t(t + h + 1 ) \
= lim ─── ( ───────────────────────────────── )
h->0 h \ (t + h + 1)*(t + 1) /
1 / t² + th + t + h - t² - h - t \
= lim ─── ( ──────────────────────────────── )
h->0 h \ (t + h + 1)*(t + 1) /
1 / h \
= lim ─── ( ───────────────────── )
h->0 h \ (t + h + 1)*(t + 1) /
1
= lim ─────────────────────
h->0 (t + h + 1)*(t + 1)
1
= lim ─────────────────
h->0 (t + 1)*(t + 1)
1
= lim ───────────
h->0 (t + 1)²
h(z) := 4*x⁶ + 2*x² + 3*x + 31
h'(z) = (4*6)*x⁽⁶⁻¹⁾ + (2*2)*x⁽²⁻¹⁾ + (3*1)*x⁽¹⁻¹⁾ + 0
= 24*x⁵ + 4*x¹ + 3*x⁰
= 24*x⁵ + 4*x + 3
j(x) := 3x³² - 54x¹² + 5x - 46
j'(x) = 3(32)x³¹ - 54(12)x¹¹ + 5(1)x⁰ - 0
== 96x³¹ - 648x¹¹ + 5
k(x) := 2t⁶ + 7t⁻⁶
k'(x) = 2(6)t⁵ + 7(-6)t⁻⁷
= 12t⁵ + -42t⁻⁷
= 12t⁵ - 42t⁻⁷
l(x) := 2ˣ
l'(x) = 2ˣ * ln(2)
}
○ formulas
+==================================+=====================================+
| Compound form | Deducted form |
+==================================+=====================================+
| ( f(x) + g(x) )' | f'(x) + g'(x) |
| | |
| | |
| ( f(x) - g(x) )' | f'(x) - g'(x) |
| | |
| | |
| ( <const>*f(x) )' | <const> * f'(x) |
| | |
| | |
| ( f(x)*g(x) )' | f'(x)*g(x) + f(x)*g'(x) |
| | |
| | |
| / f(x) \ ' | f'(x) * g(x) - f(x) * g'(x) |
| ( ────── ) | ─────────────────────────────── |
| \ g(x) / | g²(x) |
| | |
| | |
| f( g(x) )' | f'( g(x) ) * g'(x) |
+----------------------------------+-------------------------------------+
○ trigonometric derivatives
+==========+===================+
| Function | Derivative |
+==========+===================+
| sin(x) | cos(x) |
| cos(x) | -sin(x) |
| tan(x) | 1/(cos²(x)) |
| 1/cos(x) | tan(x) * 1/cos(x) |
+----------+-------------------+
• "derive sine to cosine\
there is no sign"
Partial:
• multi parameter functions
• we only want the derivative for a single var
∂ <function>
"partial derivative of <function> to <var>" := ──────────────
∂ <var>
• each, but the derived var is treated as a const
{
∂f
──── == 2*4x * 2y⁶
∂x
== 16xy⁶
∂f
──── == 4x² * 6*2y⁵
∂y
== 48x²y⁵
}
• as long as a <var> is still present, the derivation can be repeated
{
∂f / ∂f \
──── ( ──── ) == 16y⁶
∂x \ ∂x /
∂f / ∂f \
──── ( ──── ) == 48x²5y⁴
∂y \ ∂y /
== 240x²y⁴
∂f / ∂f \
──── ( ──── ) == 96xy⁵
∂y \ ∂x /
∂f / ∂f \
──── ( ──── ) == 96xy⁵
∂x \ ∂y /
}
Extremum_of_multi_variable_function:
{
f(x, y) := 2x² + y²x + 2y + 6
f'x = 4x + y²
f'y = 2x + 2
I. 4x + y² = 0
II. 2x + 2 = 0
II. 2x = -2 / /2
x = -1
I. -4 + y² = 0
y² = 4
y = ±2
f'x'x = 4
f'y'y = 0
f'x'y = 2
D(x, y) = f'x'x * f'y'y - (f'x'y)²
D₁(-1, ±2) = 4 * 0 - 2² = -4; -4 < 0
}
INTEGRAL: INTEGRAL:
∫( f(x) * dx )
• one would like to calculate the area under a slope
• sum of slices whose width approach 0 (see AT "/Theory/Function/Limit")
• "dx" stays "dx"; no expansion there
• you think you can integrate? you cannot; each exercise you are given is
artificially generated to fit within the "easily" solvable subset of
cases
• "signed area"
{
y ▲
│
│ .-`````-.
│ .'\ \ \ \ \'.
│ .'|\ \ \ \ \ \|'.
│ : | \ \ \ \ \ | :
│ : |\ \ \ \ \ \| :
│ : | \ \ \ \ \ | :
│: |\ \ \ \ \ \| :
┼─────────────────────────▶ x
y ▲
│
│ .-`````-.
│ .'_________'.
│ .'|\ \ \ \ \ \|'.
│ : | \ \ \ \ \ | :
│ : |\ \ \ \ \ \| :
│ : | \ \ \ \ \ | :
│: |\ \ \ \ \ \| :
┼─────────────────────────▶ x
y ▲
│ ___________
│ |\.\`\`\`\.\|
│ |'\ \ \ \ \'|
│ .'|\ \ \ \ \ \|'.
│ : | \ \ \ \ \ | :
│ : |\ \ \ \ \ \| :
│ : | \ \ \ \ \ | :
│: |\ \ \ \ \ \| :
┼─────────────────────────▶ x
y ▲
│
│ .-`````-.
│ .'_|\ | \|_'.
│ .'|\ | \|\ | \|'.
│ : | \|\ | \|\ | :
│ : |\ | \|\ | \| :
│ : | \|\ | \|\ | :
│: |\ | \|\ | \| :
┼─────────────────────────▶ x
to
∫ function
from
A A
1| .. 1| ..
|/ \ |/||\
+----> +-++->
π π
2/π
∫ sin(x)
1/π
2/π
⌠
⌡ sin(x)
1/π
y ▲
│
│ .'''.
│ : :
│: :
┼──────────────────▶ x
│ : :
│ : :
│ '...'
▼
y ▲
│
│ .'''.
│ : :
│: :
┼──────────────────▶ x
│ :\ \ \ \:
│ :\ \ \:
│ '\.\'
▼
}
Eulers_number:
/ 1 \^n
e := lim ( 1 + ─── )
n->∞ \ n /
~ 2.718
• all numbers raised to an arbitrary power,
will have a proportional integral
• e is the only number which raised to an arbitrary power,
will have itself as the integral
∫eⁿ = eⁿ+c
Definite:
[int-1]
∫( f(x) * dx )
[int-2]
• as oppose to indefinite, its range bounded
∞
∫[...] == ∫[...]
0
○
[int-1]
∫( f(x) * dx ) = f([int-1]) - f([int-2])
[int-2]
{
. f:[0,3]->R; f(x) := 3*ˇx
3
∫( f(x) * dx ) = ?
0
3*ˇx == 3*x^(1/2)
3 3
∫( 3*x^(1/2) * dx ) = 3*∫( x^(1/2) * dx )
0 0
┌ x^(1/2) + 1 ┐3
= 3*│ ───────────── │
└ (1/2) + 1 ┘0
/ 3^(1/2) 0^(1/2) \
= 3 * ( ───────── - ───────── )
\ 1/2 1/2 /
= 3 * ((ˇ3 / (1/2)) - 0)
= 2 * 3 * ˇ3 = 6*ˇ3
}
○ formulas
/ \ / \
∫( [const] * f(x) dx ) == [const] * ∫( f(x) dx )
\ / \ /
/ \ / \ / \
∫( f(x) + g(x) dx ) == ∫( f(x) dx ) + ∫( g(x) dx )
\ / \ / \ /
/ \ / \ / \
∫( f(x) - g(x) dx ) == ∫( f(x) dx ) - ∫( g(x) dx )
\ / \ / \ /
/ \ f^(n+1)(x)
∫( f^n(x) * f'(x) dx ) == ──────────── + c
\ / n + 1
/ f'(x) \
∫( ─────── dx ) == ln( |f(x)| ) + c
\ f(x) /
∫ f(x) * g'(x) dx == f(x)g(x) - ∫f'(x) * g(x) dx
○ base integrals
+===========================================+
I Function I Integral I
+===========================================+
| | x^(n+1) |
| xⁿ | ───────── + c |
| | n+1 |
+------------+------------------------------+
| 1 | |
| ─── | ln(|x|) + c |
| x | |
+------------+------------------------------+
| 1 | |
| ─────── | arctg(x) + c |
| x²+1 | |
+------------+------------------------------+
| | aˣ |
| aˣ | ─────── + c |
| | ln(a) |
+------------+------------------------------+
| eˣ | eˣ + c |
+------------+------------------------------+
| tan(x) | ln(|1/cos(x)|) + c |
+------------+------------------------------+
| ctg(x) | ln(|sin(x)|) + c |
+------------+------------------------------+
| sin(x) | -cos(x) + c |
+------------+------------------------------+
| cos(x) | sin(x) + c |
+------------+------------------------------+
| 1 | |
| ────────── | ln(sin(x/2)) - ln(cos(x/2)) |
| sin(x) | |
+------------+------------------------------+
| 1 | / │ 1 │ \ |
| ────────── | ln( │ ──────────────── │ ) |
| cos(x) | \ │ cos(x) + tg(x) │ / |
+------------+------------------------------+
| 1 | |
| ────────── | -ctg(x) + c |
| sin²(x) | |
+------------+------------------------------+
| 1 | |
| ────────── | tg(x) + c |
| cos²(x) | |
+------------+------------------------------+
Solvability_types:
Function_and_derivative:
— one of the following formulas will have to be used:
{
/ \ f^(n+1)(x)
∫( f^n(x) * f'(x) dx ) == ──────────── + c
\ / n + 1
/ f'(x) \
∫( ─────── dx ) == ln( |f(x)| ) + c
\ f(x) /
}
• the key is spotting the function and its derivative
{
∫ cos(x) * sin(x) dx
A A
| |
f'(x) f(x)
sin²(x)
──────────── + c = 1/2 * sin²(x) + c
2
4
∫ ─── dx
x
(x') = 1
1
∫ 4 * ─── dx
x
1 <- f'(x)
4∫ ─── dx
x <- f(x)
4 * ln(|x|) + c
}
Root_as_power:
• the key is knowing that √x = x^½
{
∫ √eˣ dx
∫ e^½x dx
2 * e^½x + c
}
Substitution:
• the equation is suspected to correspond to a result of the chain rule
• the most likely candidate for the inner function is picked to be substituted
• 'u' and 't' are the most common var names to substitute with
{
∫ 2x * cos(x²) dx
∫ 2x * cos(x²) dx
A A A
| | |
g' f g
u = x² dx
du = (x²)'
2x dx
dx = 1/2x du
∫ 2x * cos(u) * 1/2x du
∫ 2x * 1/2x * cos(u) du
∫ 1 * cos(u) du
∫ cos(u) du
sin(u) + c
sin(x²) + c
∫ (3x + 4)³ dx
u = 3x + 4
du = (3x + 4)'
= 3 dx
dx = ⅓ du
∫ (u)³ * ⅓ du
⅓∫ (u)³ du
⅓ * u⁴ * ¼ + c
(1/12)*u⁴ + c
∫ x(x² + 1)¹⁰⁰ dx
u = x² + 1
du = (x²)'
2x dx
dx = 1/2x du
1
∫ x(u)¹⁰⁰ ───── du
2x
x
∫ (u)¹⁰⁰ ───── du
2x
1
∫ (u)¹⁰⁰ ─── du
2
½ ∫ (u)¹⁰⁰ du
½ * 1/101 * (u)¹⁰¹ du
1/202 * (x² + 1)¹⁰¹ + c
1
∫ ──────── dx
x + √x
1
∫ ────────── dx
√x(√x+1)
u = √x+1
du = (√x+1)'
(x^½+1)'
x^-½
= ────── dx
2
= ½ * x^-½ dx
1 1
= ─── * ───── dx
2 √x
1
= ───── dx
2√x
dx = 2√x du
1
∫ ───────── 2√x du
√x * u
1
∫ ───────── 2 du
u
1
2∫ ─── du
u
2 ln(|u|) + c
2 ln(|√x+1|) + c
}
By_parts:
— the following is utilized:
∫ f(x) * g'(x) dx == f(x)g(x) - ∫f'(x) * g(x) dx
{
∫ x*sin(x) dx
∫ x*sin(x) dx
A A
| |
f(x) g'(x)
f(x) := x g'(x) := sin(x)
f'(x) = 1 g(x) = -cos(x)
— x*cos(x) - ∫ -cos(x) dx
— x*cos(x) + ∫ cos(x) dx
— x*cos(x) + sin(x) + c
}
Rational_functions:
?!:
{
7x-6
∫ ──────── dx
x²+x-6
— b±√(b² - 4ac)
√(x²+x-6) = ────────────────
2a
— 1±√(1 - 4*1*-6)
= ──────────────────
2
— 1±√(25)
= ──────────
2
/ \
2 -3
7x-6
∫ ──────────── dx
(x-2)(x+3)
7x-6 A B
──────────── = ───── + ─────
(x-2)(x+3) x-2 x+3
7x-6 A(x+3) + B(x-2)
──────────── = ──────────────────
(x-2)(x+3) (x-2)(x+3)
7x-6 Ax+3A + xB-2B
──────────── = ──────────────────
(x-2)(x+3) (x-2)(x+3)
7x-6 x(A+B) + 3A - 2B
──────────── = ──────────────────
(x-2)(x+3) (x-2)(x+3)
7x-6 = x(A+B) + 3A - 2B
I. 7 = A+B
II. 6 = 3A - 2B
I. B = 7-A
6 = 3A - 7A
6 = -4A
A = 8/5
B = 27/5
7x-6 8/5 27/5
──────────── = ───── + ──────
(x-2)(x+3) x-2 x+3
8/5 27/5
∫ ───── + ────── dx
x-2 x+3
8 1 27 1
∫ ─── * ───── + ─── * ───── dx
5 x-2 5 x+3
8 1 27 1
─── ∫ ───── dx + ─── ∫ ───── dx
5 x-2 5 x+3
8 1 27 1
─── ∫ ───── dx + ─── ∫ ───── dx
5 x-2 5 x+3
(8/5) ln(|x-2|) + (27/5) ln(|x+3|) dx
}
Solid_of_revolution_volume:
pass
complex_numbers
#define complex_numbers:: \
I---------------------------------------------\
I _____ _ \
I / __ \ | | \
I | / \/ ___ _ __ ___ _ __ | | _____ __ \
I | | / _ \| '_ ` _ \| '_ \| |/ _ \ \/ / \
I | \__/\ (_) | | | | | | |_) | | __/> < \
I \____/\___/|_| |_| |_| .__/|_|\___/_/\_\ \
I | | \
I |_| \
I---------------------------------------------I
{
let i := √(-1)
<num> + <num>*i
▲ ▲
│ │
real portion │
imaginary portion
}
• complex numbers is a super set of real numbers
• all complex numbers have an imaginary portion of value 0 (5 == 5+0*i)
Operators: Operators:
Addition:
(A + H*i) + (B + J*i) = (A+B) + (H+J)*i
• the real portions and the imaginary portions are added together separately
{ (10 + 4*i) + (2 + i) = 12 + 5*i }
Subtraction:
(A + H*i) - (B + J*i) = (A-B) + (H-J)*i
• the real portions and the imaginary portions are subtracted separately
{ (32 + 5*i) - (13 + 7*i) = 19 - 2*i }
Multiplication:
(A + H*i) * (B + J*i) = (A*B) + (A*J)+(B*H)*i + (H+J)*i²
• as (i == √(-1)), multiplying 2 imaginary numbers will result in a real number (i^2 == (√(-1))^2 == -1)
{ (6 + 8*i) * (4 + 2*i)
= (6*4) + 12*i + 32*i + 16*i²
= 24 + 44*i + 16*i²
= 24 + 44*i + 16*(-1)
= 24 + 44*i - 16
= 8 + 44*i
}
Division:
(A + H*i) / (B + J*i) = ((A + H*i)*(B - J*i)) / ((B + J*i)*(B - J*i))
• the idea is to multiply the expression with 1 such a way to get rid of the i-s from the denominator;
ie. we multiply by the denominators complex conjugate over itself, relying on (A+B)*(A-B) = A^2 - B^2
{ (10 + 6i) ÷ (5 – 3i)
10 + 6*i
= ─────────
5 – 3*i
10 + 6*i 5 + 3*i (10 + 6*i)*(5 + 3*i)
= ───────── * ───────── = ──────────────────────
5 – 3*i 5 + 3*i (5 – 3*i)*(5 + 3*i)
50 + 30*i + 30*i + 18*i²
= ──────────────────────────
25 - 9*i²
50 + 60*i + 18*(-1)
= ─────────────────────
25 - (9*-1)
32 + 60*i
= ───────────
34
32 60*i
= ──── + ──────
34 34
16 / 30 \
= ──── + ( ──── * i )
17 \ 17 /
}
Trigonometric_form: Trigonometric_form:
where Z, W ∈ C
where 270° < d < 360°
Z = |Z|*(cos(d) + sin(d)*i)
|Z| = ˇ(A² + B²)
d = tg^-1( A/B )
Multiplication:
Z*W = |Z|*|W|(cos(d1 + d2) + sin(d1 + d2)*i)
{ Z = 2(cos(100°) + sin(100°)*i)
W = 4(cos(280°) + sin(280°)*i)
Z*W = 2*4(cos(100°+280°) + sin(100°+280°)*i)
= 8(cos(380°) + sin(380°)*i)
= 8(cos(20°) + sin(20°)*i)
}
Division:
Z/W = |Z|/|W|(cos(d1 - d2) + sin(d1 - d2)*i)
{ Z = 3(cos(75°) + sin(75°)*i)
W = 6(cos(300°) + sin(300°)*i)
Z/W = 3/6(cos(75°-300°) + sin(75°-300°)*i)
= 2(cos(-225°) + sin(-225°)*i)
= 2(cos(135°) + sin(135°)*i)
}
Power:
Z^n = |Z|^n(cos(d*n) + sin(d*n)*i)
{ Z = 4(cos(30°)+sin(30°)*i)
Z⁵ = 4⁵(cos(30°*5)+sin(30°*5)*i)
= 1024(cos(150°)+sin(150°)*i)
}
Root:
where k ∈ [0 ... n-1]
n ___ n ___ / / d k \ / d k \ \
\/ Z = \/|Z| { cos( ─── + ─── ) + sin( ─── + ─── ) }
\ \ n n / \ n n / /
there are 'n' answered, if ones looking for the roots of Z, each are desired
numeric_bases
#define numeric_bases\
#define numerical_bases:: \
I------------------------------------------------------------------------\
I _ _ _ ______ \
I | \ | | (_) | ___ \ \
I | \| |_ _ _ __ ___ ___ _ __ _ ___ | |_/ / __ _ ___ ___ ___ \
I | . ` | | | | '_ ` _ \ / _ \ '__| |/ __| | ___ \/ _` / __|/ _ \/ __| \
I | |\ | |_| | | | | | | __/ | | | (__ | |_/ / (_| \__ \ __/\__ \ \
I \_| \_/\__,_|_| |_| |_|\___|_| |_|\___| \____/ \__,_|___/\___||___/ \
I------------------------------------------------------------------------\
Converting_base_10_integer_to_base_n:
it grows vertically
[starting_number] | :[base_n]
-------------------+-----------
[quotient] | [remainder] +
• repeated divideations while keeping the remainders
• the results are read out backwards
{ 123ˇ10 = ?ˇ8
123 | :8
-----+----
15 | 3 A
1 | 7 I
0 | 1 I
=> 173ˇ8
}
Converting_base_10_number_which_is_smaller_than_1_to_base_n:
it grows vertically
0 | [starting_number]*[base_n]
-------------------------+----------------------------
([results_whole_part])+ | ([results_fraction_part])+
• repeated multiplications
• the results are read out backwards
• the algorithm ends when there's 0 on the right side ([results_fraction_part]);
which may never come
{ 0.6875₁₀ = ?₈
0 | 0.6875 * 8
-----+----
5 | 5 A
4 | 0 I
=> 0.05
}
Converting_base_n_to_base_10_using_a_horner_table:
| <digit-1> | <digit-2> | | <digit-n> |
-------+-----------+-----------+ +-----------+
<base> | / / / / / | <prod-1> | ... | <prod-n> |
-------+-----------+-----------+ +-----------+
| <sum-1> | <sum-2> | | <sum-n> |
1. write up the digits
2. write up base
3. a <sum> is always the sum of the <digit> and the <prod> above it
4. a product is always the last multiple of <base> and the <sum> left to it
|XXX|XXX|XXX|XXX:
— - - - - - - - - -
: I :/I :/I :/I :
— - -I-/-I-/-I-/-I-
: I/: I/: I/: I :
{
75320041₈
| 7 | 5 | 3 | 2 | 0 | 0 | 4 | 1 |
-----+-------+-------+-------+-------+-------+--------+---------+----------+
8 | / / / | 56 | 488 | 3928 | 31440 | 251520 | 2012160 | 16097312 |
-----+-------+-------+-------+-------+-------+--------+---------+----------+
| 7 | 61 | 491 | 3930 | 31440 | 251520 | 2012164 | 16097313 |
^^^^^^^^
— write down 7 to the 1st sum
— multiply 7 by 8 (56), write down result to 1st product
— add 5 and 56 (61), write down result to 2st sum
— multiply 61 by 8 (488), write down result to 2st product
— add 488 and 3 (491), write down result to 3th sum
— multiply 491 by 8 (3928), write down result to 3th product
— add 3928 and 2 (3930), write down result to 4th sum
— multiply 3930 by 8 (31440), write down result to 4th product
— add 31440 and 0 (31440), write down result to 5th sum
— multiply 31440 by 8 (251520), write down result to 5th product
— add 25152 and 0 (31440), write down result to 6th sum
— multiply 25152 by 8 (2012160), write down result to 6th product
— add 2012160 and 4 (2012164), write down result to 7th sum
— multiply 2012164 by 8 (16097312), write down result to 7th product
— add 16097312 and 1 (16097313), write down result to 8th sum
— under line 16097313 as it is our solution
}
Conversion_between_square_bases:
• each digit is guaranteed to translate to a fixed number of digits
• per digit (batch) translation will yield the right result
{
0b01010110010
| 01 | 010 | 110 | 010 |
1 2 6 2
1 2 6 2
0b01010110010 == 01262
}
Polynominal:
• sum of numbers and variables raised to non-negative integers
{ f(x) = 2x² * 6x + 9
q(x, y) = 5x⁴ * y⁶ - 3x * y³ + 11y¹⁵ * x⁷
}
Horner_Ruffini_method:
a₀ * x⁰ + a₁ * x¹ + a₂ * x² + ... + aₙ * xⁿ ==
a₀ + x*( a₁ + x*( a₂ + ... + x*( aₙ₋₁ + x*aₙ) ) )
• Horner and Ruffini were both mathematicians
• can be used on single variable polynomials
• optimizes the number of operations
• repeated rearanging
{ f(x) = x³ + 2x² - 3x + 2 == ((1*x + 2) * x - 3 ) * x + 2
f(3) =
1*3*3*3 + 2*3*3 - 3*3 + 2 ==
((1*3 + 2) * 3 - 3 ) * 3 + 2
== 38
}
— an equivalent, but easier to humanly write up form is getting all the x-s and than all the multipliers:
a₀ * x⁰ + a₁ * x¹ + a₂ * x² + ... + aₙ * xⁿ ==
"( x*( )"^n-1 + "x " + "a₀) [...] aˇn"
{ g(x) = x³ - 4x² + x + 4
x*( x* (x - 4) + 1 ) + 4
}
Horner_table_form:
| [int-1] ([int-n])*
x = [int-0] | [int-0] ([int-n])*
-------------+--------------------
[int-2] ([int-n])*
• the first 2 rows are summed together to get the last row
• the last row is multiplied by x to get the values of the second row
{ f(3) = 1*3*3*3 + 2*3*3 - 3*3 + 2
| 1 2 -3 2
x = 3 | 3
-------+------------------
| 1 2 -3 2
x = 3 | 3
-------+------------------
5
| 1 2 -3 2
x = 3 | 3 15
-------+------------------
5
| 1 2 -3 2
x = 3 | 3 15
-------+------------------
5 12
| 1 2 -3 2
x = 3 | 3 15 36
-------+------------------
5 12
| 1 2 -3 2
x = 3 | 3 15 36
-------+------------------
5 12 38
}
• can be used for converting an arbitrary base number to base 10
• the multipliers are the digits
{ 11211220₃
| 1 1 2 1 1 2 2 0
x = 3 | 3 12 42 129 390 1176 3534
-------+----------------------------------------
1 4 14 43 130 392 1178 3534
}
optimization
#define optimization:: \
I--------------------------------------------------------------\
I _____ _ _ _ _ _ \
I | _ | | | (_) (_) | | (_) \
I | | | |_ __ | |_ _ _ __ ___ _ ______ _| |_ _ ___ _ __ \
I | | | | '_ \| __| | '_ ` _ \| |_ / _` | __| |/ _ \| '_ \ \
I \ \_/ / |_) | |_| | | | | | | |/ / (_| | |_| | (_) | | | | \
I \___/| .__/ \__|_|_| |_| |_|_/___\__,_|\__|_|\___/|_| |_| \
I | | \
I |_| \
I--------------------------------------------------------------I
• regards finding optimal solutions
Fishermans_problem:
— a fisherman fishes in a lake with 3 types of fish
• bass
• cod
• herring
— each fish has a different enjoyment value for the fisherman
• bass - 2
• cod - 3
• herring - 4
— the lake has 3 owners, each has a pointing system calculated
after the type of fish and by kilo,
and each pose a maximum point limit on a single days catch
○ owner 1
• max : 4
• bass - 1
• cod - 1
• herring - 2
○ owner 2
• max : 5
• bass - 2
• cod - free
• herring - 3
○ owner 3
• max : 7
• bass - 1
• cod - 2
• herring - 4
• the fisherman wishes to have the most fun while obeying each owners rules
○ formerly represented as:
f(b, c, h): 2b + 3c + 4h -> max
1b + 1c + 2h <= 4
2b + 0c + 3h <= 5
1b + 2c + 4h <= 7
b, c, h >= 0
Salesman_problem:
○ a salesman sells on the spot measured tonics
• 1l water - 1 kg - 1 Shekel profit
• 1l orange - 2 kg - 3 Shekels profit
— a boy walks in and wishes to purchase considering the following:
• he can only carry 5 kg-s
• he must buy at least 3 ls
• he must buy 1 l more water than orange
• the salesman tries to make as much profit as he can
○ formerly
f(w, o): 1w + 3o -> max
1w + 2o <= 5
w + o >= 3
w - o >= 1
w, o >= 0
Linear_programming:
• looking for an extreme in an area defined by linear inequalities on a linear function
• minimum/maximum
• the minimum solution is otherwise called the optimal solution
Graphical_technique:
• the number of dimensions is equal to the number of var-s involved
1. draw a coordinate system
2. draw a line for each constraint as if they were equalities
3. determine the direction of each area constraining
4. draw up the goal function
5. based on the goal functions angle determine the solution
6. if the solution is a single point on a cross section, determine its value
Fourier_elimination:
○ requirements
• each equation must be an inequality
• a equality can be converted by 2 inequalities
{
x = 4
x >= 4
x <= 4
}
Standard_representation:
• every linear programming problem has a standard representation
○ rules
• each variable has to have a >= 0 constraint
• only equalities
• has to be a max problem
○ conversion
• if a var has no constraints; then
swap it with (var' - var'')
• if a var has a constraint, but not for 0; then
reorder to 0,
name the following expression var',
find how to express var as var',
substitute
• if an equation is an inequality; then
case "(=)<": add sˇn
case "(=)>": subtract eˇn
and rewrite as an equality
• if its not a min problem; then
multiply by -1 to get a max problem
Assignment_problem:
{
function Matrix::prepare() {
min : int
min := 0
foreach (c in this.columns()) {
foreach (f in c) {
f -= min(c)
}
}
min := 0;
foreach (r in this.rows()) {
foreach (f in c) {
f -= min(c)
}
}
}
function Matrix::assignment_solver() {
this.prepare()
foreach (c in column) {
foreach (e in c) {
if (e == 0 and not e.row.has_star) {
star(e)
break
}
}
}
while (this.n != this.starts.size()) {
foreach (s in this.stars) {
anchor(s.column)
}
foreach (r in this.rows) {
free_null : elem
free_null = r.find_free()
if (free_null) {
if (r.has_star) {
tick(free_null)
anchor(r)
raise_anchor(r.star.column)
} else {
tick(free_null)
chain : list<elem>
chain := chain_from(free_null)
foreach (s in m.stars) {
if (not chain.is_elem(s)
|| (chain.is_elem(s) && s.is_ticked())) {
star(s)
} else {
clear(s)
}
}
clear(m.anchors)
break
}
}
} else {
free_elements : list<elem>
free_elements = m.find_free()
foreach (e in free_elements) {
e -= min(free_elements)
}
double_anchored_elements : list<elem>
double_anchored_elements = m.find_double_anchored()
foreach (e in double_anchored_elements) {
e += min(free_elements)
}
}
}
}
}
numat
#define numat\
#define nummat\
#define numerical_mathematics:: \
I-------------------------------------\
I _ _ _ \
I | \ | | | | \
I | \| |_ _ _ __ ___ __ _| |_ \
I | . ` | | | | '_ ` _ \ / _` | __| \
I | |\ | |_| | | | | | | (_| | |_ \
I \_| \_/\__,_|_| |_| |_|\__,_|\__| \
I-------------------------------------I
• "numerical mathematics"
• convergence is when an error can be arbitrary small by increasing computational effort
• a value converges to a number if the error decreases towards it,
but its proven it could never succeed it
— absolute error limit / estimated error
let estimated_error & △ = | estimated_max - approximated_value |
let upper_approximated_value = approximatated_value + △
let lower_approximated_value = approximatated_value - △
let absolute_error = δ = |f'(approximated_value)| * △
Taylor_series:
• approximates a functions just with polynomials
• nice, because polynomials are easy to work with
• the polynomial is composed such that incremental Nth derivatives of the functions
know values are the Nth derivates of the polynominal too
let const given c = x coordinate of the point of the function we approximate from
∞ / \
Taylor(f(x)) = ∑ ( f'ⁱ(c) * (x - c) ) / i!
i=0 \ /
• to "Find a taylor series for f(x)", you start by plugging eval-ing the
first few expressions, then try to generalize a simpler form of summation
Maclauirin_series:
• a special taylor series where c := 0
Interpolation:
• we have a partial function
• we wish to estimate values somewhere between the lowest and
the highest x-es we have
11 ├─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ x | y
│ | ---+---
│ O 1 | 6
│ | │ 4 | 3
│ | 7 | 9
│ O ??? | O │ 10 | 6
│ | | |
│ | | | | │ f(3) = ???
│ | O | |
│ | | | | | │
│ | | | |
0 ┼───X─────#──X────┼───x────────x────┴
0 1 2 3 4 5 6 7 8 9 10 11 12
Linear:
• we assume that every datapoint is connected with a straight line
11 ├─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ |
│ O.
│ /| `.. │
│ / | ``.
│ O ./` | `O │
│ |`.. / | |
│ | `.# / | | │
│ | ``O | |
│ | | | | | │
│ | | | |
0 ┼───X─────#──X────┼───x────────x────┴
0 1 2 3 4 5 6 7 8 9 10 11 12
We can calculate the total difference and how much of
this total difference our point in between accounts for.
xₘ₊₁ - xₘ₋₁ yₘ₊₁ - yₘ₋₁
───────────── = ─────────────
xₘ - xₘ₋₁ yₘ - yₘ₋₁
^^^^
└─ only unknown value
{
Our x is 3.
f(3) is going to be between our know y-s f(1) & f(4),
we select them.
Do a table look up, get 6 and 3.
4 - 1 3 - 6
─────── = ───────
4 - 3 ? - 6
3 - 3
─── = ───────
1 ? - 6
1
3 = - 3 * ───────
? - 6
1
1 = - 1 * ───────
? - 6
? - 6 = -1
? = 5
Is 5 between 6 and 3? Yes. Looks good.
}
Cramers_rule:
• used if there are more than 2 dimensions
• the functions is represented as equations
{
3x - y + z = -4
x + y + z = 2
2x + 3y + 4z = 8
}
• the equations are represented as a matrix
{
┌ ┐
│ 3 -1 1 │
│ │
│ 1 1 1 │
│ │
│ 2 3 4 │
└ ┘
}
• the matrix with respect to a variable is the equiation matrix
with a column replaced by the right hand side
• the value of a variable can be calculated as:
let A := the matrix
let k ∈ { matrix variables }
let Aₖ := the matrix with respect to k
k = |Aₖ| / |A|
• |A| must not be 0
• gaussian elimination is faster and easier
Newton_Lagrange:
• we attempt to construct a polynominal that fits on each point of the function
• we construct a polynome for each data point which checks out,
but results in 0 on every point, then we multiply them together
let lₖ(x) := the polynome which matches point k
n; i != k ( x - xᵢ )
= Π ────────────
i = 1 ( xₖ - xᵢ )
let P(x) := lagrange polynomial for function f(x)
n
= ∑ lₖ(x) * f(xₖ)
j=0
{
We have the following partial function:
+------+---+----+----+----+----+
| | x | -2 | -1 | 0 | 4 |
| f(x) +---+----+----+----+----+
| | y | -2 | 4 | 1 | 8 |
+------+---+----+----+----+----+
We are looking for the value a 2.
We will be using the Lagrange method to estimate it.
( x - (-1)) ( x - 0) ( x - 4)
P(x) = -2 * ───────────────────────────────
(-2 - (-1)) (-2 - 0) (-2 - 4)
( x - (-2)) ( x - 0) ( x - 4)
+ 4 * ───────────────────────────────
(-1 - (-2)) (-1 - 0) (-1 - 4)
(x - (-2)) (x - (-1)) (x - 4)
+ 1 * ───────────────────────────────
(0 - (-2)) (0 - (-1)) (0 - 4)
(x - (-2)) (x - (-1)) (x - 0)
+ 8 * ───────────────────────────────
(4 - (-2)) (4 - (-1)) (4 - 0)
3 * 2 * -2
P(2) = -2 ────────────
— 12
4 * 2 * -2
+ 4 ────────────
5
4 * 3 * -2
+ 1 ────────────
6
4 * 3 * 2
+ 8 ───────────
120
24 -64 -24 192
= ──── + ───── + ───── + ─────
— 12 5 -8 120
= - 10.2
^^^^^^^^
}
Least_squre_method:
• "linear regression"
• we are looking for a single line that can describe our data
— works best on the following type of distribution (total shit otherwise):
├─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ x x |
│ x x x x
│ x x x │
│ x
│ x x x │
│ x x
│ x x x │
│
│ x x x x │
│ x
┼───────────────────────────────────┴
• we choose our line so that it has the least squared errors fitting to
all data points combined
{
n ∑xy - ∑x ∑y
let m := ───────────────
n ∑x² - (∑x)²
∑y - m ∑x
let b := ───────────
n
y = mx + b
}
{
x | y | xy | x²
----+------+-------+-----
1 | 1.5 | 1.5 | 1
2 | 3.8 | 7.6 | 4
3 | 6.7 | 20.1 | 9
4 | 9.0 | 36.0 | 16
5 | 11.2 | 56.0 | 25
6 | 13.6 | 81.6 | 36
7 | 16.0 | 112.0 | 49
----+------+-------+-----.
28 | 61.8 | 314.8 | 140 | ∑
7 * 314.8 - 28 * 61.8 473.2
m = ─────────────────────── = ─────── = 2.414
7 * 140 - 28 * 28 196
61.8 - 2,414 * 28
b = ─────────────────── = - 0.827
7
y₃ ≈ 2.414 * 3 + ( - 0.827 ) = 6.415
}
Extrapolation:
• we have a partial, 2D function
• we wish to estimate values somewhere outsite the bounds of the lowest and
the highest x-es we have
Root_estimation:
Fixed_point_iteration:
• we iterate guesses to get more and more accurate results
— the function must be brought to the following form:
x = g(x)
let x₀ := initial guess
let n := number of iterations
for (i = 0; i < n; i++):
xᵢ₊₁ := solve(xᵢ = g())
Newton_Raphson_method:
• we are searching for an x value to feed into f(x) where it equals our
desired value {0}
• we bruteforce search for 2 output values which hug our desired value,
then start iterating until we find out desired value or an acceptable
approximation
xᵢ₊₁ = xᵢ - ( f(xᵢ) / f'(xᵢ) )
Secant_method:
• requires 2 values to start with
• used instead of the Newton method when the derivative is really ugly
xᵢ₊₁ = xᵢ - ( f(xᵢ) / ( (f(xᵢ) - f(xᵢ-1) ) / ( xᵢ - xᵢ-1) )