Geum.ru

Программы и учебный план отделения теоретической и прикладной лингвистики Издательство Московского университета 2009

Вид материалаДокументы
Подобный материал:
1   ...   45   46   47   48   49   50   51   52   ...   55

5. Топология.


5.1. Открытые и замкнутые множества точек на прямой и плоскости. Простейшие свойства открытых и замкнутых множеств.

5.2. Непрерывные отображения. Понятие гомеоморфизма.

5.3. Вполне ограниченные множества. Критерий полной ограниченности.

5.4. Компактные множества на прямой и плоскости. Критерий компактности.

6. Фракталы.


6.1. Метрическая размерность. Вычисление метрической размерности для конечного множества точек, отрезка, квадрата, куба.

6.2. Геометрические фигуры, имеющие дробную метрическую размерность. Вычисление метрической размерности совершенного канторова множества.

6.3. Самоподобные геометрические фигуры. Использование самоподобия для вычисления размерности. Снежинка Коха. Кривая дракона. «Ветвящиеся» фракталы.

6.4. Фракталы в природе. Парадокс длины береговой линии.

6.5. Множество Мандельброта.

литература

Обязательная литература


Александров А. Д., Нецветаев Н. Ю. Геометрия. М., 1990. [С. 11–98, 122–145, 281–316, 324–325, 474–488, 512–517, 643–655.]

Александров А. Д. Основания геометрии. М., 1987. [С. 113–119, 154–159, 178–180.]

Белов В. В., Воробьев В. М., Шаталов В. Е. Теория графов. М., 1976. [С. 9–17, 59–75, 112–138, 143–155, 159–171, 194–199.]

Гарднер М. От мозаик Пенроуза к надежным шифрам. М., 1993. [С. 47–68.]

Зорич В. А. Математический анализ. Ч. 2. М., 1984. [С. 11–28.]

Макаров Б. М., Голузина М. Г., Лодкин А. А., Подкорытов А. Н. Избранные задачи по вещественному анализу. М., 1993. [С. 12–13, 129–130.]

Оре О. Теория графов. М., 1980. [С. 11–12, 34–36, 77–78, 134–137, 147–150.]

Пайнтген Х.-О., Рихтер П. Х. Красота фракталов. М., 1993. [С. 17–25, 141–142.]

Яглом И. М. Геометрические преобразования. Т. 1. М., 1955. [С. 12–115.]

Дополнительная литература


Александров А. Д., Вернер А. Л., Рыжик В. И. Геометрия 8–9. М., 1991. [С. 289–367, 394–406.]

Александров П. С. Лекции по аналитической геометрии. М., 1968.

Кокстер Т. C. М., Грейтцер C. Л. Новые встречи с геометрией. М., 1978. [С. 100–108.]

Колмогоров А. Н., Фомин С. В. Элементы теории функции и функционального анализа. М., 1972. [С. 44–68.]

Погорелов А. В. Геометрия 6–10. М., 1987.

Фоменко А. Т. Наглядная геометрия и топология. М., 1992. [С. 195–198.]

Barnsley M. F. Fractals everywhere. 2nd edition. Boston, 1993.

Peintgen H.-O., Saupe D., Barnsley M. F. The science of fractal images. Springer-Verlag, 1988.

Программу составил А. Е. Ромащенко

Математическая теория грамматик

1. Формальные грамматики и языки.


1.1. Формальные языки. Порождающие грамматики. Языки, порождаемые грамматиками. Применение грамматик для описания фрагментов естественного языка.

1.2. Совпадение класса языков, порождаемых грамматиками, с классом перечислимых множеств. Теорема Райса о несуществовании нетривиальных разрешимых свойств языков, порождаемых грамматиками.

1.3. Иерархия Хомского. Контекстные, контекстно-свободные, автоматные (праволинейные) грамматики и языки.

1.4. Неукорачивающие грамматики. Алгоритм построения по неукорачивающей грамматике эквивалентной ей контекстной грамматики. Свойства класса контекстных языков. Примеры перечислимых языков, не являющихся контекстными.

2. Конечные автоматы и регулярные множества.


2.1. Конечные автоматы Мура, недетерминированные автоматы, автоматы с частично определенными функциями переходов. Задание конечных автоматов диаграммами. Множества, распознаваемые автоматами каждого из перечисленных типов.

2.2. Канонические праволинейные грамматики. Алгоритм построения по праволинейной грамматике эквивалентной ей канонической праволинейной грамматики. Алгоритм построения по канонической праволинейной грамматике конечного автомата, допускающего порождаемое этой грамматикой множество. Алгоритм построения по конечному автомату праволинейной грамматики, порождающей допускаемое этим автоматом множество.

2.3. Операции над множествами слов: конкатенация, итерация. Регулярные множества слов. Регулярные выражения. Теорема Клини о совпадении класса множеств, допускаемых конечными автоматами, с классом регулярных множеств.

2.4. Лемма о разрастании для автоматных языков. Свойства замкнутости класса автоматных языков. Примеры линейных языков, не являющихся автоматными.

2.5. Синтаксические моноиды.

3. Линейные языки.


Линейные грамматики и языки. Канонические линейные грамматики. Свойства класса линейных языков. Примеры контекстно-свободных языков, не являющихся линейными.

4. Контекстно-свободные языки и автоматы с магазинной памятью.


4.1. Канонические контекстно-свободные грамматики в форме Хомского и в форме Грейбах.

4.2. Деревья вывода и левосторонние выводы. Неоднозначные грамматики. Существенно неоднозначные языки.

4.3. Автоматы с магазинной памятью. Алгоритм построения по контекстно-свободной грамматике автомата с магазинной памятью, допускающего порождаемое этой грамматикой множество. Алгоритм построения по автомату с магазинной памятью контекстно-свободной грамматики, порождающей допускаемое этим автоматом множество.

4.4. Лемма о разрастании для контекстно-свободных языков. Свойства замкнутости класса контекстно-свободных языков. Примеры контекстных языков, не являющихся контекстно-свободными.

4.5. Контекстно-свободность пересечения контекстно-свободного языка и автоматного языка.