II семестр

0. Содержание курса

Лекций -2; Семинаров -0 (2); Лабораторных -2;

До 1 апреля 10 баллов на F (кто не успел - 15 баллов до 15 апреля).

Апрель - контрольная по составлению проекта программы.

Май - защита курсовых работ.

Июнь - экзамен.

Литература по Фортрану (в дополнение к списку 1 семестра):

1. П.В. Соловьев. Fortran для персонального компьютера (Справочное пособие). М 1991.

2. З.С. Брич, Д.В. Капилевич, Н.А. Клецкова. Фортран 77 для ПЭВМ. М, «Ф и С», 1991.

Лекция 1

1.1 Cтруктуры данных

1.1.1 Основные понятия

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

Задача для ЭВМ = вычислительная часть + обработка информации.

• Информация – совокупность сведений или знаний.

• Данные - информация, пригодная для обработки.

• Система – совокупность взаимосвязанных объектов, подчиненных определенной (единой) цели.

• Автоматизированные информационные системы (АИС) - системы обработки данных.

• Базы данных (БД) - совокупность взаимосвязанных данных.

• Структура - взаимосвязь отдельных элементов.

• Запись - совокупность (группа) элементов (полей).

Эффективность обработки данных зависит от формы представления (типы данных), взаимосвязи отдельных элементов (структур данных), последовательности действий (алгоритма).

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

Три уровня абстракции описания структур данных:

• Набор функциональных спецификаций;

• Логическое описание (типы данных);

• Физическое представление.

1.1.2 Классификация структур данных

Линейные			Нелинейные
Прямоугольные	Структуры ряда	Списковые	Древовидные	Графы	Мульти графы
Массивы, таблицы	Строки, очереди, стеки, деки	Линейный список	n-дерево, бинарное дерево, дерево двоичного поиска

Указатель - адрес начала записи.

1.1.3 Обозначения и договоренности

Пусть Т1, Т2, ..., Тn - имена известных типов данных

Т=record N1:T1; N2:T2; ...; Nn:Tn end - новый тип - запись, Ni - имена полей, i=1,2,...,n.

Пусть t:T, ti:Ti, i=1,2,...,n; инициализация t.N1=t1; t.N2=t2; ..., t.Nn=tn; если tt:T, то можно tt:=t (присваивание).

Пример:

type

Comp=record {Комплексное число}

Re:real;

Im:real

end;

var

z:Comp;

zz:Comp;

В секции действий

z.Re:=3.14; z.Im:=1.0;{инициализация}

zz:=z (присваивание).

Глобальный тип: Inf - информационная часть (часть данных, не влияющих на структуру).

1.1.4 Множества.

Множество записей - простейшая вырожденная структура данных, характеризуемая отсутствием взаимосвязи между элементами множества (записями). В языке Паскаль логическое описание и физическое представление множества берет на себя транслятор (тип данных множество предопределен в языке, описатель set of T). Операции над множествами сведены в таблицу.

Имя операции	Функциональные спецификации	Аргументы	Результат	Описание
Создать	U			Создается пустое множ
Включить	TUU	t, u	{xTxu или x=t}	К u добавляется t, если он не принадлежит u
Принадлежит?	TUBoolean	t, u	Истина, если tu,	Принадлежит ли элемент t множеству u?
Исключить	TUU	t, u	{xTxu и xt}	Удалить элемент t из множества u
Пусто?	UBoolean	u	Истина, если u=	Пусто ли множество u?
Объединение	UUU	u1, u2	{xTxu1 или xu2}	Объединение u1 и u2
Пересечение	UUU	u1, u2	{xTxu1 и xu2}	Пересечение u1 и u2
Разность	UUU	u1, u2	{xTxu1 и xu2}	Разность u1 и u2
Дополнение	UU	u	{xT xu}	Дополнение к u

Здесь Т – базовый тип множества, U – тип множество, t – данное базового типа (t:T или tT), u, u1, u2 – данные типа U.

1.1.5 Прямоугольные структуры. Массивы

Массив - конечное упорядоченное множество элементов (записей) одного типа. Индекс (номер по порядку) указывает относительное положение элемента (отсчет ведется от первого элемента). В языках программирования структура данных "массив" поддерживается транслятором. Пусть Т - базовый тип, т.е. тип элементов, I – индексный тип (множество допустимых индексов). Тогда можно определить новый тип данных М = array[I]of Т.

Над массивом определены следующие операции:

• создание массива (это делает транслятор),

• инициализация элемента,

• чтение значение элемента

Задача. Записать функциональные спецификации для структуры данных «массив».

Создание массива М,

Инициализация массива МITМ,

Чтение значения элемента массива МIT.