1.Абстрагирование данных. Концепция типа данных.

Обрабатываемая информация на компьютере представляет собой абстракцию некоторой части реального мира, в них игнорируются некоторые свойства и характеристики реальных объектов, не существенные для решаемой задачи. Поэтому абстракция – это одновременно упрощение.  При решении задачи нужно определить множество данных, описывающих реальную ситуацию, затем способ представления информации (средствами эвм).  Язык программирования описывает некоторую абстрактную вычислительную машину, понимающую термины этого языка, что соответствует какому-то уровню абстракции от объектов, используемых реальной ЭВМ. Следовательно; работая с таким «языком высокого уровня», программист освобождается от вопросов представления чисел.

Каждая константа, переменная, выражение или функция бывают определенного типа. Этот тип существенным образом характеризует множество значений, к которому при­надлежит константа, которые может принимать переменная или выражение или которые может вырабатывать функция.

1.Любой тип данных определяет множество значений, к ко­торому принадлежит константа, которые может принимать переменная (или выражение), или вырабатыватьфункция).

2.  Тип значения, задаваемого константой, переменной или выражением, можно определить по их виду или описанию без необходимости выполнять какие-либо вычисления.

3.   Каждая операция или функция требует аргументов фикси­рованного типа и выдает результат фиксированного типа.

Кроме типов, задаваемых программистом, нужно иметь некоторые стан­дартные типы, которые называются предопределенными. Они обычно включают числа и логические переменные. Можно описывать простые типы и строить из них структурированные типы любой степени сложности.

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

Основная цель использования абстракций в программи­ровании— обеспечить разработку, анализ и проверку про­граммы на основе законов, управляющих этими абстрак­циями. При этом нет необходимости знать, какими способами эти абстракции реализуются на конкретной вычислительной машине. Однако квалифицированному программисту полезно разбираться в наиболее часто применяемых приемах пред­ставления основных абстракций программирования — таких, как фундаментальные структуры данных. Эти знания могут помочь программисту строить программу и описывать данные с учетом не только абстрактных свойств структур, но и их реализации на конкретной ЭВМ, принимая во внимание.ее свойства и присущие ей ограничения.

Проблема представления данных есть проблема отобра­жения абстрактной структуры в память вычислительной ма­шины. В первом приближении эта память представляет со­бой массив отдельных ячеек памяти, называемых словами. Индексы этих слов называются адресами.

2.Массив - фундаментальная структура данных. Отображение массива на оперативную память, выравнивание, упаковка.

Массив — это регулярная структура; все его компоненты — одного типа, называемого базовым типом. Массив — также структура с так называемым слу­чайным доступом, все его компоненты могут выбираться произвольно   и   являются   одинаково  доступными. Округление числа занимаемых слов до бли­жайшего целого называется выравниванием. Выравнивание  понижает коэффициент  использования  па­мяти.

Отказ от выравнивания может привести к неэффективному обращению к частям слова.

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

Трансляторы всегда автоматически применяют выравнива­ние.

коэффициент можно значительно увеличить, помещая в каж­дое слово более одной компоненты массива. Этот прием на­зывается упаковкой. Полезно иметь возможность ука­зывать желательность упаковки хотя бы в тех случаях, когда в одно слово можно поместить более одной компо­ненты, поскольку при этом достигается экономия памяти в 2 и более раз. type alfa = packed array[l.. n] of char

3.Записи (record)- фундаментальные структуры. Отображение записи на ОП, упакованная запись.

Самый общий метод получения составных типов — это объединение компонент, принадлежащих к произвольным, возможно, тоже составным типам, в один составной тип. Запись и массив имеют обшее свойство: оба являются структурами со «случайным доступом». Запись — более уни­версальная структура, поскольку не требуется, чтобы типы всех ее компонент были одинаковы. С другой стороны, мас­сив предоставляет большие возможности, так как селекторы его компонент могут вычисляться (если они представлены выражениями), тогда как селекторы компонент записи — это фиксированные идентификаторы, задаваемые в описании типа. Записи отображаются в память (размещаются) так, что их компоненты располагаются последовательно.  Если несколько компонент записи умещаются в одном слове памяти, то может идти речь об упаковке. Так же как для массива, желательность упаковки можно указать в описании с помощью слова packed перед словом record. Поскольку смешения компонент вычисляются при трансляции, смещение  компоненты  внутри слова также может определяться транслятором. Это значит, что для многих машин упаковка записей приводит к значительно меньшей потере эффективности, чем упаковка массивов.

4.Представление множества, как фундаментальной структуры данных, в память машины.

Фундаментальная структура данных — множество. Соответствующий тип опи­сывается следующим образом:

type Т = set of Т₀ Значениями переменной х типа Т являются множества эле­ментов типа То. Множество всех подмножеств множества То называется множеством-степенью Т₀. Таким образом, тип Т — это множество-степень своего базового типа То. Примеры: type intset  set of 0.. 30; type charset — set of char. На  всех множествах определены следующие элементар­ные операции: * пересечение множеств,   +  объединение множеств,  —    разность множеств, in    принадлежность множеству. Пересечение  и   объединение  двух   множеств  часто назы­вают   соответственно   умножением   и   сложением множеств. Множество s наилучшим образом представляется в па­мяти машины с помощью характеристической функции. Характеристическая функция — это массив логических зна­чений, i-я компонента которого означает наличие или отсут­ствие i-го значения базового типа в множестве s. Размер этого массива равен кардинальному числу базового типа множества. Представление множеств их характеристической функцией позволяет реализовать операции объединения, пересечения и разности двух множеств с помощью элементарных логиче­ских  операций.

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

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

Из этого прежде всего следует, что объем памяти, необходимый для размещения структуры усложненного типа, неизвестен во время трансля­ции  и  может  изменяться  во  время  выполнения  программы. Это требует динамического распределения памяти.

Последовательность, вво­димая в качестве базового типа, допускает применение только ограниченного множества операторов, основанных на строго последовательном доступе к компонентам, эта структура называется последовательным файлом или просто фай­лом. По аналогии с определениями типа для массивов и мно­жеств файловый тип определяется так: type Т = file of T₀ Это значит, что любой файл типа  Т состоит из 0 или более компонент типа Т₀. Смысл последовательного доступа заключается в том, что в каждый момент доступна лишь одна определенная компо­нента последовательности. Эта компонента определяется те­кущей  позицией   механизма   доступа.  Файл находится в одном из двух состояний: либо формирования (записи), либо про­смотра (чтения). Преимущество строго последовательного доступа особенно ощутимо, если файлы размещаются на вспомогательных за­поминающих устройствах, т. е. если происходит обмен между устройствами. Последовательный доступ —единственный ме­тод, позволяющий успешно скрывать от программиста слож­ность механизмов такого обмена. В частности, он допускает применение буферизации — простого приема, который обес­печивает оптимальное использование ресурсов сложной вы­числительной системы.

6.Элементарные операции над файлами. Структура файловой системы.

Су­ществует операция, инициализирующая процесс формирова­ния файла, операция, инициализирующая просмотр, опера­ция, добавляющая компоненту в конец последовательности, и операция, позволяющая при просмотре переходить к сле­дующей компоненте. Две последние здесь определяются в форме, предполагающей наличие явной вспомогательной переменной, которая представляет собой буфер. Построение пустой последовательности. Операция rewrite (x). Увеличение последовательности. Операция write(x). Инициация просмотра. Операция reset (x). Переход к следующей компоненте. Операция read(x). Операции rewrite и reset не зависят от позиции буфера файла перед их выполнением. В любом случае они возвра­щают его к началу файла.

7. Алгоритм линейного поиска элемента в массиве и его оптимизация - установка «барьера».

Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где искомого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:

1) элемент найден, т.е. a[i] = x;

2) весь массив просмотрен, и совпадения не обнаружено.

Конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент «барьером», ведь он ограждает нас от выхода за границу массива. В этом случае размер массива увеличится на единицу, а сам массив будет описываться так: a[N+1].