Sets, Multisets and Partial Orders

Set :- An unordered collection of different, well defined objects.
Multiset :- An unordered collection of well defined objects.

That is a Set is a Multiset with distinct objects only.

Touple :- A permutation of well defined objects.

Equivalence Class :- Its a set S, with respect to a relation '~', such that
& ∀ x,y,z ∈ S:-

1. Reflexive : x ~ x
2. Symmetric :x ~ y ⇒ y ~ x
3. Transitive : x ~ y and y ~ z ⇒ x ~ z

Partial Order :- Its a set S, with respect to a relation '≥', such that 
& ∀ x,y,z ∈ S:-

1. Reflexive : x ≥ x
2. Anti-symmetric :x ≥ y and y ≥ x ⇒ y = x
3. Transitive : x ≥ y and y ≥ z ⇒ x ≥ z

These above concepts are  very important.

Graphs and Hypergraphs

Graph :- A graph G is an 2-tuple (V,E) of a set of vertices V and a set of edges E, where {x,y} ∈ E  ⇒ x,y ∈ V.

Directed Graph :- A directed graph D is an 2-tuple (V,E) of a set of vertices V and a set of edges E, where (x,y) ∈ E  ⇒ x,y ∈ V.

Each of above, can be further classified into, labeled and unlabeled classes.
 

Labeled simple Graph of 6 vertices and 7 edges

An un-labeled Directed Graph

Graphs, can further be classified as edge or vertex or both weighted graphs. So, weighted graphs is represented by G(V,E,w(V),w(E)), where w resembles weight. 

Computer Representation of Graph :-
w(V) is an array of numbers w₀,w₁,...,w_n-1. 
w(E) is an 2-D array of numbers, called Adjacency Matrix A = ( w_(x,y) ) where w_(x,y) is the weight of edge (x,y) ∈ E. If edge is not present then w_(x,y) = 0.

We can also, represent w(E) by an Adjacency List, where we have an array A, One element of A is another array A(x), which contains, ordered pair (w_(x,y), y) sorted with respect to y.



This representation ease the search of edge as well as reduce the storage space in the sparse graph. 

Note, that Adjacency List search time is O(log(n)), space complexity O(|V| + |E|). In Adjacency Matrix search time is O(1) but space complexity is O(|V|²).

Adjacency List Representation of directed and undirected graphs

Again Hypergraph is a graph in which each edge is a k-tuple or set of k vertices, where k ≤ |V|. 

Uniform random number generation in Computer

Let's, have a generator, Ui(R_max+1), to generate uniform random integer r ∈ [0...R_max].
We can construct Ui(N) in following way,

Ui(N) =

1. Range = R_max - ( R_max )mod N
2. do
1. r = U(R_max+1);
3. while( r  ≥  Range );
4. Return(r);

Similarly, we can further construct a real random number generator Ur(N), which generates random real r ∈ [0,1]. using  Ui(N).

Ur(N) = (N-1)/Ui(N);

Ber(p) = ( Ur(N) ≤ p ) + (Ur(N) > p) ;
Binomial(n,p) =

1. y = 0
2. for(i = 0; i < n; i = i + 1)
1. y = y + Ber(p)
3. Return y 

Fermat's Last Theorem

Pierre de Fermat in 1637, had made a conjecture that there is no integer a,b,c,n if n > 2 s.t aⁿ + bⁿ = cⁿ
become true.

This was open problem to prove through centuries. At last  Andrew Wiles had proved it in 1995. 
For n = 2 we have infinite many such tuple. But for n = 3 no such tuple exist.

Euler's totient function

Its a very nice function on Natural numbers. A totient function on natural number n represented by φ(n) is defined as -
                  For prime p : -
                                 


Clearly φ(n) = # of mutual primes w.r.t n in the range of [ 1 ... n ].

Notation :- Z_n = [ 0 ... (n - 1) ]

Property : - 1. ∀ m,n ∈ Z ( Set of Natural Numbers ) s.t. gcd(m,n) = 1,
                             φ(m.n) = φ(m).φ(n)
                   2. ∀ m,n ∈ Z, φ(m.n) = φ(m).φ(n). gcd(m,n)/φ(gcd(m,n)) 
                   3.       
                   
                  4. For mutually prime a,n
                  5. 
                  6.  For ∀ a,n ∈ Z  and n > 1, 

If we inscribe  Möbius function and then some beautiful identity could be found.

For more see http://en.wikipedia.org/wiki/Euler's_totient_function

Language

In Automata-theory -

Alphabet :- Finite set of symbols.

String :- Sequence of symbols.

Language :- Set of strings.

Operations on Strings :- 
1. (+) - union

2. (.) - concatenation  

3. (*) - Kleene star 

Ex :-  A = "aa" B = "bb" 
1. A + B = {"aa","bb"} 
2. A.B = "aabb"

3. A^* = ε ∪A∪A²…

Notice that A^* the set of all finite strings over A.

Finite permutation of strings and above mentioned operations creates Regular Expression.

Regular Language :- 

Def 1 :- If -
             i. ∃ λ : Σ →  M is a  monoid homomorphism where M is a finite monoid.
             ii. S ⊆ M
then { ω∈ Σ^* | λ(ω) ∈ S} is regular.

Def 2 :- 
Let, L ⊆ Σ^*and there is an equivalence relation ~ s.t uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular ↔  Number of equivalence classes of ~ is finite.

A language L on alphabet Σ is Regular ↔ It is equivalent to a Regular Grammar
↔ It will have an Equivalent DFA ↔ It will have an Equivalent NFA.

Finite Automaton

We already described FA in the previous pages. There are 2 kinds of Finite Automaton, 1. DFA 2.NFA. Here introduced the concept of non-determinism and determinism.

Deterministic FA :- This is a FSM with a input string and a set of Accepting states (F). Formally a 5-tuple (Q,Σ,δ,q₀,F) represents the Structure. Here machine read the symbol , progress head one step right and take a deterministic jump [ A jump where from a current state one can go to a single next state ] from current state to new state with respect to the read symbol.

Non-Deterministic FA :- This is a non-deterministic FSM [ Normally FSM are deterministic but we can also make it non-deterministic by allowing multiple possible next state from current state w.r.t single read symbol . Control would choose totally  randomly  one of the next state from those possible next states, as it could only be in only one state at a time ].

Practically then for each symbol and each current state there will be multiple possible next state and so in a obvious consequence there could be multiple path of control flow and we don't know which path the control will go. But now we can say that the NFA will accept some string if ∃ at least one path ending in a accepting state.

So, formally NFA will also be a 5-tuple same as DFA, only difference is δ: Q × Σ  → 2^Q


With δ we sometime want to see the transition function for a string and we call it δ^'.
It is designed as -
1. ∀ (s,a) ∈ ( ( Σ^*- ε ), Σ ) → δ^'(s.a)  = δ^'(s).δ(a)
2. δ^'(ε) = φ