Понятия и свойства алгоритмов

 

 

Тема 1.2. . Логические основы алгоритмизации

Логика – наука о формах и  законах человеческого мышления

1. Понятие - это мысль, в которой обобщаются и выделяются предметы некоторого класса по определенным общим для них признакам.

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

Частные - выражают конкретные факты.

Общие - характеризуют свойства групп объектов или явлений. 

Простые -  это выказывание, в котором никакая его часть не является высказыванием.

Сложные - образованы из нескольких простых с использованием связок и, или, не.

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

Правила вывода умозаключений.

Дедукция - вывод умозаключений от общих к частным.

Индукция - вывод умозаключений от частных к общим.

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

1. Отрицание(инверсия). Соответствует частице НЕ. Обозначается ù А или А. Имея суждение А, можно образовать новое суждение, которое читается «не А» или «не верно, что А». Инверсия логической переменной истинна, если сама переменная ложна и наоборот.

Таблица истинности:

А	Не А
0	1
1	0

2. Конъюнкция (логическое умножение). Соответствует союзу И. Логическим умножением двух высказываний называют новое высказывание, которое истинно только в том случае, когда оба высказывания истинны и ложно во всех остальных случаях. Обозначается знаками ^, &, *.

Таблица истинности:

А	В	А*В
0	0	0
0	1	0
1	0	0
1	1	1

3. Дизъюнкция(логическое сложение). Соответствует союзу ИЛИ. Логическим сложением двух высказываний называется новое высказывание, которое ложно, когда оба высказывания ложны и истинно во всех остальных случаях. Обозначается знаками  Ú , +

Таблица истинности:

А	В	А+В
0	0	0
0	1	1
1	0	1
1	1	1

4. Эквивалентность

Таблица истинности:

А	В	А~В
0	0	1
0	1	0
1	0	0
1	1	1

5. Импликация (Логическое  следование)

Таблица истинности:

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

 

 ПРИМЕР 1: составить таблицу истинности – не А и не В.  (А*В)

А	В	неА	неВ	F
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	0	0	0

 

ПРИМЕР 2: составить таблицу истинности – не (А и В и С) (А*В*С).

А	В	С	А*В*С	F
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	0	1
1	0	0	0	1
1	0	1	0	1
1	1	0	0	1
1	1	1	1	0

 

Примеры записи логических выражений, истинных при выполнении указанных условий.

Условие	Запись на школьном алгоритмическом  языке
Дробная часть вещественого  числа a равна нулю	int(a) = 0
Целое число a — четное	mod(a, 2) = 0
Целое число a — нечетное	mod(a, 2) = 1
Целое число k кратно семи	mod(a, 7) = 0
Каждое из чисел a, b положительно	(a>0) и (b>0)
Только одно из чисел a, b положительно	((a>0) и (b<=0)) или   ((a<=0) и (b>0))
Хотя бы одно из чисел  a, b, c является отрицательным	(a<0) или (b<0) или (c<0)
Число x удовлетворяет условию  a < x < b	(x>a) и (x<b)
Число x имеет значение в  промежутке [1, 3]	(x>=1) и (x<=3)
Целые числа a и b имеют  одинаковую четность	((mod(a, 2)=0) и (mod(b, 2)=0) или ((mod(a, 2)=1) и (mod(b, 2)=1))
Точка с координатами (x, y) лежит в круге радиуса r  с центром в точке (a, b)	(x-a)**2 + (y-b)**2 < r*r
Уравнение ax^2 + bx + c = 0 не имеет  действительных корней	b*b - 4*a*c < 0
Точка (x, y) принадлежит первой  или третьей   четверти	((x>0) и (y>0)) или   ((x<0) и (y>0))
Точка (x, y) принадлежит внешности  единичного круга   с центром в начале координат или его второй четверти	(x*x + y*y > 1) или   ((x*x + y*y <= 1) и (x<0) и (y>0))
Целые числа a и b являются  взаимнопротивоположными	a = -b
Целые числа a и b являются взаимнообратными	a*b = 1
Число a больше среднего арифметического  чисел b, c, d	a > (b+c+d) / 3
Число a не меньше среднего  геометрического чисел b, c, d	a >= (b+c+d) ** (1/3)
Хотя бы одна из логических  переменных F1 и F2 имеет   значение да	F1 или F2
Обе логические переменые  F1 и F2 имеют значение да	F1 и F2
Обе логические переменые  F1 и F2 имеют значение нет	не F1 и не F2
Логическая переменная F1 имеет  значение да, а   логическая переменная F2 имеет значение нет	F1 и не F2
Только одна из логических переменных F1 и F2   имеет значение да	(F1 и не F2) или (F2 и не F1)

 

Вопросы для самоконтроля

1. Какими понятиями оперирует алгебра логики?
2. Правила вывода умозаключений. Примеры?
3. Связь алгебры логики с алгоритмизацией?
4. Расскажите операции алгебры логики?

 

 

 

Тема 1.3. Языки и системы  программирования

1.3.1 Эволюция  языков программирования.

Классификация языков программирования

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

Таблица 1. Поколения языков программирования

 

Поколения	Языки программирования	Характеристика
Первое	Машинные	Ориентированы на использование в конкретной ЭВМ, сложны в освоении, требуют хорошего знания архитектуры ЭВМ
Второе	Ассемблеры, Макроассемблеры	Более удобны для использования, но по-прежнему машинно-зависимы
Третье	Языки высокого уровня	Мобильные, человеко-ориентированные, проще в освоении
Четвертое	Непроцедурные, объектно-ориентированные, языки запросов, параллельные	Ориентированы на непрофессионального пользователя и на ЭВМ с параллельной архитектурой
Пятое	Языки искусственного интеллекта, экспертных систем и баз знаний, естественные языки	Ориентированы на повышение интеллектуального уровня ЭВМ и интерфейса с языками

Классификация языков программирования. Изучение языков программирования часто начинают с их классификации. Определяющие факторы классификации обычно жестко не фиксируются. Чтобы продемонстрировать характер типичной классификации, опишем наиболее часто применяемые факторы, дадим им условные названия и приведем примеры ЯП для каждой из классификационных групп

Фактор	Характеристика	Группы	Примеры ЯП
Уровень ЯП	Степень близости ЯП к  архитектуре компьютера	Низкий	Автокод, ассемблер
		Высокий	Fortran, Pascal, ADA, Basic, С и др. ЯВУ
		Сверхвысокий	Сетл
Специализация ЯП	Потенциальная или реальная область применения	Общего назначения (универсальные)	Algol, PL/1, Simula, Basic, Pascal
		Специализированные	Fortran (инженерные рассчеты), Cobol (коммерческие задачи), Refal, Lisp (символьная обработка), Modula, Ada (программирование в реальном времени)
Алгорит-мичность (процедур-ность)	Возможность абстрагироваться от деталей алгоритма решения задачи. Алгоритмичность тем выше, чем точнее приходится планировать порядок выполняемых действий	Процедурные	Ассемблер, Fortran, Basic, Pascal, Ada
		Непроцедурные	Prolog, Langin

 

1.3.2 Исходный . объектный и загрузочный модуль.

Интегрированная среда программирования

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

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

Структурный подход базируется на двух основополагающих принципах:

·  использование процедурного стиля программирования;

· последовательная  декомпозиция  алгоритма решения  задачи 
сверху вниз.