More Coffee

Loading...

Del curso dictado por University of California San Diego

What is a Proof?

171 calificaciones

University of California San Diego

What is a Proof?

171 calificaciones

Curso 1 de 5 en SpecializationIntroduction 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.

De la lección

Invariants

"There are things that never change". Apart from being just a philosophical statement, this phrase turns out to be an important idea that can actually help. In this module we will see how it can help in problem solving. Things that do not change are called invariants in mathematics. They form an important tool of proving with numerous applications, including estimating running time of programs and algorithms. We will get some intuition of what they are, see how they can look like, and get some practice in using them.

More Coffee4:18

Debugging Problem2:34

Conoce a los instructores

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

Continuing with the following problem.

There are two equally sized cups.

One with coffee and another one with milk and both cups are half full.

So we prefer the first cup.

And also we prefer our coffee with lots of milk.

We would like to have one third of coffee and two thirds of milk.

And we are allowed to put coffee and milk back and forth from between two cups.

And can we get our favorite coffee in our favorite cup?

And it doesn't, the amount doesn't matter.

We would like to get our favorite proportion.

So in the previous problem,

we have discussed coffee and milk and we have

shown that if you do this process then the amount of coffee removed

from the first cup to the second cup is the same as

the amount of milk removed from the second cup to the first cup,

but it doesn't help here.

We would like to have the right proportion in

the first cup and it doesn't matter for us what happens in the second cup.

We are fine if it is mostly coffee.

So it doesn't help. But yet invariants can help here.

So, The problem was to find the right invariant.

For this we will show the following claim.

During this process,

the proportion of coffee in the first cup is always greater than in the second cup.

That means that in the first cup the coffee is always stronger. Why this helps?

Indeed, it is inequality will be our invariant.

It doesn't change so, we always have inequality here.

The coffee in the first cup is stronger than the coffee in the second cup.

So, on the other hand it doesn't allow us to have more milk than coffee in the first cup.

Why? Indeed, if it was the case,

if you had more milk than the coffee in the first cup then the same true for the second,

second cup.

Because there the drink is,

it contains even less proportions,

smaller proportion of coffee.

So then in both cups, we have more milk than coffee

but this is a contradiction because the total amount of coffee and milk is the same.

So if the claim is true,

we cannot have more than coffee in the first cup.

And so we kind of have two third of milk here and one third of coffee.

So why the claim is true?

Let's look at the picture.

But look at one step of the process

and it will show that if an inequality is true in the beginning of a step.

That is, if the coffee in the first cup is stronger in the beginning of the step,

then it will be stronger after the step.

So there are two possibilities of what we can do during the last one step.

The first possibility is that we can pour some drink from the first cup to a second cup.

And in this case we take part of a drink from the first cup and we

pour it into the second cup where a proportion of milk is greater.

So, we milk down some of our coffee from the first cup in the second cup.

The proportion of coffee in our drink

reduces when we mix it with a part of it in the second cup.

For the second case,

In the second case we can pour some drink from the second cup to the first cup.

So let's look what happens.

Our, in our second cup mostly milk and then we pour part of it into the first cup.

And there proportion of coffee is greater.

So we coffee down our milk from the second cup in the first cup.

So the proportion of milk decreases when we put

some part of the second cup to the first cup and the proportion of coffee increases.

So the inequality is two wholes.

The proportion of coffee in the first cup

is greater than the proportion of coffee in the second cup.

And the claim follows.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play