Algebraic Stucture :Lagrange’s theorem

Posted on May 31, 2013 by brigitafebrianti

Statement Verbal statement In a finite group, the order of any subgroup divides the order of the group. In fact, the ratio of the orders is the index of the subgroup, which is the same as the number of left … Continue reading →

Introduction of Sets Theory

Posted on February 19, 2013 by brigitafebrianti

Definition

A set is a collection of individual elements in the domain . The universal set contains every element in . The null set contains no element.

•	If is a set in the domain , must be a subset of the universal set , denoted as .
•	If consists of some but not all elements, is then called a proper subset of , denoted as .

Unions, Intersections, Complements

The definition of union (“or“), intersection (“and“), and complement (“not“) can be illustrated by Venn Diagrams as follows:

Suppose that $A$ and $B$ are two sets in the same domain whose universal set is .

•

The union of $A$ and $B$ consists of all elements which belong to either $A$ or $B$ , denoted by

•

The intersection of $A$ and $B$ consists of only elements which belong to both $A$ and $B$ , denoted by

•

The complement of $A$ consists of elements which do not belong to $A$ , denoted by

Important Properties

Distributive Laws

De Morgan’s Laws

PDE (Partial Differential Equation)

Posted on February 19, 2013 by brigitafebrianti

Characteristics of first-order partial differential equation

For a first-order PDE (partial differential equations), the method of characteristics discovers curves (called characteristic curves or just characteristics) along which the PDE becomes an ordinary differential equation (ODE). Once the ODE is found, it can be solved along the characteristic curves and transformed into a solution for the original PDE.

For the sake of motivation, we confine our attention to the case of a function of two independent variables x and y for the moment. Consider a quasilinear PDE of the form

$a(x,y,z) \frac{\partial z}{\partial x}+b(x,y,z) \frac{\partial z}{\partial y}=c(x,y,z).$

(1)

Suppose that a solution z is known, and consider the surface graph z = z(x,y) in R³. A normal vector to this surface is given by

$\left(\frac{\partial z}{\partial x}(x,y),\frac{\partial z}{\partial y}(x,y),-1\right).\,$

As a result,^[1] equation (1) is equivalent to the geometrical statement that the vector field

$(a(x,y,z),b(x,y,z),c(x,y,z))\,$

is tangent to the surface z = z(x,y) at every point. In other words, the graph of the solution must be a union of integral curves of this vector field. These integral curves are called the characteristic curves of the original partial differential equation.

The equations of the characteristic curve may be expressed invariantly by the Lagrange-Charpit equations^[2]

$\frac{dx}{a(x,y,z)} = \frac{dy}{b(x,y,z)} = \frac{dz}{c(x,y,z)},$

or, if a particular parametrization t of the curves is fixed, then these equations may be written as a system of ordinary differential equations for x(t), y(t), z(t):

$\begin{array}{rcl} \frac{dx}{dt}&=&a(x,y,z)\\ \frac{dy}{dt}&=&b(x,y,z)\\ \frac{dz}{dt}&=&c(x,y,z). \end{array}$

These are the characteristic equations for the original system.

Linear and quasilinear cases

Consider now a PDE of the form

$\sum_{i=1}^n a_i(x_1,\dots,x_n,u) \frac{\partial u}{\partial x_i}=c(x_1,\dots,x_n,u).$

For this PDE to be linear, the coefficients a_i may be functions of the spatial variables only, and independent of u. For it to be quasilinear, a_i may also depend on the value of the function, but not on any derivatives. The distinction between these two cases is inessential for the discussion here.

For a linear or quasilinear PDE, the characteristic curves are given parametrically by

$(x_1,\dots,x_n,u) = (x_1(s),\dots,x_n(s),u(s))$

such that the following system of ODEs is satisfied

$\frac{dx_i}{ds} = a_i(x_1,\dots,x_n,u)$

(2)

$\frac{du}{ds} = c(x_1,\dots,x_n,u).$

(3)

Equations (2) and (3) give the characteristics of the PDE.

Fully nonlinear case

Consider the partial differential equation

$F(x_1,\dots,x_n,u,p_1,\dots,p_n)=0$

(4)

where the variables p_i are shorthand for the partial derivatives

$p_i = \frac{\partial u}{\partial x_i}.$

Let (x_i(s),u(s),p_i(s)) be a curve in R²ⁿ⁺¹. Suppose that u is any solution, and that

$u(s) = u(x_1(s),\dots,x_n(s)).$

Along a solution, differentiating (4) with respect to s gives

$\sum(F_{x_i} + F_u p_i)\dot{x}_i + \sum F_{p_i}\dot{p}_i = 0$

$\dot{u} - \sum p_i \dot{x}_i = 0$

$\sum (\dot{x}_i dp_i - \dot{p}_i dx_i)= 0.$

(The second equation follows from applying the chain rule to a solution u, and the third follows by taking an exterior derivative of the relation du-Σp_idx_i=0.) Manipulating these equations gives

$\dot{x}_i=\lambda F_{p_i},\quad\dot{p}_i=-\lambda(F_{x_i}+F_up_i),\quad \dot{u}=\lambda\sum p_iF_{p_i}$

where λ is a constant. Writing these equations more symmetrically, one obtains the Lagrange-Charpit equations for the characteristic

$\frac{\dot{x}_i}{F_{p_i}}=-\frac{\dot{p}_i}{F_{x_i}+F_up_i}=\frac{\dot{u}}{\sum p_iF_{p_i}}.$

Geometrically, the method of characteristics in the fully nonlinear case can be interpreted as requiring that the Monge cone of the differential equation should everywhere be tangent to the graph of the solution.

Example

As an example, consider the advection equation (this example assumes familiarity with PDE notation, and solutions to basic ODEs).

$a \frac{\partial u}{\partial x} + \frac{\partial u}{\partial t} = 0\,$

where $a\,$ is constant and $u\,$ is a function of $x\,$ and $t\,$ . We want to transform this linear first-order PDE into an ODE along the appropriate curve; i.e. something of the form

$\frac{d}{ds}u(x(s), t(s)) = F(u, x(s), t(s))$ ,

where $(x(s),t(s))\,$ is a characteristic line. First, we find

$\frac{d}{ds}u(x(s), t(s)) = \frac{\partial u}{\partial x} \frac{dx}{ds} + \frac{\partial u}{\partial t} \frac{dt}{ds}$

by the chain rule. Now, if we set $\frac{dx}{ds} = a$ and $\frac{dt}{ds} = 1$ we get

$a \frac{\partial u}{\partial x} + \frac{\partial u}{\partial t} \,$

which is the left hand side of the PDE we started with. Thus

$\frac{d}{ds}u = a \frac{\partial u}{\partial x} + \frac{\partial u}{\partial t} = 0.$

So, along the characteristic line $(x(s), t(s))\,$ , the original PDE becomes the ODE $u_s = F(u, x(s), t(s)) = 0\,$ . That is to say that along the characteristics, the solution is constant. Thus, $u(x_s, t_s) = u(x_0, 0)\,$ where $(x_s, t_s)\,$ and $(x_0, 0)\,$ lie on the same characteristic. So to determine the general solution, it is enough to find the characteristics by solving the characteristic system of ODEs:

$\frac{dt}{ds} = 1$ , letting $t(0)=0\,$ we know $t=s\,$ ,
$\frac{dx}{ds} = a$ , letting $x(0)=x_0\,$ we know $x=as+x_0=at+x_0\,$ ,
$\frac{du}{ds} = 0$ , letting $u(0)=f(x_0)\,$ we know $u(x(t), t)=f(x_0)=f(x-at)\,$ .

In this case, the characteristic lines are straight lines with slope $a\,$ , and the value of $u\,$ remains constant along any characteristic line.

Discrete Math Is Important ?

Posted on February 16, 2013 by brigitafebrianti

Why Discrete Math Is Important by David Patrick

Most middle and high school math curricula follow a well-defined path:

Pre-algebra → Algebra 1 → Geometry → Algebra 2 → Trig / Precalculus → Calculus

Other middle and high schools prefer an “integrated” curriculum, wherein elements of algebra, geometry, and trigonometry are mixed together over a 3-year or 4-year sequence. However, both of these approaches generally lack a great deal of emphasis on discrete math: topics such as combinatorics, probability, number theory, set theory, logic, algorithms, and graph theory. Because discrete math does not figure prominently in most states’ middle or high school “high-stakes” progress exams, and because it also does not figure prominently on college-admissions exams such as the SAT, it is often overlooked.

However, discrete math has become increasingly important in recent years, for a number of reasons:

Discrete math is essential to college-level mathematics and beyond.

Discrete math—together with calculus and abstract algebra—is one of the core components of mathematics at the undergraduate level. Students who learn a significant quantity of discrete math before entering college will be at a significant advantage when taking undergraduate-level math courses.

Discrete math is the mathematics of computing.

The mathematics of modern computer science is built almost entirely on discrete math, in particular combinatorics and graph theory. This means that in order to learn the fundamental algorithms used by computer programmers, students will need a solid background in these subjects. Indeed, at most universities, a undergraduate-level course in discrete mathematics is a required part of pursuing a computer science degree.

Discrete math is very much “real world” mathematics.

Many students’ complaints about traditional high school math—algebra, geometry, trigonometry, and the like—is “What is this good for?” The somewhat abstract nature of these subjects often turn off students. By contrast, discrete math, in particular counting and probability, allows students—even at the middle school level—to very quickly explore non-trivial “real world” problems that are challenging and interesting.

Discrete math shows up on most middle and high school math contests.

Prominent math competitions such as MATHCOUNTS (at the middle school level) and the American Mathematics Competitions (at the high school level) feature discrete math questions as a significant portion of their contests. On harder high school contests, such as the AIME, the quantity of discrete math is even larger. Students that do not have a discrete math background will be at a significant disadvantage in these contests. In fact, one prominent MATHCOUNTS coach tells us that he spends nearly 50% of his preparation time with his students covering counting and probability topics, because of their importance in MATHCOUNTS contests.

Discrete math teaches mathematical reasoning and proof techniques.

Algebra is often taught as a series of formulas and algorithms for students to memorize (for example, the quadratic formula, solving systems of linear equations by substitution, etc.), and geometry is often taught as a series of “definition-theorem-proof” exercises that are often done by rote (for example, the infamous “two-column proof”). While undoubtedly the subject matter being taught is important, the material (as least at the introductory level) does not lend itself to a great deal of creative mathematical thinking. By contrast, with discrete mathematics, students will be thinking flexibly and creatively right out of the box. There are relatively few formulas to memorize; rather, there are a number of fundamental concepts to be mastered and applied in many different ways.

Discrete math is fun.

Many students, especially bright and motivated students, find algebra, geometry, and even calculus dull and uninspiring. Rarely is this the case with most discrete math topics. When we ask students what the favorite topic is, most respond either “combinatorics” or “number theory.” (When we ask them what their least favorite topic is, the overwhelming response is “geometry.”) Simply put, most students find discrete math more fun than algebra or geometry.

We strongly recommend that, before students proceed beyond geometry, they invest some time learning elementary discrete math, in particular counting & probability and number theory. Students can start studying discrete math—for example, our books Introduction to Counting & Probability and Introduction to Number Theory—with very little algebra background.

Matematika Diskrit (Pengenalan)

Posted on February 11, 2013 by brigitafebrianti

Matematika diskrit adalah cabang matematika yang mempelajari objek diskrit. Kata diskrit disini diartikan sebagai objek yang berhingga yang berlainan.

Komputer digital bekerja secara diskrit begitu pula informasi yang disimpan dan dimanipulasi oleh komputerpun adalah dalam bentuk diskrit. Matematika diskrit merupakan ilmu dasar yang penting dalam pendidikan informatika atau ilmu komputer.

Matematika diskrit memberikan landasan matematis untuk mata kuliah lain dibidang teknik informatika, misalnya: algoritma, struktur data, basis data, jaringan komputer, keamanan komputer, sistem operasi, teknik kompilasi, dsb.

Matematika diskrit bertujuan untuk memberikan dasar-dasar dan konsep-konsep matematika yang mendukung sistem dijital dan komputer.

Pada Mata Kuliah Matematika Diskrit ini terdiri atas beberapa Pokok Bahasan Antara lain:

POKOK BAHASAN 1 : Pendahuluan matematika diskrit

POKOK BAHASAN 2 : Teori Himpunan dan Logika

POKOK BAHASAN 3 : Relasi dan Fungsi

POKOK BAHASAN 4 : Algoritma

POKOK BAHASAN 5 : Matriks (Matrix) dan Komputasi

POKOK BAHASAN 6 : Induksi Matematika

POKOK BAHASAN 7 : Barisan dan Deretan

POKOK BAHASAN 8 : Penalaran Matematika

POKOK BAHASAN 9 : Pencacahan (Counting)

POKOK BAHASAN 10: Teori Peluang Diskrit

POKOK BAHASAN 11: Graf

POKOK BAHASAN 12: Diagram Pohon (Tree)

POKOK BAHASAN 13: Teori Bahasa Formal & Otomata

Discrete Mathematics

Posted on February 11, 2013 by brigitafebrianti

What Is Discrete Mathematics?

Discrete Mathematics is a rapidly growing and increasingly used area of mathematics, with many practical and relevant applications.

Because it is grounded in real-world problems, discrete mathematics lends itself easily to implementing the recommendations fo the National Council of Teachers of Mathematics (NCTM) standards. (The recently published Standards and Principles for School Mathematics notes that “As an active branch of contemporary mathematics that is widely used in business and industry, discrete mathematics should be an integral part of the school mathematics curriculum.”)
Because many discrete math problems are simply stated and have few mathematical prerequisites, they can be introduced at all grade levels, even with children who are not yet fluent readers.

Discrete mathematics will make math concepts come alive for your students. It’s an excellent tool for improving reasoning and problem-solving skills, and is appropriate for students at all levels and of all abilities. Teachers have found that discrete mathematics offers a way of motivating unmotivated students while challenging talented students at the same time.

Because many discrete math problems are simply stated and have few mathematical prerequisites, they can be easily be introduced at the middle school grade level.

EXAMPLE: Linear Programming

Minimize C = 3x + 2y on the given feasible set.

Students spent a lot of time graphing lines without seeing how it can be useful. Linear programming is a powerful tool for finding the optimal value of a linear function on some feasible set. The feasible set is created by solving a system of linear inequalities. Solutions can be found graphically so even students who have not studied systems of equations can solve these problems.

EXAMPLE: Systematic Listing & Counting

There are 45 creatures here. How many of them are fish?

Systematic listing and counting are crucial analytical skills which play a fundamantal role in many areas of mathematics, in particular probability. There are many nuances of counting which are often missed in elementary courses. One of our goals is to shed light on this topic by exploring many examples and employing a variety of learning styles.

EXAMPLE: How Many Possibilities?

Combinations and permutations can range from simple to highly complex problems, and the concepts used are relevant to everyday life. Problems and solution methods can range so much that these mathematical ideas can be used with students from elementary school to high school.

Even young students with limited reading skills can solve problems with combinations of small numbers of items. For example, given that a classmate has two shirts and three pairs of pants, students can determine that there are six possible outfits. They can reason about this problem and even draw out the different options.

For older students, more advanced solution strategies can allow them to handle more complex problems, such as the following:

I have a 6-CD player in my car and I own 100 CD’s. How many different ways can I load 6 CD’s into my player?

1st Slot	2nd Slot	3rd Slot	4th Slot	5th Slot	6th Slot

EXAMPLE: Which pizza place is closest?

Voronoi diagrams allow students and teachers to explore a technique that is used in a variety of applications, while at the same time employing critical thinking skills and geometric concepts.

These types of diagrams allow you to map out the areas in a given space that are closest to one specified point or another. For example, if there are 17 ice cream shops of equal quality in your town, a Voronoi diagram can show you which one is the closest for each region of town. This example is shown in the picture below.

This technique is used in biology, chemistry, geology, forestry, and more, as well as in resource planning and placement. This last topic is easily familiar to students as it can include determining placement for a new cell phone tower. or a new pizza place!

These diagrams are constructed using perpendicular bisectors, but students can approach these either strictly through geometric constructions, or through a more algebraic approach for more advanced students.

You are lucky enough to live in a town with 17 ice cream shops, each as good as the next. On the town map below, the ice cream shops are marked with letters. For each numbered point, which ice cream shop or shops should you frequent?