Explore
For Enterprise
Join for Free
Log In

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

More Coffee

Loading...

Mathematical Thinking in Computer Science

Universidad de California en San Diego

4.5 (650 calificaciones) | 35K estudiantes inscritos

Curso 1 de 5 en Introduction to Discrete Mathematics for Computer Science Programa Especializado

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. Do you have technical problems? Write to us: coursera@hse.ru

Destrezas que aprenderás

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Revisiones

4.5 (650 calificaciones)

5 stars
426 ratings
4 stars
147 ratings
3 stars
52 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

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

Impartido por:

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

Transcripción

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 provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. Todos los derechos reservados.

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados