Алгоритм и его свойства. Методы записи алгоритмов

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

Свойства:

Дискретность – алгоритм состоит из отдельных пунктов или шагов.

Определённость – каждый шаг алгоритма должен быть строго сформулирован (иметь точный смысл).

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

Конечность – алгоритм должен завершаться после конечного числа шагов.

Результативность – алгоритм должен приводить к получению конечных результатов.

Массовость – пригодность для решения широкого класса задач.

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

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

Алгоритмы записываются в виде:

словесных правил,

блок-схем,

программ.

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

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

Недостатки словесного способа описания алгоритмов:

отсутствие наглядности,

недостаточная точность.

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

В блок-схеме можно использовать строго определенные типы блоков:

1) начало/конец 2) Вычислительное действие 3) проверка условия 4)ввод/вывод

да нет

Алгоритмический язык - это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения.

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

Алгоритм, записанный на языке программирования, называется программой. Словесная и графическая формы записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования (языке, понятном ЭВМ).

Булева алгебра и вопросы, связанные с ее применением

Булева алгебра – непустое множество, для которого определены три операции: две бинарные операции, представленные знаками È,Ç и одна унарная операция, представленная чертой, ставящейся перед элементом множества(дополнение).

Элементы непустого множества(обозн. чер. U) принято обозначать буквами A, B,… В результате бинарных операций из произвольных элементов A и B из U получаются более сложные элементы: AÈB и AÇB, кот. соотв.-но наз. объединением и пересечением A и B. По определению для каждого элемента A из мн. U однозначно представлен элемент - A, кот. наз. дополнением к A. Для непустого множества U характерно следующее:

1) вместе с элементами A и B в нем содержатся их теоретико-множественное пересечение (Ç) и их теоретико-множественное объединение (È);

2) если элемент A содержится в множестве U, то в U содержится и теоретико-множественное дополнение к A, т. е. множество всех подэлементов из U, кот. не принадлежат A. При этом каждый элемент имеет только одно дополнение.

Система аксиом, предложенная Сикорским:

1. законы коммутативности: A È B = B È A, A Ç B = B Ç A
2. законы ассоциативности: AÈ(BÈС) = (AÈB)ÈС, AÇ(BÇС) = (AÇB)ÇС
3. законы поглощения: (AÇB)ÈB = B, (AÈB)ÇB = B
4. законы дистрибутивности: AÇ(BÈС) = (AÇB)È(AÇС), AÈ(BÇС) = (AÈB)Ç(AÈС)
5. (AÇ-A)ÈB = B, (AÈ-A)ÇB = B. Из этих аксиом следует, что AÇ-AÌ B и BÌ AÈ-A, где Ì - знак включения.

Элемент AÇ-A наз . нулевым элементом, или нулем бул. алгебры и обознач. Ù.

Элемент AÈ-A наз. единичным элементом, или единицей бул. алгебры и обозн. Ú.

При этом считается, что когда бул. алгебра явл. полем подмножеств простр.-ва Х, нулевым элементом U явл. пустое множество, а единичным элементом – все пространство Х.

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

AÈA = A, AÇA = A.

Бул. алгебра наз. вырожденной алгеброй, если в ней имеется только один элемент. Необходимым и достаточным условием вырожденности бул. алгебры счит.-ся рав.-во Ù=Ú, т.е. совпадение нуля и единицы.

Принятая в бул. алгебре система аксиом основана на принципе двойственности. Запас выводимых в ней формул остается без изменений, если всюду соот.-но заменить È на Ç, а Ç на È.

В булевой логике действительны законы де Моргана, согласно кот.

-(A È B) = -A Ç -B, -(A Ç B) = -A È -B. Из этих законов следует, что A Ì B тогда и т. т., когда -B Ì -A, а также то, что AÈB = - (-AÇ -B), AÇB = - (-AÈ -B).

Когда для непустого подмн.-ва счит.-ся выполненными след. два условия:

1) из того, что A, BÎD, следует, что AÈ BÎD,

2) из того, что BÎD и A Ì B, следует, что AÎD,то такое непустое мн.-во наз. идеалом и обознач. гр. бук. D(дельта).

В том случае, когда для непустого подмн.-ва оказ.-ся выполненными след. условия:

1) из A, B ÎÑ, следует, что A Ç BÎÑ,

2) из B ÎÑ и A É B, следует, что AÎD, то такое непуст. подмн.-во наз фильтром и обозн.переверн. гр. бук. Ñ. Понятие фильтра двойственно к понятию идеала.

Если непустое подмн.-во U₀ бул. алгебры U замкнуто относительно операций È, Ç,-, т.е. удовлетворяет след. усл.:

1) если A, B Î U₀, то A È BÎ U₀

2) если A, B Î U₀, то A Ç BÎ U₀

3) если A Î U₀, то - A Î U₀, то оно U₀ наз. подалгеброй алгебры U.

Отображение (обозн. его h) алгебры U в алгебру U¢ наз. гомоморфизмом, если оно сохраняет операции объединения, пересеч.-я, взятия дополнения, т.е.

h(A ÈB)= h (A) È h(B), h(A ÇB)= h (A) Ç h(B), h(- A)= - h(A).

Взаимно однозначный гомоморфизм наз. изоморфизмом.

Бул. алгебра U наз. атомной, если для каждого эл.-та A¹Ù (AÎU) существует атом а ÌA. Безатомной бул. алгебра наз. тогда, когда она не содержит ни одного атома. Атомом бул. алгебры наз. эл.-т а ¹Ù, если для любого AÎU включение а ÌA означает, что или A=Ù, или A= а. Понятие атома явл. бул. аналогией одноточечного мн.-ва. Изоморфизм h бул. алгебры U на себя наз. автоморфизмом.

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

Определения:

Бинарная операция – такая операция мат. логики, когда связ.-ся два высказыв.-я в новое, более сложное высказывания.(конъюнкция, дизъюнкция, импликация, эквив.-ть)

Унарная операция – так. операция, в кот. участвует одна пропорциональная связка и одно высказывание. Такими операциями явл.: операция отрицания ùA или `A, операция необходимости ÿA, операция возможности àA.

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

Æ È М = М Æ Ç М = Æ Æ \ М=Æ М \ Æ = М.

Непустое мн.-во – такое мн.-во, кот имеет хотя бы один элемент.(обозн. М).