3.Основные понятия алгебры высказываний. Примеры использования алгебры высказываний в информатике

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывание – это истинное или ложное повествовательное предложение. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0. В алгебре высказываний над высказываниями можно проводить логические операции, в результате которых получаются новые высказывания. Истинность полученных высказываний зависит от истинности исходных высказываний и использованных для их преобразование логических операций.

Операция логического умножения «И» (конъюнция), или логическое произведение

А В АВ

1 1 1

1 0 0

0 1 0

0 0 0

Операция логического сложения «ИЛИ» (дизъюнкция) для двух аргументов

А В А+В

1 1 1

1 0 1

0 1 1

0 0 0

Операция логического отрицания «НЕ» осуществляется над одним высказыванием.

А А"

1 0

0 1

4.Основные понятия теории графов

Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами.

«Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами - дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные маршруты).

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

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

5.Линейные и нелинейные структуры данных

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

Структуры данных могут быть:

- линейные (строчные, картезианские (прямоугольные), списковые);

- нелинейные (древовидные, графовые, сплетения).

Линейная СД. Алгоритм в пошаговом исполнении от начала до конца. Связи между элементами не зависят от выполнения какого либо действия.

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

Списковые СД – множество физически не связанных элементов, для которых отношение следования определено с помощью специальных адресов связи.

Нелинейная СД. Алгоритм с переходами по условию

Древовидной СД называется конечное множество элементов-узлов, между которыми существуют отношения – связь исходного и порожденного.

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

Сплетение (много связанный список) – СД объединяющая понятие дерева, графа и списковых структур.