Discrete Mathematics DSBA2019/2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Weekly Materials)
(Colloquiums)
 
(не показано 126 промежуточных версии 4 участников)
Строка 1: Строка 1:
== Blended part  ==
+
== Exams ==
  
The first topic of our course is  ``What is a Proof?". It is the first week ``Making Convincing Arguments" on the Coursera [https://ru.coursera.org/learn/what-is-a-proof course ]. It is recommended (but not obligated) to study the whole course.
+
== Colloquiums ==
  
==Exam ==
+
The 1st Colloquium is scheduled for February, 1 (room R301, from 3:00 till 9:00 pm). Please have a look at the [https://drive.google.com/open?id=1plE4LaEfDak34sP4BeVR9TcBm2Ww3V9l questions and rules] thereof. The exact time for each student to come will be determined later.
  
[http://rubtsov.su/public/hse/2018/midterm0.pdf  Zero variant].
+
== Current Results ==
 +
You can check your progress up to now via the
 +
[https://docs.google.com/spreadsheets/d/10DnnnhiiHIu0mG-gLLhKr8dz703pFkaMtWmUzxm2QC0/edit#gid=1264223279 DM1 Register Online].
  
Exam will take place in the room <b>622</b>. Note that you are allowed to use any written or printed materials, but not allowed to use any electronic device. Please take your own paper with you.
+
== Homework Deadlines ==
 +
'''For Group 191:'''
  
==Colloquium ==
+
* HW 1 -- September 23, 2019
 +
* HW 2 -- September 30, 2019
 +
* HW 3 -- October 28, 2019
 +
* HW 4 -- November 15, 2019
 +
* HW 5 -- November 25, 2019
 +
* HW 6 -- December 9, 2019
 +
* HW 7 -- February 10, 2020
  
The  [http://rubtsov.su/public/hse/2018/Colloquium_program_DSBA.pdf program] of the colloquium is ready. The examples of problems would be updated.
+
'''For Groups 192 and 193:'''
  
Colloquium will be on December 12. The timetable would be available soon.
+
* HW 1 -- September 24, 2019
 +
* HW 2 -- October 1, 2019
 +
* HW 3 -- October <s>15</s> 29, 2019
 +
* HW 4 (except ex. 6-9, 12, 14) -- November 15, 2019
 +
* HW 4 (ex. 6-9, 12, 14), HW 5 (ex. 1-4) -- November 22, 2019
 +
* HW 5 (ex. 4-8) -- November 26, 2019
 +
* HW 6 -- December 10, 2019
  
<b>Schedule:</b> groups 181 and 182 start at 13:40 in the room 509; group 183 starts at 16:40 in the room 622.
+
== Online Consultation ==
  
==Weekly Materials ==
+
If you have any questions regarding the Course, please feel free to ask them via our Telegram chat [https://t.me/joinchat/FnMTXFHUPOE16c3k3YImJQ DSBA19-20 DM1 Public]. Alternatively, you may use the Lecturer's [https://vk.com/evgeny.v.dashkov VK page] or send us an email (e:d,a:s.h:k;o,v AT gmail.com -- without punctuation marks to the left of AT, of course).
 +
 
 +
== Materials ==
 +
 
 +
You can find some useful materials (including the Lecture Notes) [https://drive.google.com/drive/folders/1o8EJwM9L4zwTVKIJh-lkjwfHfHPAv1ua?usp=sharing here].
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
! Problems || Keywords || Handouts
+
! Problems || Keywords  
 
|-
 
|-
  ||  [http://rubtsov.su/public/hse/2018/cw01_dsba.pdf Problems week 1] ||  [http://rubtsov.su/public/hse/2018/keywords_1.pdf Keywords week 1]  ||  [http://rubtsov.su/public/hse/2018/boolean_laws.pdf Properties of Boolean Formulas]  
+
  ||  [https://drive.google.com/open?id=1rBFUo9XTGQ7e3BFlwZw9oi4Ja8N8uKba cw1] ||  [https://drive.google.com/open?id=1kQGeAAaB-gqb2OLGovMTmtqIZ4YSPS1c kw1]  
 
|-
 
|-
  ||  [http://rubtsov.su/public/hse/2018/cw02_dsba.pdf Problems week 2] || [http://rubtsov.su/public/hse/2018/keywords_2.pdf Keywords week 2] || 
+
  ||  [https://drive.google.com/file/d/1I-NBJx7HXldcTKHHFqfxjsqTmQZ12lIk/view?usp=sharing cw2] || [https://drive.google.com/open?id=113ucNaQObqJkvytp0Vb2_RlODavtaedd  kw2]
 
|-
 
|-
  ||  [http://rubtsov.su/public/hse/2018/cw03_dsba.pdf Problems week 3] || [http://rubtsov.su/public/hse/2018/keywords_3.pdf Keywords week 3] || 
+
  ||  [https://drive.google.com/open?id=1vfUah9MiFySTPfdjV3OTAEd4fgeDJ1gw cw3] || [https://drive.google.com/open?id=1rspTwMDVmhDv4v3HbvJ_VUT-wMugJjX8  kw3]
 
|-
 
|-
  ||  [http://rubtsov.su/public/hse/2018/cw04_dsba.pdf Problems week 4] || [http://rubtsov.su/public/hse/2018/keywords_4.pdf Keywords week 4] || 
+
  ||  [https://drive.google.com/open?id=1NgulEyScQOcbUUZ2zkYyGon9i-vJrAjb cw4] || [https://drive.google.com/open?id=1jfb_GaxhPJEy1Irx4VTwXVCEjnGj_K63 kw4]
 
|-
 
|-
  ||  [http://rubtsov.su/public/hse/2018/cw05_dsba.pdf Problems week 5] || [http://rubtsov.su/public/hse/2018/keywords_5.pdf Plan and Keywords week 5] || 
+
  ||  [https://drive.google.com/open?id=16keB-odowxB6RXOBhz9nSqz4zqFHklOK cw5] || [https://drive.google.com/open?id=1dQGbQAjejlP57igBPAUqoFul1pWepTmF kw5]
 
|-
 
|-
  || [http://rubtsov.su/public/hse/2018/cw06_dsba.pdf Problems week 6] || [http://rubtsov.su/public/hse/2018/keywords_6.pdf Plan week 6] || 
+
  || [https://drive.google.com/open?id=1cDhwWqrYHZaBh06YuPi8K7g3fBcPDbYz cw6] || [https://drive.google.com/open?id=1ksuILmp-AX44oaMdRZe3JpBDC8zlG4nX kw6]
 
|-
 
|-
  || [http://rubtsov.su/public/hse/2018/cw07_dsba.pdf Problems week 7] ||[http://rubtsov.su/public/hse/2018/keywords_7.pdf Plan and Keywords week 7] || 
+
  || [https://drive.google.com/open?id=1RWxKdYuskUNyjJA_CK9yFLM62tKWtNmZ cw7] || []
 
|-
 
|-
  || [http://rubtsov.su/public/hse/2018/cw08_dsba.pdf Problems week 8] || [http://rubtsov.su/public/hse/2018/keywords_8.pdf Plan and Keywords week 8]   ||
+
  || [https://drive.google.com/open?id=1WIJCdO4cvQLRBgX7N692XM7w3xbuha64 cw8] || []
|-
+
||  [http://rubtsov.su/public/hse/2018/cw09_dsba.pdf Problems week 9] ||  [http://rubtsov.su/public/hse/2018/keywords_9.pdf Plan and Keywords week 9] || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw10_dsba.pdf Problems week 10] || [http://rubtsov.su/public/hse/2018/keywords_10.pdf Plan and Keywords week 10]  || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw11_dsba.pdf Problems week 11] ||  || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw12_dsba.pdf Problems week 12] || || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw13_dsba.pdf Problems week 13] || || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw14_dsba.pdf Problems week 14] || || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw15_dsba.pdf Problems week 15] ||  [http://rubtsov.su/public/hse/2018/keywords_15.pdf Plan and Keywords week 15]    || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw16_dsba.pdf Problems week 16] ||  [http://rubtsov.su/public/hse/2018/keywords_16.pdf Plan and Keywords week 16]    || 
+
|-
+
||  [http://rubtsov.su/public/hse/2018/cw17_dsba.pdf Problems week 17] ||  [http://rubtsov.su/public/hse/2018/keywords_17.pdf Plan and Keywords week 17]    || 
+
 
+
 
|}
 
|}
  
== Schedule for office hours and consultations ==
+
== Office hours ==
  
 
{| class = "wikitable"
 
{| class = "wikitable"
Строка 65: Строка 65:
 
! Teacher / Assistant !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
 
! Teacher / Assistant !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
 
|-
 
|-
| Alexander A. Rubtsov || || 17:00 - 18:00, room 617|| 17:00 - 18:00, room 511  || ||
+
| Evgeny V. Dashkov || from 3:10 till 5 p.m. in room S913 || || || ||
|-
+
| Alexey K. Kovalev || || || 16:40 - 18:00, room 427 or 619|| ||
+
|-
+
| Boris R. Danilov || || || ||  || 09:30 - 12:00, room 623
+
|-
+
| Tatyana Vasilyeva || || || || ||
+
|-
+
| Sofya Kudryavtseva  || || || || ||
+
|-
+
| Anastasia Tabisheva || || || || ||  
+
 
|-
 
|-
 +
| Boris R. Danilov || || from 10:00 till 11:30 a.m., room S913, by appointment || ||  ||
 
|}
 
|}
  
==Recommended books ==
+
==Recommended Reading ==
 +
''Please notice that '''The Book''' for our Course does not exist. The latter is based on many sources.''
  
=== Assigned Reading ===
+
#      Anderson J. A., Discrete Mathematics With Combinatorics. Prentice Hall, 2003.
1. L. Lovasz, K. Vesztergombi. Discrete Mathematics. Lecture Notes, Yale University, 1999. http://www.cs.elte.hu/~lovasz/dmbook.ps  
+
#      Biggs N. L., Discrete mathematics. 2nd ed., New York; Oxford: Oxford University Press, 2004.
 +
#      Gavrilov G. P., Sapozhenko A. A. Problems and Exercises in Discrete Mathematics. Kluwer Texts in the Mathematical Sciences 14. Springer, 1996.
 +
#      [http://courses.csail.mit.edu/6.042/spring17/mcs.pdf Lehman E., Thomson Leighton F., Meyer A. R. Mathematics for Computer Science, 2017.]
 +
#      [http://www.cs.elte.hu/~lovasz/dmbook.ps Lovasz L., Vesztergombi K. Discrete Mathematics. Lecture Notes; Yale University, 1999.]
 +
#      Melnikov O., Sarvanov V., Tyshkevich R., Yemelichev V., Zverovich I. Exercises in Graph Theory. Kluwer Texts in the Mathematical Sciences 19. Springer, 1998.
 +
#      Rosen K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 1999.
 +
#      Stein C., Drysdale R. L., Bogart K. Discrete mathematics for computer scientists. Addison-Wesley, 2010.
 +
#      Vinogradov I. M. Elements of number theory. Dover, 1954.
  
2. C. Stein, R. Drysdale, K. Bogart. Discrete mathematics for computer scientists. Pearson; 1 edition 2010
 
 
3. J. Anderson. Discrete Mathematics With Combinatroics. Prentice Hall; 2 edition 2003
 
 
7.    K. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill; 7th edition 2007
 
 
8.  E. Lehman, F. Thomson Leighton, A. R. Meyer. Mathematics for Computer Science, https://courses.csail.mit.edu/6.042/spring17/mcs.pdf
 
 
==== In Russian  ====
 
==== In Russian  ====
4. M. Vyalyi, V. Podolsky, A. Rubtsov. D. Shvarts, A. Shen. Lectures on Discrete Mathematics [http://rubtsov.su/public/DM-HSE-Draft.pdf  Draft]
+
''If you understand Russian (by any chance), you will probably benefit from reading the following books.''
  
5. A. Shen. Mathematical induction (C1) 3rd ed., Moscow: MCCME, 2007, 32 p. http://www.mccme.ru/free-books/shen/shen-induction.pdf  
+
#      Виноградов И. М. Основы теории чисел. 9-е изд., М.: Наука, 1981.
 
+
#      [http://rubtsov.su/public/DM-HSE-Draft.pdf Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Лекции по дискретной математике.]
6. N. K. Vereshchagin, A. Shen. Introduction to the set theory. 4th ed., Moscow: MCCME, 2012, 112 с. http://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf
+
#      Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., М.: ФИЗМАТЛИТ, 2004.
 
+
#      [https://drive.google.com/file/d/1DBwUuZhHjAJhKmyDeAwQGf9R69YDAeAZ/view?usp=sharing Дашков Е. В. Введение в математическую логику. Множества и отношения. М.: МФТИ, 2019.]
=== Additional Reading ===
+
#      Зубков А. М., Севастьянов Б. А., Чистяков В. П. Сборник задач по теории вероятностей. 2-е изд., М.: Наука, 1989.
* R. Distel. Graph theory, GTM 173, 5th ed. 2016. Springer-Verlag, Heidelberg, Graduate Texts in Mathematics, Vol. 173, 447 p.
+
#      Мельников О. И. Теория графов в занимательных задачах. 5-е изд., М.: Книжный дом "ЛИБРОКОМ", 2013.
* R. Hammack. Book of Proof, Virginia Commonwealth University 2013, https://www.people.vcu.edu/~rhammack/BookOfProof/BookOfProof.pdf  
+
#      [http://www.mccme.ru/free-books/shen/shen-induction.pdf Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.]
* S. Jukna, Extremal Combinatorics. Texts in Theoretical Computer Science. An EATCS Series. 2nd ed. 2011, XXIV, 308 p.
+
  
 
==Grading System ==
 
==Grading System ==
  
'''Intermediate grade 1'''
+
'''Intermediate grade-2''' = (1/2) colloquium-2 + (1/2) homework-2.
 
+
Cumulative grade-1 = 50% colloquium-1 + 50% homework
+
 
+
Intermediate grade (module 2) = 60% cumulative grade-1 + 40% intermediate exam (module 2)
+
 
+
'''Intermediate grade 2'''
+
 
+
Cumulative grade = (3/14) colloquium-1 + (3/14)colloquium-2 + (3/14) intermediate exam + (15/42) homework  
+
 
+
Intermediate grade = 70% cumulative grade + 30% final exam
+
  
Grade “homework assignments” is an average grade of all the homework assignments in the course.
+
'''Cumulative grade-3''' = (3/10) colloquium-2 + (3/10) colloquium-3 + (4/10) homework-3.
  
'''Intermediate grade 2 is the final grade for the course included in a diploma supplement.'''  
+
'''Final grade-3''' = min(10, (7/10) cumulative grade-3 + (3/10) final exam + (1/10) bonus points).
  
Rounding of the cumulative grade, intermediate and final grades must be performed according to the following rules. Rounding down for marks between 1 and 5, rounding by the rules of arithmetic for marks between 5 and 6, and rounding up for all the other marks.
+
The number in a grade’s name is the number of the module when grading takes  place. The grade homework-n is the normalized average grade for the homework in modules from 1 to n. The Intermediate and Final grades are subject to rounding half up to an integer. All the other grades are reported with the greatest precision available.
  
There is no possibility to get an extra point to compensate the low cumulative grade.
+
Bonus point number is between 0 to 20. Such points may be given for a variety of auxiliary activities.

Текущая версия на 17:42, 28 января 2020

Exams

Colloquiums

The 1st Colloquium is scheduled for February, 1 (room R301, from 3:00 till 9:00 pm). Please have a look at the questions and rules thereof. The exact time for each student to come will be determined later.

Current Results

You can check your progress up to now via the DM1 Register Online.

Homework Deadlines

For Group 191:

  • HW 1 -- September 23, 2019
  • HW 2 -- September 30, 2019
  • HW 3 -- October 28, 2019
  • HW 4 -- November 15, 2019
  • HW 5 -- November 25, 2019
  • HW 6 -- December 9, 2019
  • HW 7 -- February 10, 2020

For Groups 192 and 193:

  • HW 1 -- September 24, 2019
  • HW 2 -- October 1, 2019
  • HW 3 -- October 15 29, 2019
  • HW 4 (except ex. 6-9, 12, 14) -- November 15, 2019
  • HW 4 (ex. 6-9, 12, 14), HW 5 (ex. 1-4) -- November 22, 2019
  • HW 5 (ex. 4-8) -- November 26, 2019
  • HW 6 -- December 10, 2019

Online Consultation

If you have any questions regarding the Course, please feel free to ask them via our Telegram chat DSBA19-20 DM1 Public. Alternatively, you may use the Lecturer's VK page or send us an email (e:d,a:s.h:k;o,v AT gmail.com -- without punctuation marks to the left of AT, of course).

Materials

You can find some useful materials (including the Lecture Notes) here.

Problems Keywords
cw1 kw1
cw2 kw2
cw3 kw3
cw4 kw4
cw5 kw5
cw6 kw6
cw7 []
cw8 []

Office hours

Teacher / Assistant Monday Tuesday Wednesday Thursday Friday
Evgeny V. Dashkov from 3:10 till 5 p.m. in room S913
Boris R. Danilov from 10:00 till 11:30 a.m., room S913, by appointment

Recommended Reading

Please notice that The Book for our Course does not exist. The latter is based on many sources.

  1. Anderson J. A., Discrete Mathematics With Combinatorics. Prentice Hall, 2003.
  2. Biggs N. L., Discrete mathematics. 2nd ed., New York; Oxford: Oxford University Press, 2004.
  3. Gavrilov G. P., Sapozhenko A. A. Problems and Exercises in Discrete Mathematics. Kluwer Texts in the Mathematical Sciences 14. Springer, 1996.
  4. Lehman E., Thomson Leighton F., Meyer A. R. Mathematics for Computer Science, 2017.
  5. Lovasz L., Vesztergombi K. Discrete Mathematics. Lecture Notes; Yale University, 1999.
  6. Melnikov O., Sarvanov V., Tyshkevich R., Yemelichev V., Zverovich I. Exercises in Graph Theory. Kluwer Texts in the Mathematical Sciences 19. Springer, 1998.
  7. Rosen K. H. Discrete Mathematics and Its Applications. McGraw-Hill, 1999.
  8. Stein C., Drysdale R. L., Bogart K. Discrete mathematics for computer scientists. Addison-Wesley, 2010.
  9. Vinogradov I. M. Elements of number theory. Dover, 1954.

In Russian

If you understand Russian (by any chance), you will probably benefit from reading the following books.

  1. Виноградов И. М. Основы теории чисел. 9-е изд., М.: Наука, 1981.
  2. Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Лекции по дискретной математике.
  3. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., М.: ФИЗМАТЛИТ, 2004.
  4. Дашков Е. В. Введение в математическую логику. Множества и отношения. М.: МФТИ, 2019.
  5. Зубков А. М., Севастьянов Б. А., Чистяков В. П. Сборник задач по теории вероятностей. 2-е изд., М.: Наука, 1989.
  6. Мельников О. И. Теория графов в занимательных задачах. 5-е изд., М.: Книжный дом "ЛИБРОКОМ", 2013.
  7. Шень А., Математическая индукция. 5-е изд, М.: МЦНМО, 2016.

Grading System

Intermediate grade-2 = (1/2) colloquium-2 + (1/2) homework-2.

Cumulative grade-3 = (3/10) colloquium-2 + (3/10) colloquium-3 + (4/10) homework-3.

Final grade-3 = min(10, (7/10) cumulative grade-3 + (3/10) final exam + (1/10) bonus points).

The number in a grade’s name is the number of the module when grading takes place. The grade homework-n is the normalized average grade for the homework in modules from 1 to n. The Intermediate and Final grades are subject to rounding half up to an integer. All the other grades are reported with the greatest precision available.

Bonus point number is between 0 to 20. Such points may be given for a variety of auxiliary activities.