Iv. Дискретная математика



Скачать 240.56 Kb.
страница1/2
Дата08.11.2012
Размер240.56 Kb.
ТипДокументы
  1   2

-

Раздел IV. Дискретная математика
Содержание программы по разделу дискретная математика


  1. Преамбула

  2. Подраздел IV.1. Комбинаторика.

Темы:

IV.1.1. Теоремы существования: чередование, принцип Дирихле.

IV.1.2. Элементы комбинаторики.

Подтемы (основные понятия и методы комбинаторики):

Основные понятия и методы комбинаторики.

IV.1.2.1. Классические задачи комбинаторики.

IV.1.2.2. Применение арифметических операций в комбинаторике.

IV.1.2.3. Технический прием вычисление вариантов – “шары и перегородки”.

IV.1.2.4. Формула «включений и исключений».

IV.1.2.5. Применение формула «включений и исключений».

IV.1.2.6. Алгебраические методы в комбинаторике

IV.1.2.7. Комбинаторные тождества

IV.1.2.8. Геометрические методы в комбинаторике

IV.1.2.9. Примечательные числа комбинаторики


  1. Подраздел IV.2. Игры

Темы:

IV.1.1. Детерминированые игры. Игры на симметрию. Выигрышные позиции.

IV.1.2. Игры и система счиления.

IV.1.3. Логические игры.

IV.1.4. Математические головоломки

IV.1.5. Турниры.

IV.1.6. Элементы дифференцируемых игр.


  1. Подраздел IV.3. Логические этюды

Темы:

IV.3.1. Логические задачи.

IV.3.2. Переправы, взвешивание, переливание, дележ, конструкции.

IV.3.3. Занимательные задачи, ребусы, головоломки, логические игры.


  1. Подраздел IV.4. Графы

Темы:

IV.4.1. Основные понятия, свойства и операции над графами

IV.4.2. Связные, плоские графы

IV.4.3. Раскраски и графы

IV.4.4. Ориентированные графы

IV.4.5. Экстремальные графы

IV.4.6. Задачи, решаемые с помощью графов

IV.4.7. Группы и их графы


  1. Подраздел IV.5. Вычислительная математика и алгоритмы

  2. Подраздел IV.6. Математическая логика и нормальные дизъюнктивные формы


Преамбула
Дискретная математика область математики, занимающаяся изучением свойств структур конечного характера, которые возникают как в самой математике, так и в области ее приложений. К числу таких конечных структур могут быть отнесены, например, некоторые алгебраические системы, конечные группы, графы, комбинаторика, некоторые метаматематические модели преобразователей дискретной информации, такие как конечные автоматы, машины Тьюринга и др.
, а также некоторые виды вычислительных сред (например, однородные структуры) и т. п. К числу таких структур могут быть отнесены некоторые виды вычислительных сред.

В отличие от дискретной математики классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь, и, в связи с этим, какую модель изучаемого явления он рассматривает — дискретную или непрерывную. Само деление математики на классическую и дискретную в значительной мере условно, поскольку, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой часто возникает необходимость исследования моделей, обладающих одновременно как дискретными и, так и непрерывными свойствами. Кроме того, в математике существуют подразделы, использующие средства дискретной математики для изучения непрерывных моделей, и, наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур. Это указывает на известное слияние рассматриваемых областей.

Дискретная математика представляет собой важное направление в математике, имеющее характерные для неё предмет исследования, методы и задачи, специфика которых обусловлена, в первую очередь, необходимостью отказа от основополагающих понятий классической математики — предела и непрерывности — и (в связи с этим) тем, что для многих задач дискретной математики сильные средства классической математики оказываются, как правило, мало приемлемыми. Наряду с выделением дискретной математики путем указания его предмета, методов и задач можно также охарактеризовать дискретную математику посредством перечисления подразделов, составляющих её. К ним, в первую очередь, относятся комбинаторный анализ, теория графов, теория кодирования и декодирования, теория функциональных систем и некоторые другие.

Здесь необходимо отметить, что за счет расширения понимания в её круг вопросов возможно и причисление и других разделов математики, так например, математическая логика, теория чисел, алгебра, вычислительная математика, дискретная геометрия и теория вероятностей и многие другие разделы математики, в которых изучаемый объект носит дискретный характер.

Элементы дискретной математики возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел, приведшие затем к созданию теории чисел. Позже, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии возникли важнейшие понятия алгебры такие, как группа, поле, кольцо и др., определившие развитие и содержание алгебры на много лет вперед и имевшие по существу дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики логики — привели к выделению еще одного важного раздела математики — метаматематической логики. Однако наибольшего развития дискретная математика достигла в связи с появлением кибернетики и ее теоретической части математической кибернетики. Математическая кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практика, является важным поставщиком идей и задач для дискретной математики вызывая в ней целые новые направления. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление мощных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий вычислимости и алгоритма привел к появлению важного раздела математической логики – теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем и т. д. В то же время математическая кибернетика использует результаты дискретной математики при решении своих задач.

Наряду с отмеченными, дискретная математика обладает рядом и других особенностей. Так, вместе с задачами типа существования, имеющими общематематический характер, важное место в дискретной математике занимают задачи, связанные с алгоритмической разрешимостью и построением конкретных решающих алгоритмов, что характерно именно для дискретной математики. Особенностью дискретной математики является и то, что она по существу первая столкнулась с необходимостью глубокого исследования так называемых дискретных многоэкстремальных задач, часто возникающих в математической кибернетике. Соответствующие методы классической математики для поиска экстремумов, существенно использующие гладкость функций, в этих случаях оказываются мало эффективными. Типичными задачами такого рода в дискретной математике являются, например, задачи об отыскании в некотором смысле оптимальных стратегий в шахматной партии при ограниченном числе ходов, поиск выигрышной стратегии (см. тему: «IV.1.1. Детерминированые игры. Игры на симметрию. Выигрышные позиции» подраздела «IV.2. Игры» данного раздела, а также важный вопрос математической кибернетики о построении минимальных дизъюнктивных нормальных форм для булевых функций, т. е. так называемая проблема минимизации булевых функций. Особенностью дискретной математики, связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классической математике полное решение задачи часто возможно лишь при весьма жестких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа «полного перебора». К числу задач указанного вида можно отнести, например, упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Вместе с тем, решения типа «полного перебора» очень трудоемки и практически мало приемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи наложения ограничений на средства решения, естественных для этого класса задач, и др. IIостановка такого рода вопросов и разработка методик осуществляется на конкретных моделях, доставляемых различными разделами математики, например, на моделях минимизации булевых функций и синтеза управляющих систем из математической кибернетики.

Так как раздел «Дискретная математика» предназначен в первую очередь для школьников и учителей, а также неравнодушных и заинтересованных в формировании математического образа мышления у подрастающего поколения, то в этот раздел включены следующие подразделы и темы (см. содержание). Критерием отбора материала служило прежде всего воспитание математической культуры и исследовательских качеств. Также стороной не была обойдена олимпиадная математика. Так, например, многие темы олимпиадной математики как принцип Дирихле, метод раскраски и другие, зачастую многими воспринимаются как методы решения развлекательных задач, мало имеющие отношение к серьезной математике и никак не претендующие на то, чтобы посредством их можно было дать серьезное математическое образование. Вследствие чего эти темы были включены в тему: «Теоремы существования» подраздела «Комбинаторика», а теоремы существования это один из фундаментальных способов математического доказательства (рассуждения), как закон исключенного третьего, благодаря которому в математике используется метод доказательства от противного.

К каждой теме по возможности дается подробный список литературы с указанием глав, параграфов.

Подраздел IV.1. Комбинаторика.
Темы:

IV.1.1. Теоремы существования:
Подтемы:

IV.1.1.1. Четность: чередование, разбиение на пары, четность и нечетность

Литература:

  1. Шарыгин И. Ф., Шевкин А. В. Задачи на смекалку. Учебное пособие для 5-6 классов общеобразовательных учреждений. М: Просвещение, 2003. – 95 с. (2. Четность. С.19-24)

  2. Генкин С. А., Итенберг И. В., Фомин Д. В. Ленинградские математические кружки. Киров: АСА, 1994. – 272 с. (Глава 2. Четность. С. 12 – 16. Задачи № 1 – 32).

  3. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002.318 с. (Занятие 6. Четность. С. 59 – 70; Занятие 7: Аналоги четности: чередование, разбиение на пары. С. 71 – 80. Задачи на стр.77 – 78)

  4. Спивак А. В. Тысяча и одна задача по математике. М.: Просвещение, 2002. – 207 с. [§45. Четность. Задачи № 434 – 450. §46. Чередование. Задачи № 452 – 460. §47. Разбиение на пары. Задачи № 461 – 469. С.68 – 75]

  5. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (§4.1. Четность. Задачи № 4.1 – 22. С. 62 – 65).

  6. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с. [Задачи № 57 – 71. С. 41 – 46 ].

  7. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М:МЦНМО, 2001. – 96 с. [Задачи № 2 – 3, 6, 10. С.14 – 15 ]

  8. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Четность”).

  9. Сайт: www.mccme.problems.ru  

  10. Сайт: www.mccme.ru


IV.1.1. 2. Принцип Дирихле. Принцип Дирихле для остатков. Принцип Дирихле для длин, углов и площадей

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. (Принцип Дирихле. Задачи № 1 – 34. С. 39 – 46).

  2. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с. (Глава III. Принцип Дирихле. Задачи № 167 – 205. С.104 – 124).

  3. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002. – 318 с. (Принцип Дирихле. С.147-160)

  4. Бабинская И. Л.. Задачи математических олимпиад. М.: Наука, 1975. – 112 с. (Глава 1. §3. Принцип Дирихле (Задачи № 106 – 128. С.16-18).

  5. Леман А. А.. Сборник задач московских математических олимпиад. Под ред. В. Г. Болтянского. М.: Просвещение, 1965.

  6. Муштари Д. X.. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990. – 239 с. (Теоремы существования.§23. Принцип Дирихле. Задачи № 170 – 193. §24. Принцип Дирихле для остатков. Задачи № 185 – 189. §25. Принцип Дирихле для длин и площадей. Задачи № 190 – 193.)

  7. Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997

  8. Фоминых Ю. Ф.. Принцип Дирихле. // Ж-л «Математика в школе», 1996, No3.

  9. Шарыгин И. Ф., Шевкин А. В. Задачи на смекалку. М: Просвещение, 2003. – 95 с. (9. Принцип Дирихле. С. 51 – 5 2).

  10. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Принцип Дирихле”)

  11. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (§2.2. Принцип Дирихле. Задачи № 2.17 – 38. С. 17 – 19)

  12. Энциклопедия для детей. Т11. Математика. М:Аванта+,2002. – 688 с. (Принцип Дирихле. С.564)


IV.1.1.3. Принцип максимума (минимума)

Литература:

  1. Муштари Д. X.. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990. – 239 с. (Теоремы существования. §26. Принцип максимума (минимума). Задачи № 194 – 205)

  2. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Принцип крайнего”)

  3. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М:МЦНМО, 2001. – 96 с. [Метод крайнего. Примеры 1 – 5. С. 32 – 33. Задачи № 1 – 13. С. 33 – 34]


IV.1.1.4. Метод раскраски.

Литература:

  1. Дынкин Е. Б., Успенский В. А. Математические беседы. Москва · Ижевск: РХД, 2002. – 260 с. (Раздел I. Задачи о многоцветной раскраске. С. 9 – 42)

  2. Гантмахер Г., Теплиц О. Числа и фигуры. Ижевск: Ижевская республиканская типография, 200. – 254 с. 13. Проблема четырех красок. С. 92 – 102 (Излагается другой подход к этой проблеме, чем в [1])

  3. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  4. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Раскраски”)

  5. Спивак А. В. Тысяча и одна задача по математике. М: Просвещение, 2002. – 207 с.

  6. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с.

  7. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М.: МЦНМО, 2001. – 96 с.

  8. Мительман И. М. Раскрасим клетчатую доску. Ижевск: Издательский дом «Удмуртский университет»,2002. – 56 с.


IV.1.2. Элементы комбинаторики: основные понятия и методы комбинаторики

Подтемы:

IV.1.2.1. Классические задачи комбинаторики.

Литература:

  1. Математическая энциклопедия: Гл.редактор И. М. Виноградов,т.2 Д – Коо – М.: «Советская энциклопедия»,1979. – 1104 стб.,ил. (ст.»Комбинаторные задачи». С.971 – 974).

  2. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с.(Из предисловия автора. С.5 – 8. Глава 1. Перестановки и сочетания. С.9 – 28. Глава 2. Производящие функции. С.29 – 62)


IV.1.2.2. Применение арифметических операций в комбинаторике.

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. (Комбиниторика-1. С. 17 – 25.Комбиниторика-2. С.123 – 139)

  2. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики (16 задач). Глава II. Размещения , перестановки и сочетания (17 задачи))

  3. Шафаревич И. Р. Избранные главы алгебры: учебное пособие для школьников. М: Журнал «Математическое образование», 2000. – 380 с. (Глава 3. Конечные множества (Тема: Множество). §8. Комбинаторика. С. 103 – 120)

  4. Спивак А. В. Тысяча и одна задача по математике. М: Просвещение, 2002. – 207 с. (72. Комбинаторика. С. 117 – 129).

  5. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [Задачи №2.2 – 11, 1.40. С.16 – 17. Задачи №2.42 – 2.52. С.20 – 21, Задачи №2.57 – 2.70. С.22 – 23].

  6. Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I: Задачи по комбинаторике и теории вероятностей. §I.1. Вводные задачи (1 – 10)).

  7. Холл М. Комбинаторика. М.: Мир, 1970. – 424 с. (Глава 1. Перестановки и сочетания. С.9 – 17).


IV.1.2.3. Технический прием вычисление вариантов – “шары и перегородки”.

Литература:

    1. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002. – 318 с. (Занятие 4. Комбинаторика. С. 33 – 48)

    2. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. [Глава комбинаторика-2. §3. Шары и перегородки. С. 134 – 136].

    3. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [Задачи №2.13 – 14, 1.40. С.17. Задачи №2.2.71 – 2.75. С.23 – 24.].

    4. Яглом А. М., Яглом И. М.Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I: Задачи по комбинаторике и теории вероятностей. §I.2. Разложение чисел в произведение сомножителей и на сумму слагаемых (11 – 31)).

    5. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава IV. Комбинаторика разбиений (22 задачи)).

    6. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (Глава 3. Производящие функции и рекуррентные соотношения. С.33 – 44. Глава 4. Разбиения. С.45 – 64).

    7. Эндрюс Г. Теория разбиения. М.: Наука, 1982. – 256 с. (О методах разбиения натурального числа)


IV.1.2.4. Формула «включений и исключений».

Литература:

  1. Колосов В. А. Теоремы и задачи алгебры, теории чисел и комбинаторики. М: «Гелиос АРВ», 2001. – 256 с. (§2.4. Формула «включений и исключений». С.39 – 44.).

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [§2.4. Формула «включений и исключений». С.28 – 30.Задачи №2.109. С.29].

  3. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (§2.1. Принцип включения и исключения. Обращение Мёбиуса. С.10 – 26).

  4. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с. (Глава 3. Принцип включения и исключения. 1. Введение, с. 63. 2. Логическое тождество, с. 62 – 76. 3. Символическое обобщение. 66 – 70. 4. Ранг, с. 70 – 71)

  5. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Глава третья. Логические методы. § 3.1. Метод включения и исключения, 77 – 85)


IV.1.2.5. Применение формула «включений и исключений».

Литература:

  1. Колосов В. А. Теоремы и задачи алгебры, теории чисел и комбинаторики. М: «Гелиос АРВ», 2001. – 256 с. (§2.4. Формула «включений и исключений». С.39 – 44)

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [§2.4. Формула «включений и исключений». С.28 – 30.Задачи №2.101 – 116. С.28 – 30].

  3. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (§11. Метод включений и исключений. С.49 – 63).

  4. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с. (Глава 3. Принцип включения и исключения. 5. Задача о встречах, с. 71 – 76)

  5. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Глава третья. Логические методы. § 3.1. Метод включения и исключения, 77 – 85. § 3.2. системы представлений множеств, с. 85 – 92. § 3.3. Теорема Рамсея, с. 92 – 97)


IV.1.2.6. Алгебраические методы в комбинаторике: методы рекуррентных соотношений, многочленов, производящих функций

Литература:

    1. Шафаревич И. Р. Избранные главы алгебры: учебное пособие для школьников. М: Журнал «Математическое образование», 2000. – 380 с. (Глава 7.Степенные ряды (Тема: Многочлен). §21. Многочлены как производящие функции. §22. Степенные ряды. §23. Partitio numerous (разбиение чисел). Приложение 1. Пентагональная теорема Эйлера. Приложение 2. Производящие функции для чисел Бернулли. С. 311 – 385)

    2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (11. Последовательности и ряды. 11.2. Рекуррентные последовательности. С. 185 – 192. 11.3. Ароизводящие функции. С. 192 – 198)

    3. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики (Глава VI. Рекуррентные соотношения.С. 154 – 181. Глава VII. Комбинаторика и ряды. С. 182 – 218).

    4. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (§9. Метод рекуррентных соотношений. С. 46 – 47. §10. Метод производящих функций. С. 47 – 59).

    5. Кохась К. П. Ладейные числа и многочлены. М.: МЦНМО, 2003. – 20 с. (Биб-ка «Математическое просвещение». Вып. 26)

    6. Ландо С. К. Лекции о производящих функциях. М.: МЦНМО, 2002. – 144 с.

    7. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (Глава 3. Производящие функции и рекуррентные соотношения. С. 33 – 44).

    8. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с.

    9. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с.

    10. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с. (1 Возвратные задачи. С. 17 – 386 Специальные числа. 7 Производящие функции. 7.3 Решение рекуррентных сотношений. С. 287 – 517. )


IV.1.2.7. Комбинаторные тождества

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. – 2 72 с.

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  3. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики

  4. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (Метод траекторий)

  5. Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I. Задачи по комбинаторике и теории вероятностей.5. Задачи на биномиальные коэффициенты. Задачи № 55 – 61)

  6. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с.

  7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с. (5 Биномиальные коэффициенты. С. 178 – 286)

  8. Риордан Дж. Комбинаторные тождества. М.: Наука,1982. – 226 с.


IV.1.2.8. Геометрические методы в комбинаторике

Литература:

  1. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  2. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики

  3. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (Метод траекторий)

  4. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Геометрические методы в комбинаторике)


IV.1.2.9. Примечательные числа комбинаторики. Биномиальные коэффициенты. Числа Фибоначчи, Бернулли, Каталана, Люка, Стирлинга.

Литература:

  1. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (см. предметный указатель)

  2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с.

  3. Доценко В. Числа Каталана и естественные отображения. С.180 – 212. // Задачи Санкт-Петербургской олимпиады по математике. Спб: Санкт-Петербургский государственный университет. – 2003.


  1   2

Похожие:

Iv. Дискретная математика iconДискретная математика
Ф50 Дискретная математика: сборник задач / Сост. И. В. Тимофеев. Красноярск: ипц кгту, 2003. 35 с
Iv. Дискретная математика iconС. Б. Дискретная математика. Изд-во мгту им. Н. Э. Баумана, 2004. Бородин О. В. Дискретная математика: Учебное Пособие
Белоусов А. И., Ткачев С. Б. Дискретная математика. Изд-во мгту им. Н. Э. Баумана, 2004
Iv. Дискретная математика iconПрограмма дисциплины «Дискретная математика»
...
Iv. Дискретная математика iconРабочей программы дисциплины дискретная математика
Дискретная математика и математическая логика входят в цикл профессиональных дисциплин в базовой части. Для их успешного изучения...
Iv. Дискретная математика iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Iv. Дискретная математика iconУчебная программа Дисциплины б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Iv. Дискретная математика iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Iv. Дискретная математика iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Iv. Дискретная математика iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Iv. Дискретная математика iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org