Pokročilá odborná angličtina - zkouška
COURSE MATERIALS WEEK IX.
Introduction to Differential Equations www.maths.duke.edu/ode
The spread of a rumor
Suppose two students at your school start a rumor. How could we describe the spread of the rumor throughout the school population? Could we determine a function S such that S(t) approximates the number of people that know the rumor at a time arbitrary time t, where t is measured in, say, hours?
We'll begin by trying to decide what the graph of S might look like. Assume that M is the population of your school and that M is sufficiently large that it makes sense to model discrete numbers of students with a continuous function. Thus, if S(3) = 127.8, we'll predict that the number of students who know the rumor after 3 hours is approximately 128.
- Study the six graphs below. For each graph, decide whether or not it could be the graph of the function S. In each case, give the reasons for your decision.
Possible Graphs of S
- Describe three conditions that dS/dt, the rate of spread of the rumor, should satisfy. Keep in mind that we are describing the rate of change of the number of students who know the rumor. Suppose for example, that you know the number of "rumor-aware" students at two o'clock. What factors might determine the number of rumor-aware students at three o'clock? Consider the nature of the rumor itself, conditions at your school, and at least one condition that changes as the rumor spreads.
..........................................................................................................................
..........................................................................................................................
.......................................................................................................................................
Now consider the following Qs. In case you are not sure, study the following text.
1. What is calculus?
2. What is the difference between real and complex analysis.
3. What is the relation between the Riemann hypothesis and complex analysis?
4. What does it mean when a system is described as „dynamic“?
5. What does the chaos theory study?
6. What does the functional analysis study?
Understanding and describing change is a common theme in the natural sciences, and calculus was developed as a powerful tool to investigate it. Functions arise here, as a central concept describing a changing quantity. The rigorous study of real numbers and real-valued functions is known as real analysis, with complex analysis the equivalent field for the complex numbers. The Riemann hypothesis, one of the most fundamental open questions in mathematics, is drawn from complex analysis. Functional analysis focuses attention on (typically infinite-dimensional) spaces of functions. One of many applications of functional analysis is quantum mechanics. Many problems lead naturally to relationships between a quantity and its rate of change, and these are studied as differential equations. Many phenomena in nature can be described by dynamical systems; chaos theory makes precise the ways in which many of these systems exhibit unpredictable yet still deterministic behavior.
Differential equation
From Wikipedia, the free encyclopedia
7. Have a look at the text and try to fill in the missing words.First, try to guess, than have a look at the list of words.
A differential equation is a mathematical equation for an unknown function of one or several a) …………..that relates the values of the function itself and its derivatives of various orders.
Visualization of airflow into a duct modelled using the Navier-Stokes equations, a set of
partial differential equations.
Differential equations arise in many areas of science and technology: whenever a deterministic relationship involving some continuously varying quantities (b) …… by functions and their rates of change in c)…… and/or time (expressed as derivatives) is known or postulated. This is illustrated in classical mechanics, where the d)……. of a body is described by its position and e)…….. as the time varies. Newton's Laws allow one to relate the position, velocity, f)…….. and various forces acting on the body and state this relation as a differential equation for the unknown position of the body as a function of g)…... In some cases, this differential equation (called an equation of motion) may be h)…….. explicitly.
a) variables derivatives equations
b) described modelled draw
c) time force space
d) state position motion
e) acceleration velocity position
f) velocity acceleration time
g) time space gravity
h) counted solved guessed
8. There are various types of differential equations, have alook at the visualization of airflow into a duct and find out what kind of differential equation this is.
....................................................................................
9. Now read the definitions of the two kinds of defferential equations and fill in the missing information comparing these two types.
a) In PDE the unknown function is a function of multiple independent variable whereas .........................................................................................................................
b) ODE are classified according to the order of the highest derivative .......................................................................................................................................
c) For PDE further classification into elliptic, hyperbolic and parabolic equations is important, while...............................................................................................................
d) Try to think of one more example of difference from the text: ..........................................................................................................................................
Nomenclature
The theory of differential equations is quite developed and the methods used to study them vary significantly with the type of the equation.
- An ordinary differential equation (ODE) is a differential equation in which the unknown function (also known as the dependent variable) is a function of a single independent variable. In the simplest form, the unknown function is a real or complex valued function, but more generally, it may be vector-valued or matrix-valued: this corresponds to considering a system of ordinary differential equations for a single function. Ordinary differential equations are further classified according to the order of the highest derivative with respect to the dependent variable appearing in the equation. The most important cases for applications are first order and second order differential equations. In the classical literature also distinction is made between differential equations explicitly solved with respect to the highest derivative and differential equations in an implicit form.
- A partial differential equation (PDE) is a differential equation in which the unknown function is a function of multiple independent variables and the equation involves its partial derivatives. The order is defined similarly to the case of ordinary differential equations, but further classification into elliptic, hyperbolic, and parabolic equations, especially for second order linear equations, is of utmost importance. Some partial differential equations do not fall into any of these categories over the whole domain of the independent variables and they are said to be of mixed type.
WORD STUDY: Prefixes are important means of creating new words, usually the opposits. There are some words from the text, try to supply prefixes forming new expressions.
dependent .............................. partial .........................................
proportional .......................... significant ..................................
known .................................... real ............................................
natural ................................... continuous ................................
changing ................................ finite ........................................
predictable ........................... mixed .......................................
important ............................. varied .....................................
Listening Divide and Conquer
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed03.htm
Decide whether the statements are true or false.
- The subject of the lesson is master theorem.
- Students should go to recitation on Friday.
- Homework should be submitted on Saturday.
- Monday is a holiday.
- Divide and Conquer is the same as divide and rule.
- The question of family feud will be on the quiz.
- Divide and conquer was practiced by the Americans.
- Cormen, Leiserson, Rivest and Stein are the authors of a book on algorithms.
- There are three steps in divide and conquer.
- The value of N is larger than it was in the original problem.
- Merge algorithm fits into this system.
- When you recursively solve each part of the array, it is divide.
Listen again and fill in the missing words.
Transcript - Lecture 3
Good morning everyone. Today we are going to do some algorithms, ___________ algorithms, and we are going to use a lot of the, well, some of the simpler mathematics that we developed last class like the master theorem for solving ___________. We are going to use this a lot. Because we are going to talk about recursive algorithms today. And so we will find their running time using the master theorem. This is just the same as it was last time, I hope, unless I made a mistake. A couple of reminders. You should all go to recitation on Friday. That is required. If you want to, you can go to homework lab on Sunday. That may be a _____________ for you to actually work on your problem set a few hours early.
Well, actually, it's _______ on Wednesday so you have lots of time. And there is no class on Monday. It is the holiday known as Student Holiday, so don't come. Today we are going to cover something called Divide and Conquer. Also known as divide and rule or divide et impera for those of you who know Latin, which is a ______ and tested way of conquering a land by dividing it into sections of some kind. It could be different political factions, different whatever. And then somehow making them no longer ______ each other. Like starting a family feud is always a good method. You should remember this on your quiz. I'm kidding.
And if you can separate this big power structure into little power structures such that you _________ each little power structure then you can conquer all of them individually, as long as you make sure they don't get back together. That is divide and conquer as practiced, say, by the British. But today we are going to do divide and conquer as practiced in Cormen, Leiserson, Rivest and Stein or every other algorithm textbook. This is a very basic and very powerful algorithm design technique. So, this is our first real algorithm design experience.
We are still sort of mostly in the analysis mode, but we are going to do some _______ design. We're going to cover maybe only three or four major design techniques. This is one of them, so it is really important. And it will lead to all sorts of recurrences, so we will get to use everything from last class and see why it is useful. As you might expect, the first step in divide-and-conquer is divide and the second step is conquer.
But you may not have guessed that there are three steps. And I am leaving some blank space here, so you should, too. Divide-and-conquer is an algorithmic technique. You are given some big problem you want to solve, you don't really know how to solve it in an _________ way, so you are going to split it up into ___________. That is the divide. You are going to divide that problem, or more precisely the instance of that problem, the particular instance of that problem you have into subproblems. And those subproblems should be smaller in some sense. And smaller means normally that the value of N is smaller than it was in the original problem. So, you sort of made some progress. Now you have one, or more likely you have several subproblems you need to solve. Each of them is smaller. So, you recursively solve each subproblem.
That is the conquer step. You conquer each subproblem recursively. And then somehow you combine those solutions into a solution for the whole problem. So, this is the general divide-and-conquer ___________. And lots of algorithms fit it. You have already seen one algorithm that fits this paradigm, if you can remember. Merge sort, good. Wow, you are all awake. I'm ____________. So, we saw merge sort. And, if I am clever, I could fit it in this space. Sure. Let's be clever. A quick review on merge sort. Phrased in this 1, 2, 3 kind of method. The first step was to divide your ________ into two halves. This really doesn't mean anything because you just sort of think, oh, I will pretend my array is divided into two halves.
There is no work here. This is zero time. You just look at your array. Here is your array. I guess maybe you compute n/2 and take the floor. That takes __________ time. And you say OK, I am pretending my array is now divided into the left part and the right part. And then the interesting part is that you recursively solve each one. That's the conquer. We recursively sort each subarray. And then the third step is to ___________ those solutions. And so here we really see what this means. We now have a sorted version of this array by induction. We have a sorted version of this array by induction
Transcript - Lecture 3
Good morning everyone. Today we are going to do some algorithms, back to algorithms, and we are going to use a lot of the, well, some of the simpler mathematics that we developed last class like the master theorem for solving recurrences. We are going to use this a lot. Because we are going to talk about recursive algorithms today. And so we will find their running time using the master theorem. This is just the same as it was last time, I hope, unless I made a mistake. A couple of reminders. You should all go to recitation on Friday. That is required. If you want to, you can go to homework lab on Sunday. That may be a good excuse for you to actually work on your problem set a few hours early.
Well, actually, it's due on Wednesday so you have lots of time. And there is no class on Monday. It is the holiday known as Student Holiday, so don't come. Today we are going to cover something called Divide and Conquer. Also known as divide and rule or divide et impera for those of you who know Latin, which is a tried and tested way of conquering a land by dividing it into sections of some kind. It could be different political factions, different whatever. And then somehow making them no longer like each other. Like starting a family feud is always a good method. You should remember this on your quiz. I'm kidding.
And if you can separate this big power structure into little power structures such that you dominate each little power structure then you can conquer all of them individually, as long as you make sure they don't get back together. That is divide and conquer as practiced, say, by the British. But today we are going to do divide and conquer as practiced in Cormen, Leiserson, Rivest and Stein or every other algorithm textbook. This is a very basic and very powerful algorithm design technique. So, this is our first real algorithm design experience.
We are still sort of mostly in the analysis mode, but we are going to do some actual design. We're going to cover maybe only three or four major design techniques. This is one of them, so it is really important. And it will lead to all sorts of recurrences, so we will get to use everything from last class and see why it is useful. As you might expect, the first step in divide-and-conquer is divide and the second step is conquer.
But you may not have guessed that there are three steps. And I am leaving some blank space here, so you should, too. Divide-and-conquer is an algorithmic technique. You are given some big problem you want to solve, you don't really know how to solve it in an efficient way, so you are going to split it up into subproblems. That is the divide. You are going to divide that problem, or more precisely the instance of that problem, the particular instance of that problem you have into subproblems. And those subproblems should be smaller in some sense. And smaller means normally that the value of N is smaller than it was in the original problem. So, you sort of made some progress. Now you have one, or more likely you have several subproblems you need to solve. Each of them is smaller. So, you recursively solve each subproblem.
That is the conquer step. You conquer each subproblem recursively. And then somehow you combine those solutions into a solution for the whole problem. So, this is the general divide-and-conquer paradigm. And lots of algorithms fit it. You have already seen one algorithm that fits this paradigm, if you can remember. Merge sort, good. Wow, you are all awake. I'm impressed. So, we saw merge sort. And, if I am clever, I could fit it in this space. Sure. Let's be clever. A quick review on merge sort. Phrased in this 1, 2, 3 kind of method. The first step was to divide your array into two halves. This really doesn't mean anything because you just sort of think, oh, I will pretend my array is divided into two halves.
There is no work here. This is zero time. You just look at your array. Here is your array. I guess maybe you compute n/2 and take the floor. That takes constant time. And you say OK, I am pretending my array is now divided into the left part and the right part. And then the interesting part is that you recursively solve each one. That's the conquer. We recursively sort each subarray. And then the third step is to combine those solutions. And so here we really see what this means. We now have a sorted version of this array by induction. We have a sorted version of this array by induction