Explore
For Enterprise
Join for Free
Log In

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Warm-up

Loading...

Mathematical Thinking in Computer Science

University of California San Diego

4.5 (641 Bewertungen) | 34K Teilnehmer angemeldet

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

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

Lehrplan anzeigen

Kompetenzen, die Sie erwerben

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Bewertungen

4.5 (641 Bewertungen)

5 stars
420 ratings
4 stars
145 ratings
3 stars
52 ratings
2 stars
11 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!

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

Unterrichtet von

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

Skript

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.

Erhältlich bei Google Play

Coursera
Info
Leitung
Jobs
Katalog
Zertifikate
MasterTrack™-Zertifikate
Abschlüsse
Für Unternehmen
Für Regierungen
Für Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Verbinden
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Tech-Blog

Mehr
Nutzungsbedingungen/AGB
Datenschutz
Hilfe
Barrierefreiheit
Presse
Kontakt
Verzeichnis
Partnerunternehmen