The George Washington University

Department of Mathematics

Math 272: Algorithms and Mathematics

Fall 2007

Tu,Th 12:45–2:00 p.m.

Monroe Hall 450

Mathematics Department

Monroe Hall (2115 G Street), Room 240

Tel: (202) 994–6235, Fax: (202) 994–6760

Professor

Valentina Harizanov

http://home.gwu.edu/~harizanv/

Office: Government Hall, Room 220

Tel: (202) 994–6595

E-mail: harizanv@gwu.edu

Office Hours

Tu 11:00a.m.–12:00 noon

Th 8:30–9:30 a.m.

At other times by appointment.

Description

We will apply concepts and methods of mathematical logic to study complexity and randomness, as well as model-theoretic and computability-theoretic phenomena on various mathematical structures. Topics will include algorithmic proof of Gödel incompleteness theorem, Kolmogorov complexity and algorithmic randomness, compactness, algorithmic problems on partially ordered sets, groups, fields, and algebraic structures in general. Other topics of particular interest to students in the class may be added.

Required background

Mathematical maturity, and one of Math 101/102/103 or consent of the instructor. Math 272 can be taken for credit repeatedly. Advanced undergraduate students may also take this course for credit.

Textbook

Reading material from various sources will be provided in class.

Grading

Class participation, take-home assignments and their presentation.