Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Что можно делать с вещественными числами и нельзя с целыми
Осень 2013, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Курс будет состоять из двух формально независимых частей. Взятые вместе, они демонстрируют существенное различие, с алгоритмической точки зрения, вещественных чисел и целых чисел. А именно, в первой части будет изложена версия алгоритм Тарского, позволяющего установить истинность или ложность любой замкнутой арифметической формулы первого порядка с переменными для вещественных чисел. В качестве бесплатного приложения этот алгоритм дает разрешимость элементарной геометрии (через введенный Р. Декартом метод координат). Во второй части будет рассказано про отрицательное решение десятой проблемы Гильберта, в которой он просил найти алгоритм, который позволял бы по произвольному диофантову уравнению узнавать, имеет ли оно решения в целых числах — такого алгоритма не существует.

Статья Юрия Владимировича Матиясевича Алгоритм Тарского в журнале Компьютерные инструменты в образовании: http://ipo.spb.ru/journal/index.php?article/1002/

Lecture notes: Yury Matiysevich. On Hilbert's Tenth Problem http://www.mathtube.org/sites/default/files/lecture-notes/Matiyasevich.pdf

Задачи из книжки: 1.2, 1.11, 1.13, 1.14, 1.15, 3.1, 3.2, 3.3, 3.4, 3.6, 3.17, 5.8, 6.1, 7.1, 7.2, 7.5, 7.7, 8.2, 8.5, 8.6, 8.7, 8.8, 8.10, 10.1В, 10.2.

Скан нескольких страниц: [pdf]

Первая и пятая главы: http://logic.pdmi.ras.ru/~yumat/H10Pbook/index.html