е) Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5.

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

 

Состав языков программирования: алфавит, синтаксис, семантика (??? )

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

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

Синтаксис - правила построения из символов алфавита специальных конструкций, с помощью которых составляется алгоритм.

Семантика - система правил толкования конструкций языка.

 

 

Типы и структуры данных. Конструктор селектор (??? )

Простые переменные –описывают структуры, состоящие из одного элемента, потому они характеризуется одним (скалярным) значением. Имя простой переменной характеризует номер ячейки (одной или нескольких), где хранится ее значение. Простая переменная м.б. целой, вещественной, логической, символьной и т.д.

Массивы –переменные с индексами описывают структуры, состоящие из ограниченного множества компонент, упорядоченных в соответствии со значениями индексов. Число индексов определяет размерность (одномерные, двумерные и т.д.).Индекс обеспечивает прямой доступ к любому элементу массива. Элементами массива м.б. как простые так и структурированные данные. Например, м.б. массив массивов.

Строки – упорядоченные, ограниченные последовательности символов некоторого алфавита.

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

Списки – цепочки записей. Основные операции со списками: просмотр записей, включить новую запись и исключить запись из списка. Списки позволяют создавать объекты со сложной меняющейся структурой.

Таблицы – набор записей, с каждой из которых связано имя, называемое ключом. Поиск нужной записи в таблице производится по ее ключу. Основные операции с таблицами: найти запись, включить новую запись и исключить запись из таблицы.

Очереди – структуры данных организованные по принципу «первым пришел – первым ушел». Это динамические структуры, число элементов которых может меняться в процессе обработки. Обработка элементов очереди ведется последовательно один за другим. Добавление новых элементов производится в конец очереди. Основные операции с элементами очереди: чтение, обработка, запись в очередь, удаление из очереди

Стеки – структуры данных организованные по принципу «последним пришел – первым ушел». Примеры: стопка книг, пистолетная обойма, очередь в магазине. Поэтому эта память называется магазинной.
Ссылки – адреса поля памяти, содержимым которого являются другого поля памяти.

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

Деревья– связной граф, в котором нет циклов. При решении многих прикладных задач бывает удобно представлять наборы объектов в виде деревьев. Например, представление двоичных кодов.

 

 

17. Простейшие типы данных: номинальный, перечислимый, ограниченный (??? )

а) Перечисляемый тип — в программировании тип данных, чьё множество значений представляет собой ограниченный список идентификаторов. (например type Cardsuit = (clubs, diamonds, hearts, spades) )

б) Ограниченный тип данных - интервал значений порядкового типа, называемого базовым типом. Описание типа задаёт наименьшее и наибольшее значения, входящие в этот интервал. (Например Var a: 1..25; ch: 'a'..'z'

Здесь переменные а и ch могут принимать значения только из указанного интервала; базовым типом для переменой а является целый тип, а для переменной ch - символьный.) Переменная ограниченного типа сохраняет все свойства переменных базового типа.

 

18. Векторы и алгебра векторов

19. Конструктор-селектор вектора в различных языках программирования

20. Матрицы и матричное исчисление

21. Конструктор-селектор матриц в различных языках программирования

22. Множества и алгебра множеств

23. Операции над множествами и их свойства

 

Множественный тип данных

Множество — тип и структура данных в информатике, является реализацией математического объекта множество.

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

пример:

(type

{определяем базовые для множеств перечислимый тип и тип-диапазон}

colors = (red, green, blue);

smallnumbers = 0..10;

{определяем множества из наших типов}

colorset = set of colors;

numberset = set of smallnumbers;

{можно и не задавать тип отдельно}

anothernumberset = set of 0..20;

 

{объявляем переменные типа множеств}

var nset1, nset2, nset3: numberset;

cset: colorset;

begin

nset1: = [0, 2, 4, 6, 8, 10]; {задаем в виде конструктора множества}

cset: = [reb, blue]; {простым перечислением элементов}

nset2: = [1, 3, 9, 7, 5]; {порядок перечисления неважен}

nset3: = []; {пустое множество}

nset1: = [0..5]; {возможно задавать элементы диапазоном}

nset3: = nset1 + nset2; {объединение}

nset3: = nset1 * nset2; {пересечение}

nset3: = nset1 - nset2; {разность}

if (5 in nset2) or {проверка на вхождение элемента}

(green in cset) then

...

end; )

 

Символьный тип данных

Символьный тип (Сhar) — простой тип данных, предназначенный для хранения одного символа в определённой кодировке. Может являться как однобайтовым (для стандартной таблицы символов), так и многобайтовым (к примеру, для Юникода). Основным применением является обращение к отдельным знакам строки.

 

Строковый тип. Операция конкатенации

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

Конкатена́ ция (сцепле́ ние) — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир». (пример s: =concat(s1, s2))

 

Функции и процедуры над строковыми данными

length(s) определить длину s

copy(s1) копировать значение s1

concat(s1, s2) объединить строки s1 и s2

delete(s, n, k) удалить символы (s – откуда, n – начиная с какого, k – сколько)

insert(k, s, n) вставить текст (k – что, s – куда, n – после какого символа)

pos(k, s) найти номер символа (k – какого, s – где)

 

28. Математическая модель комбинированного типа данных

29. Записи. Вариантные записи

30. Синтаксические диаграммы комбинированного типа данных

31. Селектор записи

 

Понятие модели данных

В классической теории баз данных, модель данных есть формальная теория представления и обработки данных в системе управления базами данных (СУБД), которая включает, по меньшей мере, три аспекта:

а) аспект структуры: методы описания типов и логических структур данных в базе данных;

б) аспект манипуляции: методы манипулирования данными;

в) аспект целостности: методы описания и поддержки целостности базы данных.

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

Модель данных — это абстрактное, самодостаточное, логическое определение объектов, операторов и прочих элементов, в совокупности составляющих абстрактную машину доступа к данным, с которой взаимодействует пользователь. Эти объекты позволяют моделировать структуру данных, а операторы — поведение данных^[1].

Каждая БД и СУБД строится на основе некоторой явной или неявной модели данных. Все СУБД, построенные на одной и той же модели данных, относят к одному типу. Например, основой реляционных СУБД является реляционная модель данных, сетевых СУБД — сетевая модель данных, иерархических СУБД — иерархическая модель данных и т.д.

 

Иерархическая модель данных

Иерархическая модель данных — логическая модель данных в виде древовидной структуры.

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

Узел — информационная модель элемента, находящегося на данном уровне иерархии.

 

Сетевая модель данных

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

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

Сетевая БД состоит из набора экземпляров определенного типа записи и набора экземпляров определенного типа связей между этими записями.

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

а) каждый экземпляр типа записи P является предком только в одном экземпляре типа связи L;

б) каждый экземпляр типа записи C является потомком не более чем в одном экземпляре типа связи L.

 

Реляционная модель данных

Реляционная модель данных— логическая модель данных, прикладная теория построения баз данных, которая является приложением к задачам обработки данных таких разделов математики как теории множеств и логика первого порядка.

На реляционной модели данных строятся реляционные базы данных.

Реляционная модель данных включает следующие компоненты:

а) структурный — данные в базе данных представляют собой набор отношений.

б) целостностный — отношения (таблицы) отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.

в) обработки (манипулирования) — РМД поддерживает операторы манипулирования отношениями (реляционная алгебра, реляционное исчисление).

Кроме того, в состав реляционной модели данных включают теорию нормализации.

Термин «реляционный» означает, что теория основана на математическом понятии отношение (relation). В качестве неформального синонима термину «отношение» часто встречается слово таблица. Необходимо помнить, что «таблица» есть понятие нестрогое и неформальное и часто означает не «отношение» как абстрактное понятие, а визуальное представление отношения на бумаге или экране. Некорректное и нестрогое использование термина «таблица» вместо термина «отношение» нередко приводит к недопониманию. Наиболее частая ошибка состоит в рассуждениях о том, что РМД имеет дело с «плоскими», или «двумерными» таблицами, тогда как таковыми могут быть только визуальные представления таблиц. Отношения же являются абстракциями, и не могут быть ни «плоскими», ни «неплоскими».

Для лучшего понимания РМД следует отметить три важных обстоятельства:

а) модель является логической, то есть отношения являются логическими (абстрактными), а не физическими (хранимыми) структурами;

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

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

 

36. Реляционная алгебра. Основные операции

37. Пример программирования треугольника Паскаля

38. Задача преобразования вектора

⇐ Предыдущая12

Поделиться: