Лекция: Принципы построения алгоритмов

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

1. Принцип поэтапной детализации алгоритма (другое название — «проектирование сверху-вниз»). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.
2. Принцип «от главного к второстепенному», предполагающий составление алгоритма, начиная с главной конструкции. При этом, часто, приходится «достраивать» алгоритм в обратную сторону, например, от середины к началу.
3. Принцип структурирования, т.е. использования только типовых алгоритмических структур при построении алгоритма. Нетиповой структурой считается, например, циклическая конструкция, содержащая в теле цикла дополнительные выходы из цикла. В программировании нетиповые структуры появляются в результате злоупотребления командой безусловного перехода (GoTo). При этом программа хуже читается и труднее отлаживается.

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

В древности различные мыслители пробовали давать рецеп­ты правильных умозаключений, которые от истинных посылок приводят только к истинным выводам. Таких мыслителей назы­вали логиками. Наука установила общие методы правильных умозаключений, называемых формальной логикой.

Термин «логика» происходит от древнегреческого logos,оз­начающего «слово, мысль, понятие, рассуждение, закон».

Понятие — это форма мышления, в которой отражены суще­ственные (отличительные) свойства объектов.

Суждение — это форма мышления, отражающая связь поня­тий друг с другом.

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

Высказывание — это любое предложение какого-либо языка (утверждение), содержание которого можно определить как ис­тинное или ложное.

Предикат — высказывание, содержащее одну или несколько неизвестных.

Таблица истинности — это таблица, описывающая логическую функцию.

Всякое высказывание или истинно, или ложно; быть одно­временно и тем и другим оно не может. Формулировка любой теоремы является высказыванием. Высказывания могут выра­жаться с помощью математических, физических, химических и прочих знаков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства. Сами числовые выражения высказываниями не являются. Не являются высказываниями и равенства или неравенства, содер­жащие переменные.

Например, предложение Х < 12 становится высказыванием при замене переменной каким-либо конкретным значением. Та­кие предложения называют высказывательными формами.

Примерами высказываний могут служить:

1) {Число 2 является делителем числа 7} (ложное высказыва­ние);

2) {3 + 5 = 2*4} (ложное высказывание);

3) {2 + 6 > 10} (ложное высказывание);

4) {II + VI > VIII} (ложное высказывание);

5) {Сумма чисел 2 и 6 больше числа 8} (ложное высказы­вание);

6) {Two plus six is eight} (истинное высказывание);

7) {Студент X лучший по информатике} (предикат).

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

В алгебре логики, как и в обычной алгебре, вводится ряд операций.