Explore
For Enterprise
Join for Free
Log In

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Knights on a Chessboard

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

Our next puzzle is about knights on a chessboard. Knight moves in an L-shape. For example, the knight shown here on this slide can move to any of the shown eight positions. The knight moves by one cell vertically and two cells horizontally, or vice versa. Okay, so the natural question, you can guess it already, of course, is, what is the maximum number of knights that one can place on a chessboard such that no two knights attack each other? While trying to solve this problem, let's take a look once again on the allowed moves for the knight. Okay, as we see, the knight here stays on a white cell. And all the eight cells that it attacks, are actually of an opposite color. They're all black, right? So this already tells us something. So it tells us that if we place knights on all 32 white cells like here, then definitely no two of them are going to attack each other. So you can either check this manually, or you can either once again notice that a knight standing on a white cell only attacks black cells. Right, so this is already good. We have a solution where we have 32 knights. It is still at the same time not clear whether it is optimal or not. It is clear that this one cannot be expanded, we cannot put more knights here on the chess board. At the same time, it is still not excluded that there is some other solution whose size is greater than 32. So let's try to understand how one would show that it is not possible to place more than 32 knights. First of all, why we cannot just place knights to all 64 cells? Just because in particular, it is not possible to place knights simultaneously to these two cells, to the left bottom corner and to the position shown here on this slide. So in a sense, these two cells form a pair. For this pair of cells, we can select only one of them. We cannot select them simultaneously. Like in one of the examples shown, considered before. To reflect this fact, let's connect them by a segment. And now let's realize the following. It would be great if we could partition all our 64 cells into such pairs. In this case, we would be done, just because this would mean that everything is partitioned into pairs, and so the number of pairs is 32. And for every pair, we know that we can make at most one cell. We can place at most one knight into these two cells. This will immediately mean that 32 is indeed optimal. The only thing which is still not clear is how to partition the whole work in to such pairs. So let's at least try to do this. So first of all we have this pair. Let's add this symmetrical pair. Let's now add two more pairs, which are also, in a sense, similar. And now, we have this nice feature. Why it is nice? Because it is already a rectangle. It is a two by four rectangle. And so what we already know is that for this two by four rectangle, the number of knights that can be placed inside this rectangle is at most four, right? Because there are eight cells in this rectangle. And all these eight cells are partitioned into four pairs. For each pair, we know that, for each pair of such cells, we know that we can place at most one knight into them. So there are four pairs, and for each pair we can place at most one knight. So at most four knights. Which is great, already. And the fact that this rectangle is of size two by four actually implies that we can partition the whole board into such rectangles, right? Like these, which in turn means that we can partition the whole board into such pairs, which finally proves that 32 is indeed the answer for our initial problem.

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