Институт №8 МАИ

11 День. Типы данных

d10. Нотация Дейкстры <–> d11. Типы данных <–> d12. Файлы, блоки <–> d13. Критика фон Неймана, рекурсия
d1. Раскладки клавиатур, кодировки <–> d6. Системы программирования <–> d9. Железки (1-12) <–> d14. Железки (13-35) <–> d15. Железки (36-74)

Словарик программиста:

Рациональное число представимо в виде отношения целого и натурального.
В 1937г. Конрад Цузе предложил полулогарифмический формат представления вещественных чисел в ЭВМ.
Массив — регулярный структурный тип с индексированным доступом.
Регулярный: одинаковый тип всех компонент; использование в качестве индексной структуры декартового произведения.
Обход массива — рассмотрение всех компонентов без исключений в определённом порядке по одному разу.
Скалярные данные обрабатываются за раз.

© Нормальный человек не должен
- думать о смерти 
- (это об экзаменах)
- Но мы не настроены на неудачи,
- хотя они, конечно, будут.

Машина умножения конгениальна (там отдельные немногочисленные сдвиги и сложения в двоичных числах. 0х0 = 0, 0х1 = 0)

Надо уметь описать оценку времени работы алгоритмов logO(n), logO(n^2), иначе скидка.

Умножение быстрее деления!

Лучше умножить на 0.5, чем поделить на 2

Задача деления — это эвристика подбора.

3.2.4 Вещественный тип

Рациональное число представимо в виде отношения целого и натурального.

В 1937г. Конрад Цузе предложил полулогарифмический формат представления вещественных чисел в ЭВМ.

Число разлагается на произведение мантиссы (дроби) и экспоненты, являющейся целой частью логарифма. Оно представляется в ЭВМ тремя частями машинного слова: знаком, степенью экспоненты и значением после запятой.

Полулогарифмический формат иначе назван представлением с плавающей точкой. Только плавает не точка, а порядок числа, потому формулировка неудачная!

Необходимость представления знака порядка порождает проблему: они могут быть положительными и отрицательными, а сами числа как очень большие, так и около нуля. Проблема решается кодировкой со смещением, что называется характеристикой (дополнительный код).

Фиксированная арифметика (с фикс. точкой) применялась на бортовых компьютерах в режиме реального времени, а также в СУБД для представления денег.

Любое вещественное число может быть представлено в нормализованном виде с помощью двух чисел (m, p) в приближенном виде.

Машинное эпсилон характеризует точность плавающей арифметики.

Вычисляется в районе единицы, потому что нормализация числа приводит мантиссу к правильной дроби без ведущих нулей после запятой.

При использовании чисел типа REAL получаем приближенные результаты, что связано с неустранимой погрешностью.
А при дополнительных округлениях сталкиваемся с погрешностью округления (возникает и при переходах из разных СС).

© Когда недоступна и зубная щётка, пишем на Pascal.

3.2.5 Литерный тип

В Pascal и Cи имеется встроенный литерный тип. Он применим для ввода-вывода и обработки текстовых данных. Часто для этого используют одномерные массивы — строки.

Константы литерного типа заключаются в кавычки: ‘3’, ‘a’

Множество значений определяется конкретной кодировкой (ASCII, КОИ-8), которая и задаёт порядковый номер литеры, определяемой функцией преобразования типа ord, связывающей литеорный тип с поддапазоном целого.

Литерный тип имеет минимальный набор операций и отношений, включая присваивание.

3.2.6 Согласование типов

Языки фон Неймановского типа допускают согласованное использование различных типов данных в вычислениях.

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

Согласование целого и вещественных типов, близких с математической точки зрения, осуществимо путём округления round() или отбрасывания дробной части trunc().

Преобразование из целого в вещественный осуществляется по умолчанию (перевод смешанного выражения к вещественному типу). Но процесс часто реализуется интерпретативно, и потому достаточно трудоёмкий.

3.2.7 Небазовые типы данных

3.2.8 Понятие о структурном типе данных

Структурные значения — упорядоченные организованные совокупности других значений, рассматриваемые как единое целое. Типичный пример — комплексный тип: состоит из вещественной и мнимой частей.

Структурные типы — совокупности компонентов, распадаемых на поля и элементы.
Структурный тип характеризуется типом компонент и методом организации.

Машина фон-Неймана скалярная и наши первоначальные типы — скалярные!

3.2.9 Тип массив

Массив — регулярный структурный тип с индексированным доступом.
Регулярный: одинаковый тип всех компонент; использование в качестве индексной структуры декартового произведения.

Для массивов одного типа поддерживаются присваивания, а для их элементов и другие арифметические операции.

Обработка массивов в виду скалярности машины фон Неймана выполняется покомпонентно: не за копейку, а за рубль. Как правило, с помощью циклов for.

Обход массива — рассмотрение всех компонентов без исключений в определённом порядке по одному разу.