7.3. Тематика рефератов/курсовых работ и методические рекомендации по их выполнению

1. Творцы теории алгоритмов.

Цель данной работы – исследовать причины возникновения теории алгоритмов, ее необходимость для обоснования иных математи­ческих наук.

Рекомендуется следующий план изложения материала:

1. Проблемы отсутствия алгоритма для решения класса математичес­ких задач (проблема тождества для полугрупп и групп, нахождение общего способа решения диофантовых уравнений и др.)./1/, § 71.

2. Неразрешимые задачи в теории алгоритмов. /2/,с. 279-282.

Литература, рекомендуемая для изучения темы:

1. Клини С.К. Введение в математику.- М.: ИЛ, 1957.

2. Мендельсон Э. Введение в математическую логику.- М.: Наука, 1984.

2. Алгоритмы поиска.

Цель данной работы – рассмотреть основные алгоритмы на

графах, которые находят применение при сжатии информации, распозна­вании образов и синтезе баз данных.

Рекомендуется следующий план изложения материала:

1. Необходимые понятия теории графов (/2/, с. 9-43, /1/, с. 57-64).

2. Бинарный поиск (/1/, с. 64-65).

3. Быстрая сортировка (/1/, с. 65-69).

4. Алгоритм Дикстры (/1/, с. 69-72).

Литература, рекомендуемая для изучения темы:

1. Гоппа В.Д. Введение в алгебраическую теорию информации. – М.:

Наука, 1995.

2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

3. Неразрешимость логики первого порядка.

Одним из принципиально важных результатов математической логики и теории алгоритмов является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и вы­полнимости ее предложений. Цель данной работы – изучить до­казательства неразре­шимости логики первого порядка.

Рекомендуется следующий план работы:

1. Изучить основные понятия логики первого порядка (/1/, с. 130-151).

2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость про­блемы остановки (/1/, с. 36-54).

3. Вывести неразрешимость логики первого порядка из неразрешимо­сти проблемы остановки (/1/, с. 152-160).

4. Разобрать доказательство неразрешимости логики первого порядка

методом Геделя (/1/, с. 160-166).

5. Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

4. Нестандартные модели арифметики.

В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. Цель дан­ной работы – проанализировать этот вопрос для элементарной теории арифметики.

Рекомендуется следующий план работы:

1. Рассмотреть язык логики узкого исчисления предикатов арифметики и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).

2. Доказать теорему о существовании нестандартных моделей

элементарной теории арифметики (/1/, с. 252-260).

3. Изучить метод построения моделей элементарной теории арифме­тики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57- 79).

4. Разобрать все примеры из указанных выше литературных источ­ников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 стр.131 в книге /2/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.