Презентация на тему Теория алгоритмов. (Лекция 3)

Алгоритм не содержит ошибок, если он дает правильные результаты

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

Свойства
рецепта,
процесса,
метода,
способа

способами, привлекая разные алгоритмы.
• Как выбрать наиболее эффективный из

Задание «неразмышляющему» исполнителю: вычислить 85 × 85.
Алгоритм 1. Угадывать последовательным перебором чисел из [101, 10 000] до «победного конца».
Алгоритм 2. Умножение «в столбик». Требуется оперативная память тетрадочного листа.
Алгоритм 3. По формуле (8 × (8 + 1)) × 100 + 5 × 5. Вычисления – устный счет.
Алгоритм 4. По вычисленной ранее таблице умножения 100×100, имеющейся у исполнителя.

СРАВНЕНИЕ АЛГОРИТМОВ

http://rain.ifmo.ru/cat/view.php/theory/school

1 – лучший.
• Объём внешней памяти. Оцениваются привлекаемые ресурсы

КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ

http://rain.ifmo.ru/cat/view.php/theory/school

Алгоритм 1
Угадывать последователь-
ным перебором чисел
из [101, 10 000] до «победного конца».

Алгоритм 4
По вычисленной ранее таблице умножения 100×100,
имеющейся у исполнителя.

Алгоритм 3
По формуле
(8 × (8 + 1)) × 100 + 5 × 5. Вычисления – устный счет.

Алгоритм 2
Умножение «в столбик». Требуется оперативная память для записи промежуточныхрезультатов.

и отладки компьютерной программы.
• Нередко оценка временной эффективности опытным

КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ

http://rain.ifmo.ru/cat/view.php/theory/school

Н. И. Пак, Е. К. Хеннер. — М.: Издательский

элементы компьютера, реализующие элементарные логические функции (И,ИЛИ, НЕ, ИЛИ-НЕ,

Базовые логические элементы ЭВМ

Основы алгебры логики

Основные принципы построения архитектуры
ЭВМ

Использование двоичной системы представления данных  

Принцип адресности

Принцип хранимой программы

Принцип однородности памяти

логики отражают в сознании человека свойства, связи и отношения

Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны.

ОСНОВЫ АЛГЕБРЫ ЛОГИКИ

Основы формальной логики заложил Аристотель. Он впервые отделил логические формы мышления от его содержания.

признаки предмета

устройство для автоматической обработки информации
Компьютер

оно распространяется
Компьютер

Дважды два равно пять – естественный язык

- Истинно

- Ложно

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

Алгебра высказываний определяет истинность или ложность составных высказываний

Высказывание может быть либо истинным, либо ложным

форма мышления,
с помощью которой из одного или нескольких

Умозаключение

(0) – ложь
Алгебра высказываний служит для определения истинности или

Простое высказывание состоит из одного высказывания и не содержит логической операции.

Пример.
Простые высказывания:
«процессор является устройством обработки информации»
«принтер является устройством печати»

состоящее из двух простых, соединённых союзом операцией «И»:

«процессор является

Логические операции:
И - логическое умножение, конъюнкция
ИЛИ - логическое сложение, дизъюнкция
НЕ - логическое отрицание, инверсия
«ЕСЛИ - ТО» - логическое следование, импликация
«тогда и только тогда, когда» - эквивалентность, равнозначность

в одно при помощи операции «И».
Конъюнкция обозначается: &, ^,

Составное высказывание, образованное в результате операции «конъюнкция», истинно только тогда, когда истинны входящие в него простые высказывания.

светит солнце
Стоит теплая погода
Стоит холодная погода
На улице

Таблица истинности
операции «конъюнкция»

Пересечение множеств
(диаграмма Эйлера – Венна)

В

одно при помощи союза «ИЛИ»
Дизъюнкция обозначается: ∨, +
Составное высказывание,

х 3 = 9
2 х 2 = 5
4

2 х 2 = 4 или 4 х 4 = 4 F = A ∨ D
3 х 3 = 9 или 2 х 2 = 5 G = B ∨ C
2 х 2 = 4 или 2 х 2 = 5 H = A ∨ C
2 х 2 = 5 или 3 х 3 = 6 I = С ∨ Е

Таблица истинности
операции «дизъюнкция»

Объединение множеств
(диаграмма Эйлера – Венна)

В

высказыванию
Инверсия обозначается: ‾, ¬
Логическое отрицание (инверсия) делает истинное

2 = 5
В – ложь

1) А: 2 х 2 = 4
А - истина
¬А - ложь

Дополнение до универсального множества
(диаграмма Эйлера – Венна)

Таблица истинности
операции «инверсия»

высказывание, которое ложно тогда и только тогда, когда A

Логическое выражение «А → В» в устной интерпретации «звучит»: «если A, то B» или «А имплицирует В».

Импликация обозначается: ®, →

Таблица истинности
операции «импликация»

высказывание, которое истинно тогда и только тогда, когда оба

Эквиваленция обозначается: ↔
Логическое выражение «A ↔ B» в устной интерпретации «звучит»: «A тогда и только тогда, когда B».

Таблица истинности
операции «эквиваленция»

любое высказывание, например: x, у, x1, y1, xk, уn

Логической формулой является:
любая логическая переменная, а также каждая из двух логических констант — 0 (ложь) и 1 (истина);
если А и В — формулы, то В и А*В — тоже формулы, где знак «*» означает любую из логических бинарных операций.

Пример 4:
А=(х & у) → z

Формула принимает одно из двух значений — 0 или 1.

того же набора переменных x1, х2, х3, … xn,

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции: &, v и ¬.

∨ (В ⇒ С) & D ⇔ Ū

Порядок вычисления:
1)

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

В формуле логические переменные, обозначающие высказывания, объединяются знаками логических операций и скобками.
Пример: F = A или В и не А или не В = А + В & ¬А + ¬В

обработки информации
B: Сканер – устройство вывода информации
C: Монитор –

(AVB) <=> (C&D)
(A&B) -> (CVD)
(AVB) -> (C&D)
(A&B) <=> (CVD)
(Ā -> B)&(CVD)
(C <=> Ā)&B&D
(A&B)VC <=> (A&C)V(A&B)
(AVB)VC -> (A&C&D)&(BVD)

A=1
B=0
C=0
D=0

Ответы:

(AVB) <=> (C&D) = 0
(A&B) -> (CVD) = 1
(AVB) -> (C&D) = 0
(A&B) <=> (CVD) = 1
(Ā -> B)&(CVD) = 0
(C <=> Ā)&B&D = 0
(A&B)VC <=> (A&C)V(A&B) = 1
(AVB)VC -> (A&C&D)&(BVD) = 0

A=1, B=0, C=0, D=0

Определите истинность
логических выражений:

истинность или ложность высказывания (логического выражения) при всех возможных

Количество строк в таблице истинности логического выражения определяется количеством логических переменных (N), равно 2 N.

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

функцию
F(X1, X2, …, XN), аргументами которой

= 4.
Количество столбцов в таблице истинности: N2=2N1 =24

F(A,B)=1

F(A,B)=А&B

F(A,B)=A V B

F(A,B)=A↔B

F(A,B)=A→B

F(A,B)=¬(A&B)

F(A,B)=¬(A V B)

¬ (A V B)
Инверсия конъюнкции («штрих Шеффера», «И-НЕ»): F(A,B)=

импликации: A → B = ¬ A V B
Правило

Правило двойной инверсии: ¬ ¬ А =А

может быть доказан с помощью
таблиц истинности.
Пример 6. Правило

Пример 7. Доказательство первого закона поглощения:
x V (x

Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна.
Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула x, или формула (x & у), или обе эти формулы одновременно.
Если x ложна, тогда (x & у) ложна, следовательно, x может быть только истинной.

8.
Доказательство первого закона поглощения x v (x & у

x V (x & у ) = (x & 1 ) V (x & у ) = x & (1 V y) = x

истинна при любых значениях
своих переменных.

Пример 9.
х V ¬х

0 при любых значениях своих переменных.

Пример 10.
х &

V ¬a) = b
¬(x V a) V ¬(x V

Решение

(b → a)
(a & b) → a
Таблицы истинности логических

→ b) & (a → ¬b)

равносильной ей, в которой используются только операции НЕ, И,

По закону дистрибутивности вынесем А за скобки:

скобки на основании закона дистрибутивности:

и сумма делится на 3, то и другое слагаемое

Пример 16.

x = <одно слагаемое делится на 3>
y = <сумма делится на 3>
z = <другое слагаемое делится на 3>
F1 = x & y → z
F2 = x & ¬z → ¬y

x & ¬z → ¬y

и обозначить их буквами.
Записать условие задачи с помощью логических

логику?», был получен ответ:
«Если изучал первый, то изучал и

не изучали.
Обозначим:
Р1 – ,
Р2 –

Упростим выражение
(Р1 → Р2) & ¬(Р3 → Р2) = (¬Р1 v Р2) & ¬(¬ Р3 v Р2) =
= (¬ Р1 v Р2) & Р3 & ¬ Р2= ¬ Р1 & Р3 & ¬ P2v Р2 & Р3 & ¬ Р2

Высказывание Р2 & ¬Р2 =0 (правило операции переменной с ее инверсией), значит: Р2 & Р3 & ¬Р2=0.
Поэтому высказывание: ¬Р1 & Р3 & ¬Р2=1.

На вопрос «Кто из трех студентов изучал логику?», был получен ответ:
«Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

получить максимальную прибыль.
Если А получит максимальную прибыль, то В

получит максимальную прибыль},
С = {С получит максимальную прибыль}.

F1 =

Одно из трех предположений оказалось ложно, а остальные два истинны.

В и С получат максимальную прибыль.