Pokročilá odborná angličtina - zkouška
COURSE MATERIALS WEEK X.
Lecture 16 Greedy algorithms
Decide whether the statements are true or false.
- Greedy algorithms are one distinct kind of algorithms.
- Digraph is an abbreviation for directed graph.
- The plural form of vertice is vertices.
- The word vertices comes from old English.
- It appeared in the 15th century.
- Directed graph contains unordered pairs.
- In asymptotic notation, we leave out vertical bars.
- In connected graph, the number of edges is bigger than the number of vertices.
9. In connected graph, you can connect all vertices in the graph.
Listen again and try to find words which are wrong
Transcript - Lecture 16
A)-- valuable experience. OK, today we're going to start talking about a particular class of algorithms called greedy algorithms. But we're going to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in enclosure B. And so, if you haven't reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our get -home quiz. So, just reminder, a digraph, what's a digraph? What's that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices.
B)And, I always get people telling me that I have one vertice. The singular is not vertice; it is vertex, OK? The plural is vertices. The singular is vertex. It's one of those strange English words. It's probably originally like French or something, right? I don't know. OK, anyway, and we have a set, E, which is a subset of V cross V of edges. So that's a digraph. And undirected graph, E contains unordered pairs.
C)OK, and, sorry? It's Latin, OK, so it's probably very old, then, in English. I guess the vertex would be a little bit of a giveaway that maybe it wasn't French. It started to be used in 1570, OK. OK, good, OK, so the number of edges is, whether it's directed or undirected, is O of what? V^2, good. OK, and one of the conventions that will have when we're dealing, once we get into graphs, we deal a lot with sets. We generally drop the vertical bar notation within O's just because it's applied. It just makes it nicer. So, once again, another abuse of notation. It really should be order the size of V^2, but it just messes up, I mean, it's just more stuff to write down. And, you're multiplying these things, and all those vertical pubs.
D)Since they don't even have a sense to the vertical bar, it gets messy. So, we just drop the vertical bars there when it's in asymptotic notation. So, E is order V^2 when it's a set of pairs, because if it's a set of pairs, it's at most n choose two, which is where it's at most n^2 over 2, here it could be, at most, sorry, V^2 over 2, here it's at most V^2. And then, another property that sometimes comes up is if the G is connected, we have another limit, implies that the size of E is at least the size of V minus one. OK, so if it's connected, meaning, what does it mean to have a graph that's connected?
E)Yeah, there's a path from any vertex to any other vertex in the graph. That's what it means to be connected. So if that's the case, that a number of edges is at least the number of vertices plus one, OK? And so, what that says, so one of the things we'll get into, a fact that I just wanted to tell you, is that in that case, if I look at log E, OK, log of the number of edges, that is O of log V.
Transcript - Lecture 16
-- valuable experience. OK, today we're going to start talking about a particular class of algorithms called greedy algorithms. But we're going to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in appendix B. And so, if you haven't reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our take-home quiz. So, just reminder, a digraph, what's a digraph? What's that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices.
And, I always get people telling me that I have one vertice. The singular is not vertice; it is vertex, OK? The plural is vertices. The singular is vertex. It's one of those weird English words. It's probably originally like French or something, right? I don't know. OK, anyway, and we have a set, E, which is a subset of V cross V of edges. So that's a digraph. And undirected graph, E contains unordered pairs.
OK, and, sorry? It's Latin, OK, so it's probably pretty old, then, in English. I guess the vertex would be a little bit of a giveaway that maybe it wasn't French. It started to be used in 1570, OK. OK, good, OK, so the number of edges is, whether it's directed or undirected, is O of what? V^2, good. OK, and one of the conventions that will have when we're dealing, once we get into graphs, we deal a lot with sets. We generally drop the vertical bar notation within O's just because it's applied. It just makes it messier. So, once again, another abuse of notation. It really should be order the size of V^2, but it just messes up, I mean, it's just more stuff to write down. And, you're multiplying these things, and all those vertical bars.
Since they don't even have a sense to the vertical bar, it gets messy. So, we just drop the vertical bars there when it's in asymptotic notation. So, E is order V^2 when it's a set of pairs, because if it's a set of pairs, it's at most n choose two, which is where it's at most n^2 over 2, here it could be, at most, sorry, V^2 over 2, here it's at most V^2. And then, another property that sometimes comes up is if the G is connected, we have another bound, implies that the size of E is at least the size of V minus one. OK, so if it's connected, meaning, what does it mean to have a graph that's connected?
Yeah, there's a path from any vertex to any other vertex in the graph. That's what it means to be connected. So if that's the case, that a number of edges is at least the number of vertices minus one, OK? And so, what that says, so one of the things we'll get into, a fact that I just wanted to remind you, is that in that case, if I look at log E, OK, log of the number of edges, that is O of log V.
Abstract algebra
From Wikipedia, the free encyclopedia
1. There are many kinds of algebra in the text. Read the text and try to explain the following terms:
a) algebra....................................................................................................
b) elementary algebra...............................................................................
c) abstract algebra....................................................................................
d) representation theory...........................................................................
e) universal algebra..................................................................................
1. There are definition of the terms from the text. Try to match terms and their definitions.
ring, vector space, category, group, field
a) a field is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms
b) vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied ("scaled") by numbers
c) group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element
(usually called addition and multiplication), where each operation combines two elements to form a third element
e) a category is an algebraic structure consisting of a collection of "objects", linked together by a collection of "arrows" that have two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow of each object
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. The phrase abstract algebra was coined at the turn of the 20th century to distinguish this area from what was normally referred to as algebra, the study of the rules for manipulating formulae and algebraic expressions involving unknowns and real or complex numbers, often now called elementary algebra. The distinction is rarely made in more recent writings.
Contemporary mathematics and mathematical physics make intensive use of abstract algebra; for example, theoretical physics draws on Lie algebras. Subject areas such as algebraic number theory, algebraic topology, and algebraic geometry apply algebraic methods to other areas of mathematics. Representation theory, roughly speaking, takes the 'abstract' out of 'abstract algebra', studying the concrete side of a given structure; see model theory.
Two mathematical subject areas that study the properties of algebraic structures viewed as a whole are universal algebra and category theory. Algebraic structures, together with the associated homomorphisms, form categories. Category theory is a powerful formalism for studying and comparing different algebraic structures.
History and examples
3. Study the short paragraph below and choose the correct option.
Many textbooks are false because they state that the axioms more important than study.
Many textbooks are false because they state than axioms arrived before scientific study.
Many textbooks claim untrue facts.
In the course of historical development the axioms came first.
In the course of historical development there were first considerations of individual facts.
The common sets of concepts were considered first, then came the various problems.
The common concepts cane after the consideration of various problems.
The various facts were collected from many fields of maths.
The various facts were collected from many fields of science.
Numerous textbooks in abstract algebra start with axiomatic definitions of various algebraic structures and then proceed to establish their properties, creating a false impression that somehow in algebra axioms had come first and then served as a motivation and as a basis of further study. The true order of historical development was almost exactly the opposite. Most theories that we now recognize as parts of algebra started as collections of disparate facts from various branches of mathematics, acquired a common theme that served as a core around which various results were grouped, and finally became unified on a basis of a common set of concepts.
An example
4. Read the following paragraph and try to explain:
a) monoid........................................................................
b) binary operation........................................................
c) concatenation.............................................................
d) association..................................................................
Abstract algebra facilitates the study of properties and patterns that seemingly disparate mathematical concepts have in common. For example, consider the distinct operations of function composition, f(g(x)), and of matrix multiplication, AB. These two operations have, in fact, the same structure. To see this, think about multiplying two square matrices, AB, by a one column vector, x. This defines a function equivalent to composing Ay with Bx: Ay = A(Bx) = (AB)x. Functions under composition and matrices under multiplication are examples of monoids. A set S and a binary operation over S, denoted by concatenation, form a monoid if the operation associates, (ab)c = a(bc), and if there exists an e∈S, such that ae = ea = a.
Function composition is the application of one function to the results of another. For instance, the functions f: X → Y and g: Y → Z can be composed by computing the output of g when it has an argument of f(x) instead of x. Intuitively, if z is a function g of y and y is a function f of x, then z is a function of x.
Thus one obtains a function g ∘ f: X → Z defined by (g ∘ f)(x) = g(f(x)) for all x in X. The notation g ∘ f is read as "g circle f", or "g composed with f", "g after f", "g following f", or just "g of f".
As an example, suppose that an airplane's elevation at time t is given by the function h(t) and that the oxygen concentration at elevation x is given by the function c(x). Then (c ∘ h)(t) describes the oxygen concentration around the plane at time t
There is another example of the matrix multiplication. Read it again and try to fill in the missing items.
multiply dot product
column last
comma
product
height row
width coordinates
Ordinary matrix product
The ordinary matrix product is the most often used and the most important way to ................ matrices. It is defined between two matrices only if the width of the first matrix equals the .............. of the second matrix. Multiplying an m×n matrix with an n×p matrix results in an m×p matrix. If many matrices are multiplied together, and their dimensions are written in a list in order, e.g. m×n, n×p, p×q, q×r, the size of the result is given by the first and the ............. numbers (m×r), and the values surrounding each ................must match for the result to be defined.
The element x3,4 of the above matrix ................ is computed as follows
The first ................. in matrix notation denotes the .............and the second the column; this order is used both in indexing and in giving the dimensions. The element at the intersection of row i and ................. j of the product matrix is the dot product (inner product) of row i of the first matrix and column j of the second matrix. This explains why the .................. and the height of the matrices being multiplied must match: otherwise the .................. is not defined.
WORD STUDY: There are some terms from the text but some of their letters are missing. Try to supply the missing letters.
-op- - -g- a-g- - r- - c -o-o- - e- -i- - -e-t c- - e- -r- -ul- - p- - e-
There are some more words, but the order of their syllables has been mixed up. Try to sort them out.
rimacest nacoteontican
cunfiton cortev
moromhosimph monulc