Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Apuntes

cs 6.042

Kumar Shubham Computer Science Inglés 4 páginas

Contenido del apunte (4)

Página 1

Página 2

Lecture 10 :

Hamiltonian path :

path where every node is visited only once.

Tournament Graph:

an edge from one node to other basically mean that a given vertex has beaten other vertex

THM : every tournament graph actually contain a hamiltonian path.

Proof : Induction on the no of nodes in the graph

removing a node in tournament graph still keep it as tournament graph.

consider smallest i such that V beats Vi

since its smallest other has beaten V so V will be between Vi-1 and Vi

Página 3

Lecture 11 :

Relations, partial orders, and scheduling

Relations :

A relation from set A to set B is a subset R of A X B

ex : for a set A : no of student and set B(classes )

then R (a,b) is the relation of student taking which subject

aRb is denoted by a~Rb

SET A together with R forms a directed graph.

edges : it is joining those nodes which satisfies given relation

vertex : it is the set of all the valid point in given set.

Properties of Relation :

Reflexive : if x is related to itself for all x in set A

Symmetric : if xRY => yRx for all x and y

anti Symmetric : if xRy and yRx => x=y

transitive : if xRy and yRz => xRz

Equivalence relations:

if a relation is Reflexive + symmetric + transitive

ex : equality (=),

equivalence classes : [x] is all the set of x which satisfy a given relation

Partition of A : It is a collection of all disjoint , non empty set whose union is A.

equivalence class form the partition of equivalence relation

Partial ordering

if a relation has Reflexive + anti symmetric and transitive -- (WEAK) PARTIAL ORDERING

Hasse diagram : A Poset based directed graph where we remove reflexive(self loop) and all the edges which are implied by trasitivity

POSET : a graph representation of partial ordering

A Poset has no directed cycle apart from self loop.

A POSET without self loop is a DAG

Total order : Aa partial order where all the element are comparable.

Topological sort :

it is a total order of a poset with new relation M such that Poset relation is a subset of M.

THM : every finite Poset has a topological sort

Página 4

Lecture 12:

N year M dollar annuity : paying M dollar at start of each year for N year

1 dollar currently with P% rate will be (1+p) in a year

(1+p)^2 in two year

(q+p)^3 in three year

and so on.

similarly 1 dollar in one year = 1/(1+P) now

1 dollar in 2 year = 1/(1+p)^2 now

and so on

if |x| <1 then summation of [ 1/x^n ] to infinity is 1/(1-x)

Perturbation method of calculation.

S = x + 2x^2 + 3x^3 + 4x^4 .....nx^n

x*S = x^2 + 2x^3 + 3x^4 ..... .... n*x^n+1

subtract

S(1-x) = x +x^2 +x^3 + x^4 .....x^n+1

Información

Descripción
Computer Science Apunte sobre cs 6.042, creado por Kumar Shubham el 26/09/2019.
Creado por
Kumar Shubham · sep 2019
Actualizado
29 sep 2019
Visitas
11
Valoración

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?