https://www.udacity.com/course/viewer#!/c-cs215/l-48369875
LESSON 2
Утверждение 1. Если существует предел lim x→x0 (f(x)/g(x)) = A , A != ∞ , то f(x) = O(g(x)) , x → x0 .
Утверждение 2. Если существует lim x→x0 (f(x)/g(x)) = 0 , то f(x) = o (g(x)), x → x0 .
Утверждение 3. Если существует lim x→x0 (f(x)/g(x)) = 1 , то f(x) ∼ g(x), x → x0 .
e^x − 1 ∼ x ,
ln(1 + x) ∼ x ,
(1 + x)^a − 1 ∼ a · x , a ∈ R ,
sin x ∼ x ,
1 − cos x ∼ x^2 / 2,
tg x ∼ x ,
arcsin x ∼ x ,
arctg x ∼ x .
Пусть функция f = f(x) определена на некотором множестве D. Пусть x0 – предельная точка этого множества, причем функция f(x) не обращается в нуль в
некоторой окрестности этой точки (за исключением, быть может, самой точки x0). Тогда при x → x0 имеют место следующие утверждения:
1) o(f) + o(f) = o(f) ;
2) O(f) + O(f) = O(f) ;
3) O(f) + o(f) = O(f) ;
4) o(o(f)) = o(f) ;
5) O(O(f)) = O(f) ;
6) O(o(f)) = o(f) ;
7) o(O(f)) = o(f).
Пусть на некотором множестве D , для которого x0 – предельная точка, определена бесконечно малая функция α = α(x) : α(x) → 0 при x → x0 , причем функция α(x) не обращается в нуль в некоторой окрестности этой точки (за исключением, быть может, самой точки x0). Пусть m , n ∈ N . Тогда справедливы следующие утверждения:
1) o(α^n) = o(α^m), m ≤ n ;
2) O(α^n) = O(α^m), m ≤ n ;
3) o(α^m) + o(α^n) = o(α^m), m ≤ n ;
4) O(α^m) + O(α^n) = O(α^n), m ≤ n ;
5) o(α^m) · o(α^n) = o(α^(m+n)) ;
6) O(α^m) · O(α^n) = O(α^(m+n)) ;
7) (o(α))^n = o(α^n) ;
8) (O(α))^n = O(α^n) ;
9) α · o(α^n) = o(α^(n+1));
10) α · O(α^n) = O(α^(n+1)) ;
11) o(α^n)/α = o(α^(n−1)), n > 1 ;
12) O(α^n)/α = O(α^(n−1)), n > 1 .
Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.
Big O notation is also used in many other fields to provide similar estimates.
Θ(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Θ (g(n)) means it is within a constant multiple of g(n). The equation is read, "f of n is theta g of n".
Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k. The values of c1, c2, and k must be fixed for the function f and must not depend on n.
The adjacency matrix of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row i and column j when vertices i and j are adjacent, and a zero otherwise.
In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).
An undirected graph is a graph in which edges have no orientation. The edge (x, y) is identical to the edge (y, x), i.e., they are not ordered pairs, but sets {x, y} (or 2-multisets) of vertices. The maximum number of edges in an undirected graph without a loop is n(n − 1)/2.
A weighted graph is a graph in which a number (the weight) is assigned to each edge.
A regular graph is a graph in which each vertex has the same number of neighbours, i.e., every vertex has the same degree. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.
- circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2
- a cage is a regular graph with the smallest possible order for its girth
- a planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect
- a tree is a connected graph with no cycles
- a forest is a graph with no cycles, i.e. the disjoint union of one or more trees
- a hypercube graph is a graph formed from the vertices and edges of a geometric hypercube
- a star is a tree with one internal vertex; equivalently, it is a complete bipartite graph K1,n for some n ≥ 2; the special case of a star with three leaves is called a claw
# How many edges in a complete graph on n nodes?
#
def clique(n):
# Return the number of edges
# Try to use a mathematical formula...
return n*(n-1)/2
print clique(10)
PROBLEM SET 2
#1
# Write a program that returns the number of edges
# in a star network that has `n` nodes
#
def star_network(n):
# return number of edges
return n-1
#7
# Generate a combination lock graph given a list of nodes
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def create_combo_lock(nodes):
G = {}
make_link(G, nodes[0], nodes[1])
for i in range(len(nodes)-2):
make_link(G, nodes[i+1], nodes[i+2])
make_link(G, nodes[0], nodes[i+2])
# your code here
return G
##############
# Code for testing
#
def is_chain(graph, nodes):
# find the first node with degree one
start = (n for n, e in graph.iteritems()
if len(e) == 1).next()
count = 1
# keep track of what we've seen to make
# sure there are no cycles
seen = set([start])
# follow the edges
prev = None
current = start
while True:
nexts = graph[current].keys()
# get rid of the edge back to prev
nexts = [n for n in nexts if not n == prev]
if len(nexts) > 1:
# bad. too many edges to be a chain
return False
elif len(nexts) == 0:
# We're done following the chain
# Did we get enough edges:
return count == len(nodes)
prev = current
current = nexts[0]
if current in seen:
# bad. this isn't a chain
# it has a loop
return False
seen.add(current)
count += 1
def is_combo_lock(graph, nodes):
# first see if we have a star
center = None
degree = None
for node, edges in graph.iteritems():
if len(edges) > degree:
center = node
degree = len(edges)
if not degree == len(nodes) - 1:
return False
# make a graph out of all the edges
# not connected to the center
chain = {}
for node, edges in graph.iteritems():
if node == center:
continue
for e in edges:
if e == center:
continue
make_link(chain, node, e)
return is_chain(chain, [n for n in nodes if n != center])
def test():
for n in [5, 10, 20]:
combo = create_combo_lock(range(n))
if not is_combo_lock(combo, range(n)):
return False
return True
print test()
Last login: Sat Jun 18 09:03:25 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson1_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson2_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson1_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update reflections lesson1"
[master 085d3f4] Update reflections lesson1
1 file changed, 40 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson2_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections lesson2"
[master 1777e02] Add reflections lesson2
1 file changed, 80 insertions(+)
create mode 100644 reflections-cs215/lesson2_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 2 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 4.27 KiB | 0 bytes/s, done.
Total 8 (delta 4), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
37adbd0..1777e02 master -> master
olgabelitskaya (master) version-control $
LESSON 2
Утверждение 1. Если существует предел lim x→x0 (f(x)/g(x)) = A , A != ∞ , то f(x) = O(g(x)) , x → x0 .
Утверждение 2. Если существует lim x→x0 (f(x)/g(x)) = 0 , то f(x) = o (g(x)), x → x0 .
Утверждение 3. Если существует lim x→x0 (f(x)/g(x)) = 1 , то f(x) ∼ g(x), x → x0 .
e^x − 1 ∼ x ,
ln(1 + x) ∼ x ,
(1 + x)^a − 1 ∼ a · x , a ∈ R ,
sin x ∼ x ,
1 − cos x ∼ x^2 / 2,
tg x ∼ x ,
arcsin x ∼ x ,
arctg x ∼ x .
Пусть функция f = f(x) определена на некотором множестве D. Пусть x0 – предельная точка этого множества, причем функция f(x) не обращается в нуль в
некоторой окрестности этой точки (за исключением, быть может, самой точки x0). Тогда при x → x0 имеют место следующие утверждения:
1) o(f) + o(f) = o(f) ;
2) O(f) + O(f) = O(f) ;
3) O(f) + o(f) = O(f) ;
4) o(o(f)) = o(f) ;
5) O(O(f)) = O(f) ;
6) O(o(f)) = o(f) ;
7) o(O(f)) = o(f).
Пусть на некотором множестве D , для которого x0 – предельная точка, определена бесконечно малая функция α = α(x) : α(x) → 0 при x → x0 , причем функция α(x) не обращается в нуль в некоторой окрестности этой точки (за исключением, быть может, самой точки x0). Пусть m , n ∈ N . Тогда справедливы следующие утверждения:
1) o(α^n) = o(α^m), m ≤ n ;
2) O(α^n) = O(α^m), m ≤ n ;
3) o(α^m) + o(α^n) = o(α^m), m ≤ n ;
4) O(α^m) + O(α^n) = O(α^n), m ≤ n ;
5) o(α^m) · o(α^n) = o(α^(m+n)) ;
6) O(α^m) · O(α^n) = O(α^(m+n)) ;
7) (o(α))^n = o(α^n) ;
8) (O(α))^n = O(α^n) ;
9) α · o(α^n) = o(α^(n+1));
10) α · O(α^n) = O(α^(n+1)) ;
11) o(α^n)/α = o(α^(n−1)), n > 1 ;
12) O(α^n)/α = O(α^(n−1)), n > 1 .
Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.
Big O notation is also used in many other fields to provide similar estimates.
Θ(definition)
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Θ (g(n)) means it is within a constant multiple of g(n). The equation is read, "f of n is theta g of n".
Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k. The values of c1, c2, and k must be fixed for the function f and must not depend on n.
The adjacency matrix of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row i and column j when vertices i and j are adjacent, and a zero otherwise.
In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).
An undirected graph is a graph in which edges have no orientation. The edge (x, y) is identical to the edge (y, x), i.e., they are not ordered pairs, but sets {x, y} (or 2-multisets) of vertices. The maximum number of edges in an undirected graph without a loop is n(n − 1)/2.
A weighted graph is a graph in which a number (the weight) is assigned to each edge.
A regular graph is a graph in which each vertex has the same number of neighbours, i.e., every vertex has the same degree. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.
- circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2
- a cage is a regular graph with the smallest possible order for its girth
- a planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect
- a tree is a connected graph with no cycles
- a forest is a graph with no cycles, i.e. the disjoint union of one or more trees
- a hypercube graph is a graph formed from the vertices and edges of a geometric hypercube
- a star is a tree with one internal vertex; equivalently, it is a complete bipartite graph K1,n for some n ≥ 2; the special case of a star with three leaves is called a claw
# How many edges in a complete graph on n nodes?
#
def clique(n):
# Return the number of edges
# Try to use a mathematical formula...
return n*(n-1)/2
print clique(10)
PROBLEM SET 2
#1
# Write a program that returns the number of edges
# in a star network that has `n` nodes
#
def star_network(n):
# return number of edges
return n-1
#7
# Generate a combination lock graph given a list of nodes
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def create_combo_lock(nodes):
G = {}
make_link(G, nodes[0], nodes[1])
for i in range(len(nodes)-2):
make_link(G, nodes[i+1], nodes[i+2])
make_link(G, nodes[0], nodes[i+2])
# your code here
return G
##############
# Code for testing
#
def is_chain(graph, nodes):
# find the first node with degree one
start = (n for n, e in graph.iteritems()
if len(e) == 1).next()
count = 1
# keep track of what we've seen to make
# sure there are no cycles
seen = set([start])
# follow the edges
prev = None
current = start
while True:
nexts = graph[current].keys()
# get rid of the edge back to prev
nexts = [n for n in nexts if not n == prev]
if len(nexts) > 1:
# bad. too many edges to be a chain
return False
elif len(nexts) == 0:
# We're done following the chain
# Did we get enough edges:
return count == len(nodes)
prev = current
current = nexts[0]
if current in seen:
# bad. this isn't a chain
# it has a loop
return False
seen.add(current)
count += 1
def is_combo_lock(graph, nodes):
# first see if we have a star
center = None
degree = None
for node, edges in graph.iteritems():
if len(edges) > degree:
center = node
degree = len(edges)
if not degree == len(nodes) - 1:
return False
# make a graph out of all the edges
# not connected to the center
chain = {}
for node, edges in graph.iteritems():
if node == center:
continue
for e in edges:
if e == center:
continue
make_link(chain, node, e)
return is_chain(chain, [n for n in nodes if n != center])
def test():
for n in [5, 10, 20]:
combo = create_combo_lock(range(n))
if not is_combo_lock(combo, range(n)):
return False
return True
print test()
Last login: Sat Jun 18 09:03:25 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson1_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson2_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson1_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update reflections lesson1"
[master 085d3f4] Update reflections lesson1
1 file changed, 40 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson2_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections lesson2"
[master 1777e02] Add reflections lesson2
1 file changed, 80 insertions(+)
create mode 100644 reflections-cs215/lesson2_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 2 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 4.27 KiB | 0 bytes/s, done.
Total 8 (delta 4), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
37adbd0..1777e02 master -> master
olgabelitskaya (master) version-control $
Комментариев нет:
Отправить комментарий