Лекция 2.

Структуры данных. Математические основы информатики.

Системы компьютерной графики.

Структуры данных.

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

Линейная структура данных (или список) – это упорядоченная структура, в которой адрес данного однозначно определяется его номером (индексом).

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

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

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

Математические основы информатики.

Наиболее важное прикладное значение для информатики имеет алгебра высказываний (или булева алгебра). Основное понятие булевой алгебры – высказывание. Под высказыванием понимается простое повествовательное предложение, о котором можно сказать, истинно оно или ложно (другого быть не может). Высказывания обычно обозначают латинскими буквами (A,B,C,Dи др.), и они могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозначают 1).

Два высказывания называют равносильными, если они имеют одинаковое значение истинности (А=В=0, или А=В=1).

Логические операции.

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

Операцией отрицанияА называют высказывание Ā (иногда обозначают ¬А, произносят как не А), которое истинно тогда, когда А ложно; или наоборот. Операции отрицания соответствует языковая конструкция, использующая частицу НЕ. Операцию отрицания можно записать в виде таблицы, называемой таблицей истинности:

А	Ā
0	1
1	0

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания (С=А٨В или С=А&В, говорят С равно А и В). Операции конъюнкции соответствует языковая конструкция, использующая частицу И. Таблица истинности операции конъюнкции имеет вид:

А	В	А٨В
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывания. Записывается С=А۷В (при этом говорится С равно А или В). Операции дизъюнкции соответствует языковая конструкция, использующая частицу ИЛИ. Таблица истинности операции конъюнкции имеет вид:

А	В	А۷С
0	0	0
0	1	1
1	0	1
1	1	1

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, которое ложно только тогда, когда посылка истина, а заключение ложно. Записывается в виде С=А→В (при этом говорится из А следует В). Таблица истинности имеет следующий вид:

А	В	А→С
0	0	1
0	1	1
1	0	0
1	1	1

Импликация имеет следующие свойства:

А→В ≠ В→А; А→А = 1; 0→А = 1; 1→А = А; А→1 = 1; А→0 = Ā.

Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается в виде С=А↔В (произносится как А равносильно В). Таблица истинности имеет следующий вид:

А	В	А↔С
0	0	1
0	1	0
1	0	0
1	1	1

Эквиваленция имеет следующие свойства:

А↔В = В↔А, А↔В = В↔Ā, А↔1 = А, А↔0 = Ā.