Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Дискретная математика (ПМ).
Студенческий форум ГУ-ВШЭ > Государственный Университет - Высшая Школа Экономики > Прикладная математика и информатика
Страницы: 1, 2
Shvarts_DA
Предполагается, что здесь я буду отвечать на вопросы по упомянутому курсу, сообщать о новостях и выслушивать мнения студентов о курсе и обо мне. Надеюсь делать это раз в 1-2 дня, а в четверг вечером буду просматривать тему постоянно, чтобы on-line отвечать на вопросы готовящихся к семинару.

Вся помещенная мной здесь информация считается официальной.

Просьбы к студентам.

1. Если Вы уверены, что знаете ответ на заданный кем-то вопрос, ответьте. Идеально для меня было бы вечером просматривать тему и писать "ага, все ОК".

2. Мне очень важна Ваша реакция и советы, как сделать курс или свое преподавание лучше. Но интересы только содержательные отклики - для объяснений, какой я плохой или хороший преподаватель, существует рейтинг. Мне хочется знать, почему Вы так считаете.

Теперь про курс.

1-4-й модуль, отчетность - зачет в конце 2-го модуля и экзамен в конце 4-го. Оценка за экзамен равна среднему арифметическому всех контрольных, зачет - оценка за кр-2.

Преподаватели - Кузнецов Олег Петрович, Шварц Дмитрий Александрович (dshvarts dog mail dot ru).

Страничка курса. http://www.hse.ru/edu/courses/23121680.html. Вам здесь важна программа.

Мои консультации. Пт, 9.00-10.20, Г-???.

Учебники.

Дискретная математика для инженера. Кузнецов.
http://lib.hse.su/node/48

Дискретная математика для программистов. Новиков.
http://lib.hse.su/node/2

Задачники:

Лавров, Максимова.
http://lib.hse.su/node/160

Гаврилов, Сапоженко.
http://lib.hse.su/node/159

Мой Нажмите для просмотра прикрепленного файла задачник по комбинаторике.

А еще есть такая отличная книжка по комбинаторике для желающих получить удовольствие. Если цель - только написать контрольную, она не очень полезна.
http://lib.hse.su/node/161


Жду Ваших вопросов :-)

-------------------------

Сообщение от администрации (добавлено администратором):

Ребята, при регистрации на форуме пожалуйста внимательно заполняйте поля своего профиля, это поможет нашему антиспам-фильтру распознать в вас студентов. Спасибо!
Shvarts_DA
В качестве домашнего задания предлагаю сделать большую часть листка (это не страшно, большинство задач простые).

То, что должно быть просто - если уверены, можно пропустить. 2-7, 9, 16-17, 19, 21, 23, 25, 30, 31а, 33, 34а.

Похитрее. 8, 10, 11, 26, 28а,з, 29, 34г, 36г, 37.
evgeniako
Здравствуйте, Дмитрий Александрович!
У меня возник такой вопрос:
пустое множество является подмножеством любого множества
также подмножеством любого множества является оно само.
Значит ли это, что подмножество пустого множества - пустое множество?
Заранее спасибо

С уважением, Евгения К.
zVz
Цитата(evgeniako @ 3.9.2011, 10:37) *
Здравствуйте, Дмитрий Александрович!
У меня возник такой вопрос:
пустое множество является подмножеством любого множества
также подмножеством любого множества является оно само.
Значит ли это, что подмножество пустого множества - пустое множество?
Заранее спасибо

С уважением, Евгения К.


Да. Пустое множество является подмножеством любого множества.

Аскар.
Shvarts_DA
Цитата(evgeniako @ 3.9.2011, 11:37) *
Значит ли это, что подмножество пустого множества - пустое множество?


Да, причем единственное :-)
lenhens
Добрый вечер, Дмитрий Александрович!
При доказательстве 17(в) задумалась, является ли мое доказательство достаточным:
(AvB)A=A
(AA)v(AB)=A
AB-подмножество А => (AB)vA=(AvB)A=A

С уважением, Сотникова Лена
Shvarts_DA
Да, достаточно. В этом стиле можно чуть короче - сразу заметить, что А это подмножество объединения А и В.
Shvarts_DA
Обновил задачник. Домашнее задание -

1. Прочитать то, что я не успел на лекции (небольшой кусок про функции - с. 21-23 в новом (синем) издании Кузнецова).

2. Задачи 40, 41, 43, 45, 46, 47в,ж,з,и.

P.S. Адрес 174 группы мне по прежнему неизвестен. Староста, напишите его мне на почту, пожалуйста.
Misha
1. Нам в библиотеке ничего по дискре не выдали, а "новое (синее) издание Кузнецова" не согласуется с тем, что Вы выложили в первом посте. Можно ссылку на новое издание?

2. В задачнике номера 44а) и 45а) взамоисключающие...

3. а номер 43 вообще, вроде бы некорректен. Если области определения f и g не пересекаются, то все нормально. Может имелись ввиду не просто функции, а отображения?

4. В 47ж) нельзя пользоваться пользоваться результатами из пунктов з) и и), да?
evgeniako
Цитата(Misha @ 11.9.2011, 20:56) *
1. Нам в библиотеке ничего по дискре не выдали, а "новое (синее) издание Кузнецова" не согласуется с тем, что Вы выложили в первом посте. Можно ссылку на новое издание?

2. В задачнике номера 44а) и 45а) взамоисключающие...


Присоединяюсь к этим вопросам)
Мне выдали учебник Кузнецова, а задачников никаких
Какой из тех, что Вы рекомендовали, покупать для занятий? (и надо ли вообще)

А номера 44а и 45 а действительно друг другу противоречат, как мне показалось...
lisoveen
Цитата(Misha @ 11.9.2011, 20:56) *
1. Нам в библиотеке ничего по дискре не выдали, а "новое (синее) издание Кузнецова" не согласуется с тем, что Вы выложили в первом посте. Можно ссылку на новое издание?


Это?
Кузнецов О.П. Дискретная математика для инженера Учебное пособие. 6-е изд., стер. — СПб.: Издательство «Лань», 2009. — 400 с.: ил. — (Учебники для вузов. Специальная литература).
Shvarts_DA
Цитата(Misha @ 11.9.2011, 20:56) *
1. Нам в библиотеке ничего по дискре не выдали, а "новое (синее) издание Кузнецова" не согласуется с тем, что Вы выложили в первом посте. Можно ссылку на новое издание?

2. В задачнике номера 44а) и 45а) взамоисключающие...

3. а номер 43 вообще, вроде бы некорректен. Если области определения f и g не пересекаются, то все нормально. Может имелись ввиду не просто функции, а отображения?

4. В 47ж) нельзя пользоваться пользоваться результатами из пунктов з) и и), да?


1. Ответил выше. Спасибо за ссылку.

2. Вы правы. Приношу извинения. Но раз так получилось, не буду подсказывать, сами решите, какое утверждение верно :-)

3. Все корректно. Просто функция - частный случай соответствия. Пересечение соответствий всегда будет соответствием, а вот функицей не всегда.

4. Можно, но тогда нужно сделать з) и и).
Shvarts_DA
Цитата(evgeniako @ 12.9.2011, 21:26) *
Присоединяюсь к этим вопросам)
Мне выдали учебник Кузнецова, а задачников никаких
1. Какой из тех, что Вы рекомендовали, покупать для занятий? (и надо ли вообще)

2. А номера 44а и 45 а действительно друг другу противоречат, как мне показалось...


1. Я не буду пользоваться на семинарах ничем, кроме своих листков. Понадобится ли Вам больше задач, сказать не могу, но Вы уже можете это оценить по имеющимся листкам. По следующим темам задач будет в среднем столько же.

На этическую часть вопроса (пользоваться ли электронной версией или честнее купить бумажную) Вы ответите сами :-)

2. Да :-) Прокомментировал выше.
Misha
Цитата(Shvarts_DA @ 14.9.2011, 11:45) *
1. Ответил выше. Спасибо за ссылку.

2. Вы правы. Приношу извинения. Но раз так получилось, не буду подсказывать, сами решите, какое утверждение верно :-)

3. Все корректно. Просто функция - частный случай соответствия. Пересечение соответствий всегда будет соответствием, а вот функицей не всегда.

4. Можно, но тогда нужно сделать з) и и).


3.Контрпример к номеру 43(т.е. f и g неравны но их объединение всё равно функция). Множество аргументов - {0,1}, мн-во значений - тоже. f состоит из единственной пары (0,0), g - только из пары (1,1). их объединение - тоже функция.
Shvarts_DA
Цитата(Misha @ 14.9.2011, 13:07) *
3.Контрпример к номеру 43(т.е. f и g неравны но их объединение всё равно функция). Множество аргументов - {0,1}, мн-во значений - тоже. f состоит из единственной пары (0,0), g - только из пары (1,1). их объединение - тоже функция.


Да, я был не прав и не внимательно прочитал Ваш предыдущий пост. В этой задаче действительно предполагается, что функции должны быть всюду определены. Приношу извинения. По традиции "отлов" преподавателя на ошибке приравнивается к решению бонусной задачи. Так что, если хотите раскрыть ник (в личку - ?), то...
Misha
Цитата(Shvarts_DA @ 15.9.2011, 9:39) *
Да, я был не прав и не внимательно прочитал Ваш предыдущий пост. В этой задаче действительно предполагается, что функции должны быть всюду определены. Приношу извинения. По традиции "отлов" преподавателя на ошибке приравнивается к решению бонусной задачи. Так что, если хотите раскрыть ник (в личку - ?), то...


Миша Тёмкин smile.gif А что такое бонусная задача? Ведь те которые со звёздочками на лекции и семинаре разбирались...
Shvarts_DA
Цитата(Misha @ 15.9.2011, 22:21) *
А что такое бонусная задача? Ведь те которые со звёздочками на лекции и семинаре разбирались...


Пока да. Но дальше их будет больше и разбираться будут только после появления достаточного числа решений.
Shvarts_DA
Обновил задачник. Домашнее задание будет довольно большое.

48а, 49, 52, 53, 54бд, 60, 62, 64, 71, 72, 81, 83, 86, 91, 92.

Возможно, что Вам не хватит 1-2 определений. Их нужно прочитать у Кузнецова или спросить здесь.

P.S. Книги. По бинарным отношениям я рекомендую прочитать соответсвующую главу книги

Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А.
Бинарные отношения, графы и коллективные решения
М.: Издательский дом ГУ-ВШЭ, 2006. 298 с.

Если Вас заинтересовали темы конца последней лекции, можно почитать

Подиновский В.В. Введение в теорию важности критериев. Москва, Физматлит, 2007. Серия "Анализ и поддержка решений".
maskimka3
1. А в номере 64 частичные порядки идут по одному бинарному отношению или по разным? А то если по разным, то два несравнимых элемента в одном порядке могут быть сравнимы в другом.
2. В номере 71b по-моему опечатка, вместо последней b не должна стоять с? И внутри скобок сначала выполняется бинарное отношение или пересечение?
3. Как и когда сдавать задания со звёздочками?
4. В номере 84 во втором условии включение разве строгое?
Shvarts_DA
Цитата(maskimka3 @ 19.9.2011, 0:04) *
1. А в номере 64 частичные порядки идут по одному бинарному отношению или по разным? А то если по разным, то два несравнимых элемента в одном порядке могут быть сравнимы в другом.
2. В номере 71b по-моему опечатка, вместо последней b не должна стоять с? И внутри скобок сначала выполняется бинарное отношение или пересечение?
3. Как и когда сдавать задания со звёздочками?
4. В номере 84 во втором условии включение разве строгое?


1. Частичный порядок - это и есть бинарное отношение. Определены они на одном и том же множестве. Не знаю, ответил ли.

2. Да, Вы правы. Галочки -это логические "и" и "или". Они выполняются позже значков типа ">".

3. Письменно, перед семинаром.

4. Нестрогое, но я то как раз привык к ммм... европейской нотации.
MaXiMiliaN
"Возможно, в 3-м модуле Вы сдаете домашнее задание на зачет. В случае незачета оценка за курс уменьшается на 2 балла."

Т.е. вы в 3-м модуле проверите все ДЗ которые мы готовим к семинару или это будет отдельный блок задач который Вы выдадите нам в 3-м модуле на решение?
Shvarts_DA
Цитата(MaXiMiliaN @ 25.9.2011, 21:18) *
"Возможно, в 3-м модуле Вы сдаете домашнее задание на зачет. В случае незачета оценка за курс уменьшается на 2 балла."

Т.е. вы в 3-м модуле проверите все ДЗ которые мы готовим к семинару или это будет отдельный блок задач который Вы выдадите нам в 3-м модуле на решение?


Второй вариант верен. Обычно такое ДЗ было, но в прошлом году мы решили обойтись без него и, кажется, получилось неплохо. Возможно также, что у нас хватит сил на небольшой "практикум на ЭВМ".
Shvarts_DA
Добрый вечер! В конец первой темы вставлена текущая версия моего задачника по комбинаторике. Надеюсь, что он проходит последнюю предвыпускную обкатку, поэтому буду благодарен за любые комментарии и указания на опечатки и ошибки. Особо приветствуются ответы в тех задачах, где их нет.

Сейчас нас интересует первая глава. Прочитайте "самоучительную" часть (с. 4-5) и решайте задачи

5,8,11,15,17,21,26,29,32,44,47,55.

Еще меня спрашивали, где можно найти задачи на доказательство про бинарные отношения с решениями. Могу порекомендовать 3-ю главу своей книги :-) См. пост от 17.09. Она есть в библиотеке и, вероятно, в интернете. В конце главы задачи, многие с решениями.
Dronte
Задача 25.

Российский автомобильный номер не может содержать каждую из 33 букв русского алфавита. В них встречаются только те, которые есть в латинском алфавите. Например А в номерах встречается, а Й - никогда. Не знаю, важно ли это.
Shvarts_DA
Цитата(Dronte @ 29.9.2011, 0:09) *
Задача 25.

Российский автомобильный номер не может содержать каждую из 33 букв русского алфавита. В них встречаются только те, которые есть в латинском алфавите. Например А в номерах встречается, а Й - никогда. Не знаю, важно ли это.


Да, спасибо. Это важно (никогда не задумывался). А могут ли встречаться буквы Б и В?
MaXiMiliaN
Цитата(Shvarts_DA @ 29.9.2011, 14:04) *
Да, спасибо. Это важно (никогда не задумывался). А могут ли встречаться буквы Б и В?

Как автолюбитель могу утверждать, что встречаться могут всего двенадцать букв — А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Они русские, но такие, что похожи по печатному написанию на латинские, в связи с единой системой регистрации гос-автономерных знаков! По идее все буквы латинские, но в России их расшифровывают как русские, к примеру из серии "блатных" номеров ЕКХ (Еду Как Хочу) ОАО (Ольга Антон Ольга) и т.д. Кстате, такая система, после того как жители страны начали иметь по два и более автомобиля, учитывая рост и развитие транспортной системы и отсюда и количества автомобилей, стала порождать проблемы с нехваткой уникальных номерных знаков, а буквы внести новые нельзя, и поэтому решили к номеру региона приписывать слева цифру 1, т.е. раньше к Москве относились 77 97 99, а сейчас ещё и 177 197 199. Т.е. советую в задачу внести измения на сегодняшний день:
1- всего 12 латинских букв (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).
2- Номер субъекта России теперь может содержать не только две цифры но и три.
(пример: Х 777 КХ 77 и Х 777 КХ 177)
Stv
я так полагаю, это опечатка.
стр.2. 8-ая строчка снизу, 1-ое слово.
MaXiMiliaN
Цитата(Stv @ 29.9.2011, 18:22) *
я так полагаю, это опечатка.
стр.2. 8-ая строчка снизу, 1-ое слово.

Да. Тогда на 11 строке снизу на этой же 2-ой странице пробел нужно поставить между от И нюансов: "отнюансов"...
На 3-ей странице, пятая строка сверху, слово "урокои" поменять на "уроки"...и прочие опечатки, для книги, так сказать "на выпуск в массы" можно подкорректировать.
И проверить соответствие номеров задач и ответов к ним, к примеру в ответах: есть номер задачи 18, а ответ к этой задаче под номером 17.а.
Misha
А где звёздочки искать?)
Shvarts_DA
Цитата(Misha @ 29.9.2011, 19:42) *
А где звёздочки искать?)


Пока нигде. Умение решать комбинаторные задачи очень зависит от того, учились Вы в матшколе или нет. У матшкольников и так преимуществ на 1-м курсе много, не хочу создавать еще одно.

За опечатки большое спасибо - учту и исправлю. У редактора задачник еще не был :-)
Shvarts_DA
Уже написал на почту, но на всякий случай дублирую и сюда. Увы, но консультации завтра не будет.
MaXiMiliaN
55 задача.

Ниже очень интересный комментарий в задаче, что 0 - это не букет...с этим всё ясно, думаю что и 1 цветок тоже не стоит включать в количество букетов, теперь вопрос: Учитывать ли букеты состоящие из чётного количества цветков?
Stv
Цитата(MaXiMiliaN @ 29.9.2011, 20:51) *
55 задача.

Ниже очень интересный комментарий в задаче, что 0 - это не букет...с этим всё ясно, думаю что и 1 цветок тоже не стоит включать в количество букетов, теперь вопрос: Учитывать ли букеты состоящие из чётного количества цветков?


почему бы и нет. тем более, что в некоторых странах, наоборот, принято дарить четное количество цветов)
p.s. комментарий и правда хороший smile.gif
Shvarts_DA
Про цветы. Считаю один цветок и четное число цветков букетом. Частично аргументировал это на семинарах, но, если надо, могу развернуть :-)

Домашнее задание. 89, 90, 95,100,104,123,149,259 (абвгдз)+ остатки задачи про покер.

P.S. Большое спасибо за замеченные опечатки, я их внес к себе, но пока не буду вносить в выложенный текст.
evgeniako
Здравствуйте, Дмитрий Александрович!

Решаю номер 123 в)г)д), ответ не сходится с тем, что указан в конце задачника
Например, пункт в)
6-значные числа, сумма цифр которых равна 2
Это, во- первых, число 200000
Во, вторых, это все числа, состоящие из четырех нулей и двух единиц
Учитывая, что 0 не может стоять на первом месте, получаем шестизначное число, первая цифра которого 1. Вторая единица может стоять на одном из 5 мест
Получается, всего искомых чисел 5+1=6
а в ответе 10
Ошибка в моем решении или в ответах?)
Заранее спасибо
MaXiMiliaN
Цитата(Shvarts_DA @ 1.10.2011, 2:46) *
Про цветы. Считаю один цветок и четное число цветков букетом. Частично аргументировал это на семинарах, но, если надо, могу развернуть :-)


Да, если можно, то интересны Ваши развёрнутые аргументы, я как раз опоздал на ту часть, когда это объяснялось (по медицинским причинам) rolleyes.gif
Dronte
Дмитрий Александрович!
Можно вас попросить выкладывать отдельным файлом задачи которые заданы. Иначе получается очень много распечатывать. Или, например, такой файл: теория+ заданые задачки + задачки со звездочками.

Или выложить исходник (я так полагаю, tex), чтобы те, кто хочет, могли сами выбрать.. Вобщем как-то решить эту проблему. Очень неудобно.
Shvarts_DA
Цитата(MaXiMiliaN @ 2.10.2011, 21:15) *
Да, если можно, то интересны Ваши развёрнутые аргументы, я как раз опоздал на ту часть, когда это объяснялось (по медицинским причинам) rolleyes.gif


Одну розу дарят довольно часто. И некоторые (моя жена точно) предпочитают одну розу пяти гвоздикам :-)
Shvarts_DA
Цитата(Dronte @ 3.10.2011, 23:46) *
Дмитрий Александрович!
Можно вас попросить выкладывать отдельным файлом задачи которые заданы. Иначе получается очень много распечатывать. Или, например, такой файл: теория+ заданые задачки + задачки со звездочками.

Или выложить исходник (я так полагаю, tex), чтобы те, кто хочет, могли сами выбрать.. Вобщем как-то решить эту проблему. Очень неудобно.


Понял. Честно говоря, цель была именно в том, чтобы Вы просмотрели и остальное :-) В любом случае, больше такой проблемы не будет - дальше все листки по темам и небольшие.
lenhens
Добрый вечер, не могли бы Вы объяснить произведение бинарных отношений на матрицах?
ну или посоветовать, где можно почитать про них поподробнее smile.gif

С Уважением, Сотникова Лена

П.С. Будет ли завтра консультация? Можно ли будет на ней уточнить некоторые вопросы по бинарным отношениям?
Shvarts_DA
Цитата(evgeniako @ 1.10.2011, 12:07) *
Решаю номер 123 в)г)д), ответ не сходится с тем, что указан в конце задачника


Виноват, не заметил. У Вас все правильно, уже обсудили на семинаре.
Shvarts_DA
Цитата(lenhens @ 6.10.2011, 22:11) *
Добрый вечер, не могли бы Вы объяснить произведение бинарных отношений на матрицах?


Виноват, в пт уже лег спать. А про произведение бинарных отношений мы знать не должны :-) Если серьезно, то на матрицах пока лучше произведение не изучать. По плану мы вернемся к этому месяца через полтора.
Shvarts_DA
С некоторым запозданием выкладываю домашнее задание. Из задачника по комбинаторике нас интересуют задачи

187, 197, 206, 215, 221, 222, 233, 236, 244.

P.S. Хочу извиниться, я оговорился на одном из семинаров, сказав, что оценка за первую контрольную влияет на зачет. На самом деле зачет - это в точности оценка за 2-ю контрольную + бонусы. Но я посмотрел архив за последние 2 года - никто из получивших 8 на 1-й контрольной не получал меньше 8 за зачет. Так что статистически я был прав :-)

Shvarts_DA
Добавил в задачник задачи по общей алгебре. (94-116). Решайте и спрашивайте. Жду вопросов.
Dronte
Что-то странное написано в ответах к 236 номеру.
Afrikanets
Дошел до 100 и что такое?
Разве нам не понадобится бинарная операция для определения групп?
AnnRibkina
А можно ли будет пользоваться учебными материалами на контрольной?
Pharellka
Влияют ли результаты 1ой контрольной на экзамен? То,что на зачёт не влияют, я уже понял.=)
MaXiMiliaN
Цитата(AnnRibkina @ 18.10.2011, 21:36) *
А можно ли будет пользоваться учебными материалами на контрольной?

Можно библиотечными книгами пользоваться и тем что записывали на лекциях и семинарах. Ни каких гаджетов - даже чёрно-белых без 3G и вафли.

Цитата(Pharellka @ 19.10.2011, 13:12) *
Влияют ли результаты 1ой контрольной на экзамен? То,что на зачёт не влияют, я уже понял.=)

Читай в первом посте - оценка за экзамен это средняя арифметическая за все контрольные) не придешь на первую - то максимум сможешь 7,5 получить за экзамен! это при условии что все остальные будут на десятки. в общем четыре контрольных будет у каждой коэффициент 0,25.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2018 IPS, Inc.