Калентьев А.А. Основы информатики

Учебное пособие. — Самара: Самарский университет, 2003. — 80 с.Представлены в конкретной и доступной для практического использования форме базовые понятия информатики: данные (множества, отношения, отображения, способы их представления и интерпретация) и алгоритмы (элементы теории вычислимости, понятие машины Тьюринга). Выбранный способ представления материала позволяет сформировать у студента дельное представление о системе понятий, связанных с изучением информатики.
Пособие предназначено для технических специальностей и может быть рекомендовано студентам старших курсов и аспирантам, специализирующимся по информационным технологиям. Подготовлено на кафедре компьютерных систем.Введение.
Данные.
Множества.
Отношения.
Отображения.
Способы представления данных.
Понятие алфавита.
Кодирование данных.
Представление множеств.
Представление отношений.
Представление отображений.
Интерпретация данных.
Элементы теории вычислимости.
Понятие терма.
Интерпретация терма.
Вычислимые функции.
Базовые функции.
Базовые операции над функциями.
Примитивно-рекурсивные функции.
Частично рекурсивные функции.
Алгоритмы и машины Тьюринга.
Неформальное определение машины Тьюринга.
Формальное определение машины Тьюринга.
Работа машины Тьюринга.
Библиографический список.