Faculty of Information Technology, BUT

Course details

Algebra, Combinatorics and Graphs

QM3 Acad. year 2007/2008 Winter semester

Universal algebras. Vatieties. Categories of classes of algebras. Special binary systems more general than groups. Chapters from group theory, rings and skew-fields. Finite fields and polynomials over fields. Lattices and theory of varieties. Representative selected parts of Combinatorial analysis and Graph theory: Counting, recurrence relations, exclusion-inclusion, transversals of systems of sets, traveling in multigraphs, planarity and colourings, sequences of degrees of vertices and of couples of halfdegrees of vertices, isomorphism problem, selected matrix methods.

Guarantor

Language of instruction

Czech

Completion

Examination (oral)

Time span

39 hrs lectures

Assessment points

Department

Lecturer

Subject specific learning outcomes and competences

Enlarging of the knowledges in General Algebra, Combinatorial Analysis and Graph Theory and thus to be better equipped for the study of special disciplines of Computer Science.

Learning objectives

To recall and make deeper the lower level knowledges from algebra and discrete mathematics. To obtain ability of applying of algebraic reasoning in informatics.

Prerequisite kwnowledge and skills

Rudiments of theoretical computer science.

Study literature

  • Lecture notes of the lecturer (mimeographed).
  • Bang-Jensen Gutin, Digraphs, London-Berlin-Heidelberg, 2000, inv.č. 5141.
  • Buchmann, Introduction to Cryptography, New York-Berlin-Heidelberg, 2000, inv.č. 5316.
  • J.A.Bondy-U.S.R.Murty:Graph Theory with Applications,North-Holland,New York-Amsterdam-Oxford, 1986

Fundamental literature

  • Skornyakoff, Elements of general algebra, Nauka, Moscow, 1983, in Russian.
  • McKenzie-McNulty-Taylor, Algebras, lattices, varieties I, Wadsworth-Brooks/Cole Monterey, California. 1987.
  • Mitchell, Theory of categories, Academic Press, New York. 1965.
  • Rosen, Discrete mathematics and its applications, The Random House, New York, 1965.
  • Balakrihnan-Ranganathan, A textbook of graph theory, Springer, New York-Berlin-Heidelberg, 2000.

Syllabus of lectures

  1. General approach to algebras: theory of universal algebras, varieties, theorem of Birkhoff. Multisorted (heterogeneous) algebras.
  2. Theory of categories and classes of algebras. Brandt groupoids.
  3. Halfgroupoids and groupoids, cancellation groupoids, quasigroups, loops, semigroups, monoids. Comparison from point of view of congruence relations. 3-sorted quasigroups (and automata).
  4. Selected chapter from general group theory.
  5. Selected chapter from general ring theory.
  6. Embedding of a semigroup into a group and of a ring into a field.Adjunctions for skew-fields. Finite fields: construction, existence, automorphisms. To algebraic cryptography.
  7. Ideals in lattices and factorization. Lattices and mathematical logic. How lattice theory contributes to the study of varieties.
  8. Combinatorics I: Dirichlet principle. Lexicographic orderings. Recurrence relations (problem of Fibonacci, principle of "divide-and-conquer").
  9. Combinatorics II: Applications of exclusion-inclusion principle and of P. Hall's theorem on mutually distinct representatives. Tfe famous algorithm of Marshall Hall, Jr. leading to systems of mutually distinct representatives.
  10. Graphs I: Traveling in multigraphs and multidigraphs. Recent results on eulerian and hamiltonian paths, on planarity and on colouring.
  11. Graphs II: Degree sequences and halfdegree couple sequences. Algorithms of restitution. Systems of unequalities of Erdös-Gallai and of Gale-Ryser. Problem of isomorphism.
  12. Graphs III: Selected matrix methods. Algorithm of Demoucron for levels of accessibility, Warshall' algorithm.

Syllabus - others, projects and individual work of students

  • One seminar work on prescribed accompanying topic.

Progress assessment

Discussion on actual study matter.

Course inclusion in study plans

Back to top