Warm-up

Loading...

Aus dem Kurs von University of California San Diego

Mathematical Thinking in Computer Science

480 Bewertungen

University of California San Diego

Mathematical Thinking in Computer Science

480 Bewertungen

Kurs 1 von 5 in Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Aus der Unterrichtseinheit

How to Find an Example?

How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, in many cases, the search space is enormous. A computer may help, but some reasoning that narrows the search space is important both for computer search and for "bare hands" work. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.

Subset without x and 100-x4:10

Rooks on a Chessboard2:39

Knights on a Chessboard5:09

Bishops on a Chessboard2:42

Subset without x and 2x6:24

Treffen Sie die Kursleiter

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

For everybody, welcome back.

In this lesson,we are going to discuss ways of showing optimality.

As a warm up example,

consider the following situation.

Imagine a small chocolate factory that produces two types of chocolate,

milk chocolate and dark chocolate.

The price per box of milk chocolate is $10,

and the price per box of the dark chocolate is $30.

Okay. So, the estimated daily demands are

500 boxes of milk chocolate and 200 boxes of dark chocolate.

Unfortunately, the factory cannot fully

satisfy these daily demands because it can produce,

at most, 600 boxes per day.

So, on these given constraints,

the natural question is,

what is the optimum production plan?

To find it out,

they go to a consulting company,

and the consulting company claims that the optimum profit per day is $10,000.

So, the question is now,

how can the consulting company convince the factory that it is indeed optimal?

So, in general, such proof of optimality consists of two parts.

The first part is the so-called existential part.

In this case, we need to show that there exists a production plan,

achieving the value of $10,000.

All right.

And the other part is the so-called universal part.

We need to show that for all plans, the profits that they'll achieve is at most 10,000.

Let's start with the existential part.

So once again, for this,

we need to give the explicit production plan,

achieving $10,000 per day.

And for this, the consulting company suggests that the factory needs to

produce 400 boxes of milk chocolate per day and 200 boxes of dark chocolate per day.

First of all, we need to check whether all the constraints are satisfied,

and this is not difficult to do.

First of all, in the proposal plan,

the factory produces no more than 500 boxes of milk chocolate and

also no more than 200 boxes of dark chocolate,

and then total, no more than 600 boxes.

And indeed, the profit can also be easily computed.

This is 400 boxes of milk chocolate x $10 per

box + 200 boxes of dark chocolate x $30 per box of dark chocolate.

This gives exactly 10,000. So, we are done with the existential part.

Now we need to show the universal part,

mainly, we need to show that in any production, in any valid production plan,

mainly in any plan satisfying all the given constraints,

the profit is at most 10,000.

Okay, so for this, let's denote by M,

and these are number of boxes of milk and dark chocolate,

respectively, produced per day.

Then we are given the following constraints,

M should be at most 500, D should be at most 200, these are our estimated daily demands,

and M+D should be at most 600,

because the factory can not produce more than 600 boxes per day.

What we would like to show is that,

under these constraints, the profit is at most $10,000.

The profit is computed as 10 times M plus 30 times D. Okay.

So to prove this,

it is enough actually to compute the sum of the following two inequalities.

The first inequality is,

10M+10D is at most 6,000.

So it comes by multiplying this inequality M+D is at most, 600 by 10.

Then we do multiply it by 10,

we get 10M+10D is at most 6,000.

On the other hand, we can also get this inequality,

D is at most 200 and multiply it by 20,

then we'll get 20D is at most 4,000.

then if we compute the sum of these two inequalities, then

what we get is exactly what we want to get,

the sum, that the profit is at most 10,000.

Well, that was easy, right?

And it was actually clear from the very beginning that in this case,

the optimal production plan actually is to produce as

much dark chocolate as needed and only then to produce milk chocolate.

But the message of this short warm up video

was not about chocolate, but about optimality.

So once again, to show that some value alpha is optimal,

what we usually need to do is to show that,

first of all, this value is achievable, that is,

to provide some solutions that achieves the value alpha,

this is the existential statement.

And then we need to show the universal statement,

that all solutions achieve the value not greater than alpha.

So in this lesson we are going to

show several such examples of optimality, following the same pattern.

Durchsuchen Sie unseren Katalog

Melden Sie sich kostenlos an und erhalten Sie individuelle Empfehlungen, Aktualisierungen und Angebote.

Coursera arbeitet mit erstklassigen Universitäten und Organisationen zusammen, um Online-Kurse anzubieten und dadurch universellen Zugriff auf die weltweit beste Ausbildung zu ermöglichen.

© 2019 Coursera Inc. Alle Rechte vorbehalten.

Aus dem App Store herunterladen

Erhältlich bei Google Play