Обсуждение:МФТИ/Кафедра МОУ/Дискретный анализ (семестр 1)

Если вы обнаружили незамеченные опечатки, неточности или ошибки в выложенных материалах, пожалуйста, добавьте сообщения о них в соответствующий раздел в формате:

• <что и где> --<кто и когда>

Семинар 1

Исправления

8.09.2015

• В материале семинара 7, в примере 7.1 получается: z ∼ ('не'1 · 0) = 0 => z = 1, а не 0. --Антонова Нина, 25.10.2014
• в конце 31 начале 32 страницы в предложении <<Но такой таблице истинности удовлетворяют функции, каждая из которых...>> пропущена данная запятая --Андрей Дзись 29 сентября 2014
  • Эта запятая стоит после четвертой формулы. --К.Ч. 21:30, 29 сентября 2014 (UTC)

28.09.2013

• УпражЕнение 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7. --Дмитрий Соловьев 10 декабря 2011
  • Это общая ошибка, вызванная макросом. Была уже отмечена тут. --К.Ч. 23:15, 9 декабря 2011 (UTC)

Семинар 3

• На странице 43 в утверждении 9.5 должно быть "... зависящую от каждой". --Иван Саюшев 01 ноября 2011
  • Совсем не обязательно. То, что написано, следует из предыдущих утверждений. --К.Ч. 10:58, 7 декабря 2011 (UTC)
• Там же: запятая между "выбрать" и "с какого шага". --Афанасьев Филипп 9 октября 2012
  • Зачем? --К.Ч. 07:56, 16 октября 2012 (UTC)
    • Это сложное предложение. --Афанасьев Филипп 18 октября 2012
      • Согласен. Похоже, пора вспоминать школьную программу :) --К.Ч. 10:52, 25 октября 2012 (UTC)
• Утверждение 9.4: полностью отсутствует его доказательство при наличии слова "Доказательство:". Может быть, так и нужно. --Афанасьев Филипп 9 октября 2012
  • Пока не написал.--К.Ч. 07:56, 16 октября 2012 (UTC)

Исправления

28.09.2013

• В оглавлении 2 раза написано слово "классы". В решении примера 9.2 пропущено слово "сохраняет" между "Функция единицу". --Иван Киселев 29 ноября 2011
• В упражнениях в 9 и 10 семинарах есть ошибка: "упражЕнение" --Рогожин Максим 29 ноября 2011
• 1. Упражнение 9.7, первый пример: надо L заменить на S.
  2. Решение примера 9.3, второй абзац: "хотя бы" (раздельно).
  3. В доказательстве утверждений 9.1 и 9.3: "особенные" неплохо бы заменить на "особые".
  4. Утверждение 9.3: "в каждой точке" вместо "в каждом точке".
  5. Там же: "n способами" вместо "n способом".
  6. Там же: запятая между "выбрать" и "с какого шага".
  7. Там же: в скобках надо убрать "ни".
  8. Утверждение 9.4: полностью отсутствует его доказательство при наличии слова "Доказательство:". Может быть, так и нужно.
  9. Утверждение 9.5: "функцию" вместо "фунцию". И вставить "от" между "зависящую" и "каждой".

  --Афанасьев Филипп 9 октября 2012

29.11.2011

• В доказательстве утверждения 9.5: "самодвойственнх". И в определении 9.1: "конъюнкия". --Иван Киселев 28 ноября 2011
• В доказательстве теоремы 9.1: "конъюнции". Там же вместо "Пусть" написано "Путь". И дальше: "конъюнкия". --Иван Киселев 28 ноября 2011
• В примере 9.1: "фанкции". --Иван Киселев 28 ноября 2011

Семинар 4

Исправления

28.09.2013

• Теоремма 10.1. -...содержалась целиком ни в одном из замкнутых классов (:/,) T0, T1, L, S и M. --Алексей Хацкевич 23 декабря 2012
• УпражЕнение 10.1. --Дмитрий Соловьев 10 декабря 2011
  • Это общая ошибка, вызванная макросом. Была уже отмечена тут. --К.Ч. 23:15, 9 декабря 2011 (UTC)

Семинар 5

Исправления

13.10.2015

• 1. Решение примера 1.6, 4-я строчка: запятая между "ещё один" и "когда".
  2. Условие примера 1.10: "круг висит" вместо "круг весит".
  3. Решение примера 1.10, 2-й пункт: "Рассмотрим размещение. Оно не поменяется..." вместо "Она не поменяется...".

  --Афанасьев Филипп 8 ноября 2012

• Стр 2, после определения верхней и нижней степеней во втором заключении поставить вместо нижней степени n верхнюю. --Авдюхов Дмитрий 27 октября 2013
• Пример 1.7. Ошибка в базе при n = 2. Тогда предположение тоже неверное. Примерное решение:

  Докажем по индукции, что F_{n+2}. Не нарушая общности можно считать, что множество состоит из точек множества N (натуральных чисел), причем, если мощность множества равна n, то оно состоит из чисел от 1 до n. Обозначение пустого множества: "{}"

  База: n = 1: 2 = F_{3} ({}, {1});

  n = 2: 3 = F_{4} ({}, {1}, {2})

  n = 3: 5 = F_{5} ({}, {1}, {2}, {3}, {1,3});

  n = 4: 8 = F_{6} ({}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4})

  и т.д.

  Предположим, что для всех k < n верно. Возможны два несовместных варианта:

  • Подмножество содержит n. Тогда оно не может содержать (n-1), а каждый из оставшихся n-2 элементов содержать может. Таких вариантов, по предположению, F_{n-2+2} = F_{n}. Следует обратить внимание, подмножество не обязано содержать ни одного из оставшихся n-2 элементов.
  • Подмножество не содержит n. Тогда оно может содержать любой из оставшихся n-1 элементов множества, но не обязано. Если оно не содержит ни одного, получаем пустое подмножество. По предположению, таких вариантов F_{n-1+2} = F_{n+1}. По правилу суммы всего вариантов F_{n} + F_{n+1} = F_{n+2}.

  Итак, условие задачи корректно, в частности, не требует добавления "непустых" (подмножеств).

  --Авдюхов Дмитрий 27 октября 2013. 5 ноября 2013 исправлено неверное решение от 27 октября 2013.

• Перед определением 1.5 m в верхней степени n. --К.Ч. 17:42, 18 декабря 2013 (UTC)

27.10.2011

• В примере номер 3.7 "Подмножество сожержит n", видимо есть опечатка. --Дмитрий Банков 3 ноября 2010
• 3.13: "Всего мест меджу объектами..." опечатка. --Дмитрий Банков 3 ноября 2010
• 19 стр. нижняя строка "Втроую" --Борик 3 января 2011
• "Пример 3.2. Найти количество взаимнооднозначных отображений n-элементного множества сОмого в себя." опечатка в слове "самого" --Максим Рогожин 22 сентября 2011

Семинар 6

Исправления

21.10.2015

• в пункте 2.4 в доказательстве нужно поменять местами содержит и не содержит элемент. --Юрий Самарин 08 ноября 2011
• В доказательстве утверждения 2.4 перепутаны местами варианты, когда подмн-во содержит элемент и когда не содержит. --Иван Киселев 19 декабря 2011
• 1. Доказательство утверждения 2.1: запятая между "указать" и "какие".
  2. Доказательство утверждения 2.8: "Каждое из них" вместо "Каждае из них".
  3. Решение примера 2.1, 6-я строчка: "группу" вместо "гуппу".

  --Афанасьев Филипп 9 ноября 2012

• Утверждение 2.5(Комбинаторика). Доказательство, последний абзац: "Подмножество не содержит второй элемент. Тогда нужно выбрать m из оставшихся (n − 1). Возможны два варианта..." Исправленный вариант: "Подмножество не содержит второй элемент. Тогда нужно выбрать m+1(ВМЕСТО m)из оставшихся (n − 1). Возможны два варианта..." --Стёпкин Максим 24 декабря 2012
• в утверждении 2.3. Триномиальный вариант. В обсуждениях исправить не удалось. --Аввакумов Рома 24 декабря 2012

• 1. Утверждение 2.4. Перепутаны случаи (содержит - не содержит), т.е. слова не согласуются с логикой. (Как видно, выше отмечалось.)
  2. Утверждение 2.5. В последнем пункте вместо m должно быть m+1. (Как видно, выше отмечалось.)
  3. Утверждение 2.6. В последнем пункте вместо n должно быть n-2.

  --Дмитрий Авдюхов 27 октября 2013

28.09.2013

• упражЕнение 2.1, 2.2, 2.3, 2.4, 2.5. --Дмитрий Соловьев 10 декабря 2011
  • Это общая ошибка, вызванная макросом. Была уже отмечена тут. --К.Ч. 23:15, 9 декабря 2011 (UTC)

Семинар 7

Найденные ошибки

• В примере 7.4 речь идет о шахматной доске, но вдруг появляются монеты: « Количество способов выбрать моменты, когда были…». -- Ушаков Роман 21 ноября 2015
  • Здесь всё нормально. Имеются в виду моменты пути.--К.Ч. (обсуждение) 05:11, 24 ноября 2015 (MSK)
• «Пакеты акций» не имеют отношения к задаче 7.1 и 5.14: «Задачу можно решить и по-другому. Вспомним результат примера 5.14 (задача о пол- ках). В данном случае пакеты акций станут книгами, а каждый тип — полкой, но…». Задача 7.1 о способах неупорядоченно и без возвращений выбрать набор из 20-ти шариков красного белого или черного цвета. -- Ушаков Роман 21 ноября 2015

Исправления

28.10.2015

• В доказательстве утверждения 5.2: "Каоличество" --Иван Киселев 28 ноября 2011
• В доказательстве утверждения 5.3: вместо "только" написано "тоЧко". Там же вместо "из" написано "их". --Иван Киселев 28 ноября 2011
• В решении примера 5.3 во втором абзаце "дЕлее" и в доказательстве утверждения 5.3 "единственным оДразом" --Маким Рогожин 7 декабря 2011
• В последнем предложении утверждений 5.1, 5.2 и 5.3 нужна запятая: "Суммируя по всем точкам, получаем нужный результат." --Афанасьев Филипп 29 ноября 2012

28.09.2013

• Слова "УпражЕнение" следует поменять на "Упражнение". --Дмитрий Банков 3 ноября 2010
• В упражнении 5.4 в ответе должно быть не 6^3, а 3^6 - Мария Рыскина, 10.12.2010

Семинар 8

Исправления

09.11.2015

• В определении 4.3: вместо "πk − 1(x)" надо написать π^(k-1) (x). --Иван Киселев 24 ноября 2011
• В самом конце темы в рекуррентном соотношении после знака "=" в двух последних слагаемых надо заменить "B(n − 1)" и "B(n)" на "B(n-k)" и "B(0)" соответственно. --Иван Киселев 19 декабря 2011
• В доказательстве утверждения 4.3 потерялось n, и неверная замена индекса суммирования. --Иван Богатов 25 декабря 2012

3.11.2011

• В определении 6.2: "Пусть заданно упорядочнное множесвто...", в последних 2 словах опечатки. --Дмитрий Банков 3 ноября 2010
• В утверждении 6.5: "Каждому элементу Иножества Y соответствует класс его Крообразов...", 2 опечатки. --Дмитрий Банков 3 ноября 2010

Исправления

18.11.2015

• Определение 5.1: вместо слова "пусть" написано "путь"; и в последовательности напечатаны только нижние индексы членов, сами буквы "а" не напечатаны
  • См. запись Вани Киселёва от 28 ноября 2011--К.Ч. 18:37, 5 декабря 2014 (UTC)
• В определении 5.1 вместо слова "пусть" написано "путь". И там же в последовательности написаны только индексы, пропущено "a". --Иван Киселев 28 ноября 2011
• После таблицы 5.1: 2 раза встречается "неКпорядоченных". И в доказательстве утверждения 5.4 два раза написано слово "можно". --Иван Киселев 28 ноября 2011
• 1. После таблицы: 2 раза "раделить" без "з".
  2. Утверждение 5.4, 2-й пункт: "хотябы" нужно написать раздельно.

  --Афанасьев Филипп 29 ноября 2012

• В определении 5.1 под знаком суммы вместо n должно быть k. --Елена Безроднова 22 декабря 2012
• В доказательстве утверждения 5.4 в пункте 1 вместо "(n-1) объектов" написано "(n-1) объект", вместо "(k-1) групп" написано "(k-1) группу". --Алсу Сагирова 24 декабря 2014
• Внизу первой страницы: согласно формуле включений-исключений должно быть 91-0=91. --Иван Саюшев 25 ноября 2011
• Внизу первой страницы опечатка: "Тепрь". --Иван Киселев 28 ноября 2011
• 1. В решении примера 6.1 (4 абзац): "положим в них 21 и 17 шариков..." вместо "положив".
  2. 2 лист, 3 строка: "количество всех объектов".
  3. В самом конце 2-го листа: "Решая её, найдем:" (пропущена запятая).

  --Афанасьев Филипп 07 декабря 2012

• Пример 6.1. Предпоследний абзац "Теперь заметим, что количество случаев...". Ошибка в том, что, если добавляли 4 раза, а вычитали 3 раза, нужно вычесть, а не добавить. Поэтому численное выражение будет 91-0=91.--Дмитрий Авдюхов 15 декабря 2013

28.09.2013

• УпражЕнение 5.1, 5.2 --Соловьев Дмитрий 10 декабря 2011
  • Это общая ошибка, вызванная макросом. Была уже отмечена тут. --К.Ч. 23:15, 9 декабря 2011 (UTC)

Задание 1

• Задание по ФАЛ №1.4 Слово Рузельтат) Макарычев 113 гр
• раздел 1.1 задание 1.2 либо оба истинны, либо оба ложны следует исключить второе оба, так как союз либо либо соединяет однородные сказуемые,а включене второго оба порождает грамматическую ошибку. Дзись А. 412 гр.10.18,2014

  Комментарий редактора издательства Физматкнига:

  "Это было бы верно, если бы было написано "Два утверждения совпадают тогда и только тогда, когда они оба либо истинны, либо ложны". Здесь другое построение фразы."

  --К.Ч. 20:02, 14 ноября 2014 (UTC)

Исправления

28.09.2013

• В задании 2.1 нужна запятая после слова "выяснить". --Дяговченко Дмитрий 23 декабря 2012

10.09.2013

• В задании 1.4 написано "Разложить в дизъюнктивнЦю и конъюнктивную формы. --Поволоцкий Михаил, 19 сентября 2011.

27.10.2011

• в задании 1.4 написано "Рузельтаты" --Саюшев Иван 11 сентября 2011

Задание 2

Найденные ошибки

• замечена неточность, (ошибкой назвать сложно). Условие задачи 2.4 трактуется двусмысленно:

1. n парней n девушек ВКЛЮЧАЯ Машу и Сашу. 2. ИСКЛЮЧАЯ молодоженов. Предложение по исправлению: было всего n юношей ..... или же всего гостей было n юношей .... --Дзись А.И 412 гр

• опечатка в задаче 2.8: "треуголники" --> "треугольники".

Ушаков Р. 513 гр

• замечена неточность в формулировке задачи 2.7, приводящая к неверному ответу. Нечетные слагаемые должны быть ПОЛОЖИТЕЛЬНЫМИ. В противном случае возможно бескончное количество представлений числа в виде суммы положительных и отрицательных нечетных слагаемых.

Предложение по исправлению "как упорядоченный набор положительных нечётных слагаемых" Николай Гайдученко, 513 группа

• ошибка в ответе к задаче 2.13 б). ответ 6048 --> 20412. Галайда А. 519 гр 6.11.15

• А нет ли в ответе 2.13б) ошибки? Итого 20412. А в ответе 6048. В задании №2 по комбинаторике ошибка в номере 2.14 вместо «подобный» должно быть «подобных». Исхаков Ришат, 513 группа.

• В 2.22 написано "состоялись n боев". Нужно исправить на "состоялось". Исхаков Р. 513 гр.
  • Почему? --К.Ч. (обсуждение) 21:43, 18 ноября 2015 (MSK)

Исправления

20.11.2013

• Задача мАжордома - не критично, но глаз режет --Андрей Глебов 10 ноября 2011
• Задание 2.16. N=(m) исправить на N(m) --Рогожин Максим 11 ноября 2011
  • На самом деле, нужно $N_=(m)$ умножить на число сочетаний из n по m. Но ты прав, ошибка есть. --К.Ч. 23:21, 21 ноября 2011 (UTC)

====04.12.2015

• в определении 3.2 написано: "k-дольный граф Граф". По-моему, или слово граф лишнее, или не хватает тире, или скобок, как в определении 3.3. Исхаков Р., 513
• Неточность в задании 3.4: неясно, в какую сторону ориентировано ребро графа (в таблице нет знаков). Исхаков Р. 513

Задание 3

14.12.2011

• В задании 4.2 написано:"либо ни один их них не знает других",должно быть "из них".--Андрей Кочетыгов 12 декабря 2011