Kombinatorika
Lekcijas
1. lekcija (13. februārī).
2. lekcija (20. februārī).
3. lekcija (27. februārī).
4. lekcija (13. martā).
5. lekcija (20. martā).
6. lekcija (27. martā).
7. lekcija (3. aprīlī).
9. lekcija (24. aprīlī).
11. lekcija (15. maijā).
13. lekcija (29. maijā).
Mājas darbi
1. mājas darbs (nodošanas termiņš 2003. gada
13. marts).
2. mājas darbs (nodošanas termiņš 2003. gada
3. aprīlis).
3. mājas darbs (nodošanas termiņš 2003. gada
24. aprīlis).
4. mājas darbs (nodošanas termiņš 2003. gada
26. jūnijs).
Rezultāti.
Ja mājas darbs nav nodots laikā, tajā savāktie punkti tiek dalīti ar
divi.
Mājas darbu teksti pieejami PostScript formātā. Freeware PostScript
failu pārlūks GhostScript/GhostView pieejams šeit.
Kursa plāns
1. Kas ir kombinatorika? Pārskaitošā kombinatorika. Skaitīšanas
rezultāts.
2. Kombinatorisks un nekombinatorisks pierādījums. Veidotājfunkcijas.
3. Kopas un multikopas. Izlases. Variācijas, permutācijas.
4. Kombinācijas. Binomiālie koeficienti.
5. Skaitļa sadalījumi un kombinācijas ar atkārtojumiem.
6. Multikopas permutācijas. Multinomiālie koeficienti.
7. Substitūcijas. Transpozīcijas. Sadalījums transpozīcijās.
8. Cikli. Sadalījums ciklos.
9. Pirmā veida Stirlinga skaitļi.
10. Inversijas. Kritumi. Eilera polinoms. Eilera skaitļi.
11. Substitūciju attēlošana koka veidā.
12. q-multinomiālie koeficienti.
13. Skaitļa saskaldījumi.
14. Kopas saskaldījumi. Otrā veida Stirlinga skaitļi.
15. Sieta metode.
16. Latīņu kvadrāti.
17. Blokshēmas.
18. Transversāļi. Varbūtisko automātu dekompozīcija. Permanenti.
19. Grafu skaitīšana. Ramseja teorēma.
20. Poijā teorēma.
Konsultācijas un eksāmeni
Noapaļots 4 labāko mājas darbu un konspekta atzīmju vidējais
aritmētiskais dod automātisko atzīmi. Ja tā neapmierina, jāliek
eksāmens. Eksāmenā atrisināts uzdevums uzlabo atzīmi
par 0,5, neatrisināts - samazina par 0,5. Var risināt 2, 4 vai 6
uzdevumus,
pēc studenta izvēles.
Konsultāciju un eksāmenu laiki:
11.06.2003. 16.30
konsultācija Antonijas 8-8
12.06.2003. 9.00
eksāmens 12.aud.
18.06.2003. 16.30
konsultācija Antonijas 8-8
19.06.2003. 9.00
eksāmens 12.aud.
25.06.2003. 16.30
konsultācija Antonijas 8-8
26.06.2003. 9.00
eksāmens 12.aud.
Literatūra
Pamatliteratūra
1. Р. Стенли. Перечислительная комбинаторика.
Москва, Мир, 1990. (Angliski: Richard P. Stanley. Enumerative
Combinatorics. Wadsworth, 1986.)
2. Indulis Strazdiņš. Diskrētā matemātika. Rīga, Zvaigzne ABC, 2001.
(3. nodaļa: Kombinatorika un grafu teorija.)
3. Ф. А. Новиков. Дискретная математика. Санкт-Петербург, Питер, 2001.
(Глава 5: Комбинаторика.)
4. В. Н. Сачков. Комбинаторные методы дискретной математики. Москва,
Наука, 1977.
5. М. Холл. Комбинаторика. Москва, Мир, 1970. (Angliski: Marshall Hall,
Jr. Combinatorial Theory. Waltham (Massachusetts), Blaisdell
Publishing, 1967.)
Papildliteratūra
6. A. Andžāns, P. Zariņš. Matemātiskās indukcijas metode un varbūtību
teorijas elementi. Rīga, Zvaigzne, 1983. (3. nodaļa: Kombinatorika.)
7. Agnis Andžāns, Jānis Čakste, Tomass Larfelds, Līga Ramāna, Mārīte
Seile. Vidējās vērtības metode. Rīga, Mācību grāmata, 1996.
8. A. Gailītis, A. Andžāns. Kārtošanas un meklēšanas uzdevumi.
Aizkraukle, Krauklītis, 1995.
9. Я. Гульден, Д. Джексон. Перечислительная комбинаторика. Москва,
Наука, 1990. (Angliski: I. P. Goulden and D. M. Jackson. Combinatorial
Enumeration. New York, Wiley-Inrescience, 1983.)
10. А. Кофман. Введение в прикладную комбинаторику. Москва, Наука,
1975.
11. Дж. Риордан. Введение в комбинаторный анализ. Москва, Издательство
иностранной литературы, 1963. (Angliski: John Riordan. An Introduction
to Combinatorial Analysis. New York, John Wiley & Sons, 1958.)
12. Г. Эндрюс. Теория разбиений. Москва, Наука, 1982. (Angliski: George
E. Andrews. The Theory of Partitions. London, Addison-Wesley, 1976.)
13. Прикладная комбинаторная математика, под редакцией Э. Беккенбаха.
Москва, Мир, 1968. (Angliski: Applied Combinatorial Mathematics, Edwin
E. Beckenbach, editor. New York, John Wiley
and Sons, 1964.)
14. М. Н. Аршинов, Л. Е. Садовский. Коды и математика. Библиотечка
Квант, выпуск 30. Москва, Наука, 1983.
15. Р. Басакер, Т. Саати. Конечные графы и сети. Москва, Наука, 1974.
(Angliski: Robert G. Busacker & Thomas L.
Saaty. Finite Graphs and Networks: An Introduction with Applications.
New York, McGraw-Hill.)
16. Р. Грэхем. Начала теории Рамсея. Москва, Мир, 1984. (Angliski:
Ronald L. Graham. Rudiments of Ramsey Theory. Providence (Rhode
Island), American Mathematical Society, 1981.)
17. О. А. Иванов. Избранные главы элементарной
математики. Санкт-Петербург, Издательство С.-Петербургского
университета,
1995.
18. А. Н. Колмогоров, И. Г. Журбенко, А. В. Прохоров. Введение в теорию
вероятностей. Библиотечка Квант, выпуск 23. Москва, Наука, 1982.
19. В. А. Садовничий, А. А. Григорьян, С. В. Конягин. Задачи
студенческих математических олимпиад. Москва, Издательство Московского
университета, 1987.
20. В. А. Успенский. Треугольник Паскаля. Москва, Наука, 1979.
21. Д. О. Шклярский, Н. Н. Ченцов, И. М. Яглом. Геометрические оценки и
задачи из комбинаторной геометрии. Москва, Наука, 1974.
22. М. К. Чирков. Основы общей теории конечных
автоматов. Ленинград, Издательство Ленинградского университета,
1975.
23. А. М. Яглом и И. М. Яглом. Неэлементарные задачи в элементарном
изложении. Москва, Государственное издательство
технико-теоретической литературы, 1954.
Saites
Visas šīs lapas ir angļu valodā:
Kombinatorika
(definīcija)
Kombinatorika
(definīcija)
Kombinatorikas mājaslapa
Kombinatorikas
uzdevumu krātuve
Ramseja spēle
Ja zināt vēl kādas kombinatorikas lapas, īpaši
latviešu valodā, lūdzu, atsūtiet man par to ziņu (juris punkts smotrovs
et sets punkts lv).