Explore
For Enterprise
Join for Free
Log In

HEC Paris
MSc in Entrepreneurship and Innovation
Get an MSIE from a top business school. Apply by Feb 17 to get 2,000 EUR off.
University of London
Bachelor of Computer Science
This bachelor's degree offers 7 concentrations so students can pick where their career goes

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Principales cursos
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 (682 calificaciones) | 37K estudiantes inscritos

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

Inscríbete gratis

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 (682 calificaciones)

5 stars
447 ratings
4 stars
153 ratings
3 stars
53 ratings
2 stars
13 ratings
1 star
16 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

Prueba el curso Gratis

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

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

Comunidad

Estudiantes
Socios
Desarrolladores
Probador beta
Traductores
Blog
Blog de Tecnología

Más

Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados

Aprende en cualquier lado

Síguenos

© 2020 Coursera Inc. Todos los derechos reservados.