программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 1. Введение в информатику а) элементарные шаги обработки, которые имеются в распоряжении; б) описание выбора отдельных подлежащих выполнению шагов. Для алгоритмически разрешимой постановки задачи всегда имеется много раз- личных способов ее решения, т. е. различных алгоритмов. 1.2.1 Примеры неформальных описаний алгоритмов Пример 1. Арифметические операции над десятичными числами. В начальной школе мы на неформальном уровне изучаем правила вычисления суммы двух чисел и умножения («вычисления в столбик»). Пример 2. Алгоритм Евклида для вычисления наибольшего делителя (НОД). Постановка задачи. Пусть даны два положительных целых числа a и b, надо найти наибольший общий делитель НОД(a, b) чисел a и b. 2а. Первая версия алгоритма: • если a = b, то справедливо НОД(a, b) = a; • если a < b, то применяем алгоритм НОД к числам a и b − a; • если b < a, то применяем алгоритм НОД к числам a − b и b. Используется математическое свойство: для любых положительных целых чи- сел x и y если x < y, то НОД(x, y) = НОД(y − x, x). 2б. Вторая версия алгоритма: 1) если a < b, то меняем местами значения (так, чтобы стало a ⩾ b); 2) делим a на b, пусть r — остаток от деления (имеем a ⩾ b > r ⩾ 0); 3) если r = 0, то b — выход; 4) положить (заменить) a на b, b на r и вернуться к шагу 2. Пример 3. Сортировка колоды карт. Постановка задачи. Имеется колода карт. Пусть на каждой карте зафиксирова- но одно натуральное число (ради простоты будем считать, что все числа попарно 1.2 Понятие алгоритма 11 различны). Требуется отсортировать, т. е. упорядочить, колоду карт так, чтобы за- фиксированные на картах числа образовывали монотонную (возрастающую или убывающую) последовательность. 3а. Сортировка путем предсортировки и слияния. Заданная колода x сортируется с помощью следующего предписания: • если x пуста или содержит одну карту, то x отсортирована; • если x содержит более одной карты, то x разделить на две непустые колоды; отсортировать каждую из них и затем слить (объединить) эти колоды в одну отсортированную колоду. 3б. Сортировка путем вставок. Заданная колода сортируется по убыванию с помощью следующего алгоритма, который в соответствующее место отсортированной колоды y вставляет по очереди карты, выбираемые из неотсортированной колоды x (процесс начинается с пустой колоды y): • если колода x пуста, то y — искомая отсортированная колода; • если x не пуста, то из x берется любая карта и вставляется в подходящее место колоды y, так, чтобы в результате колода y осталась отсортированной. Этот алгоритм применяется к уменьшающейся колоде x и увеличивающейся колоде y. 3в. Сортировка путем выбора. Заданная колода x сортируется по убыванию по следующему алгоритму, кото- рый последовательно выбирает из x «наибольшую» карту и добавляет ее в конец колоды y (процесс начинается с пустой колоды y). Пусть даны две колоды x и y. Пусть колода y отсортирована по убыванию, и пусть все карты из y больше любых карт из x. Колода x всортировывается в y по следующему предписанию: • если x пуста, то y — искомая отсортированная колода; • если x не пуста, то из x выбирается «наибольшая» карта и добавляется в ко- нец y. Алгоритм применяется к уменьшающейся колоде x и увеличивающейся колоде y. 3г. Сортировка путем перестановки. Заданная колода x сортируется по следующему алгоритму: • если x содержит две соседние карты, нарушаемые требуемое упорядочение, то эти карты меняются местами, после чего к полученной колоде применя- ется этот же алгоритм; • если в x не встречается ни одной неупорядоченной пары соседних карт, то колода x отсортирована и тем самым является искомой колодой. 12 Глава 1. Введение в информатику Пример 4. Алгоритм вычисления дроби (a + b)/(a − b). Сначала вычисляем (используя алгоритмы сложения и вычитания) значения выражений a + b и a − b (все равно, последовательно или одновременно), а потом образуем частное от деления полученных результатов (используя алгоритм деления). Пример 5. Алгоритм, распознающий, можно ли получить последовательность знаков a из последовательности знаков b посредством вычеркивания некоторых знаков. Если a — пустая последовательность знаков, то ответом будет «да». В против- ном случае нужно посмотреть, не пуста ли последовательность b. Если это так, то ответом будет «нет». Иначе нужно сравнить первый знак последовательности a с первым знаком последовательности b. Если они совпадают, то надо снова при- менить тот же алгоритм к остатку последовательности a и остатку последователь- ности b. В противном случае нужно снова применить тот же алгоритм к исходной последовательности a и остатку последовательности b. Этот алгоритм выдает двузначный результат, «да» или «нет», т. е. он являет- ся алгоритмом распознавания свойства «быть частью данной последовательности знаков». Хотя описание алгоритма конечно и постоянно, количество фактически вы- полняемых тактов — величина переменная. Это оказывается возможным благодаря итерации (алгоритмы 2б, 3б, 3в, 3г) или рекурсии (алгоритмы 2а, 3а, 5). При словес- ном описании итерацию часто записывают в следующей форме «Пока выполнено определенное условие, повторяй». Рекурсия — это когда поставленная задача реша- ется с помощью решения той же самой задачи, но с несколько измененными (более простыми) параметрами. Классические элементы описания алгоритмов: • выполнение элементарных шагов; • разветвление по условию; • повторение и рекурсия. 1.3 Вычислительные структуры 13 1.3 Вычислительные структуры Установление отношений между содержащейся в представле- нии информацией и окружающим миром мы называем понима- нием. Поскольку это понимание является индивидуальным, субъ- ективным процессом, который трудно сделать общедоступным, мы удовлетворяемся в информатике тем, что интерпретацию представления как носителя информации определим путем отож- дествления информации с подходящими математическими (вы- числительными) структурами. Тогда значение представления устанавливается путем отображения на эти математические (вычислительные) структуры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Представление N вместе с сопоставленной ему информацией I называется объектом (элементом данных), а во множественном числе — данными. Итак, объект есть пара (N, I), при этом ин- формацию I называют значением объекта, а представление N — обозначением объекта. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Объекты в алгоритмах играют роль предметов, над которыми производятся определенные операции. На практике классы объектов часто выделяются благодаря тому, что на них определен некоторый естественный процесс обработки информа- ции и ее представлений. (Например, операции сложения и умножения над целыми числами.) Не всякий объект годится как операнд для той или иной операции. Пример Множество объектов, для которых естественным образом определено некото- рое количество операций, называется множеством объектов определенного типа. Таким образом, тип элементов данных характеризуется операциями, которые могут над ними выполняться. Вычислительная структура состоит из одного или нескольких типов и некоторых основных (элементарных, базовых) операций над этими типами, каждая с результатом одного из этих типов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . При составлении программы для решения какой-либо задачи необходимо сна- чала выделить подходящие вычислительные структуры, а затем решить, как эти структуры представлять в языке программирования. 14 Глава 1. Введение в информатику 1.3.1 Основные вычислительные структуры Рассмотрим основные вычислительные структуры и обычное представление этих структур с помощью языка Паскаль. 1. Вычислительная структура целых чисел. Состоит из множества целых чисел и некоторого ряда производимых над ними арифметических операций. Внутренние операции: сложение, вычитание, умножение и некоторые другие. Операция деления не всегда определена. Наряду с внутренними операциями для целых чисел определены операции сравнения: предикаты равно, не равно, больше, меньше, больше или равно, меньше или равно. Результат сравнений имеет значение «истина» или «ложь». Типичное представление целых чисел в Паскале осуществляется с помощью типа данных Integer. 2. Вычислительная структура вещественных чисел. Состоит из множества вещественных чисел и арифметических операций с ве- щественными результатами. В отличие от целых чисел для вещественных нет опе- раций получения последующего или предыдущего числа. Типичное представление вещественных чисел в Паскале осуществляется с по- мощью типа данных Real. 3. Вычислительная структура символов. Состоит из множества символов (знаков), для которых выполняются некоторые операции, например сравнения. Символы в языке Паскаль представляются с помо- щью типа Char. 4. Однородные конечные последовательности. Состоит из множества конечных последовательностей, элементами которых служат данные одного и того же типа, например: числа или символы. В Паскале данной вычислительной структуре соответствуют массивы. Конечные последова- тельности легко реализуются также динамически в виде списков (используется ссылочный тип). Представления с помощью строк или списков позволяют после- довательностям менять свои размеры во время выполнения программы. 5. Неоднородные конечные последовательности. Состоит из множества конечных последовательностей, элементами которых могут быть данными разных типов. В Паскале данной вычислительной структуре соответствуют записи. 6. Бесконечные последовательности. Абстракции заранее не ограниченных последовательностей в языках програм- мирования соответствуют файлы. 7. Вычислительная структура значений истинности. При выполнении алгоритма часто необходим разбор случаев (разветвление по условию), и поэтому необходимо иметь возможность формально выражать выпол- нение или невыполнение тех или иных условий. Поэтому вводится вычислительная структура значений истинности, состоящая из двух элементов данных «истина» и «ложь» — соответственно True и False в языке Паскаль. 1.4 Алгоритмические языки 15 1.4 Алгоритмические языки Использованный ранее неформальный способ описания алгоритмов отличается следующими недостатками: • громоздок и излишне многословен; • неоднозначность понимания. Для представления, улучшения читаемости и для простоты представления алго- ритмов, которые будут выполняться на компьютере, применяются алгоритмические языки (языки программирования). Запись алгоритма на языке программирования называется про- граммой. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . При конструировании алгоритмического языка необходимо: • исходить из некоторого набора вычислительных структур (структур данных); • вводить как составные операции, так и составные (структурированные) объекты; • выбрать форму, удобную как для человека, который описывает алгоритм, так и для человека, который должен будет читать и понимать этот алго- ритм, — форму, соответствующую кругу человеческих понятий и представ- лений. Три составляющие (любого) языка: алфавит, синтаксис и семантика. Алфавит — набор основных символов, «букв алфавита», никакие другие символы в предложениях языка не допускаются. Синтаксис — система правил, определяющая допустимые кон- струкции из букв алфавита. Синтаксис отвечает на вопрос: яв- ляется ли последовательность символов текстом (программой) на данном языке или нет? Семантика — система правил, истолковывающая отдельные кон- струкции языка с точки зрения процесса обработки (смысл про- граммы). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . При описании языка и при построении алгоритма используются понятия языка. Любое понятие алгоритмического языка имеет свой синтаксис и свою семантику. 16 Глава 1. Введение в информатику Точнее: • синтаксические правила показывают, как образуется данное понятие из других понятий и (или) букв алфавита; • семантические правила определяют свойства данного понятия в зависимости от свойств используемых в них понятий. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Описание синтаксиса алгоритмических языков Для описания синтаксиса языка необходим какой-то язык (метаязык, надъ- язык). Естественный язык часто используется как метаязык, но для описания язы- ков программирования он — громоздкий, нестрогий, неоднозначный. В качестве метаязыка часто используется язык металингвистических формул Бэкуса-Наура (язык БНФ). Язык БНФ позволяет описывать формальные языки в виде некоторых формул. Описание синтаксиса иерархично: с использованием символов (буквы алфавита) сначала описываются простейшие понятия, потом — более сложные понятия, наконец, описываются синтаксически правильные про- граммы. С точки зрения синтаксиса каждое определяемое понятие являет- ся метапеременной языка БНФ, значением которой может быть любая конструкция из некоторого фиксированного для этого по- нятия набора конструкций. Для каждого понятия используется своя метаформула, которая состоит из левой и правой частей. Левая часть — определяемое понятие (метапеременная). Правая часть задает все множество значений этой метапеременной, все возможные способы конструирования этого понятия. Метапеременные заключаются в угловые скобки, например <чис- ло>, <арифметическое выражение>. Метасимвол «::=» (смысл которого можно передать словом «есть») разделяет левую и пра- вую части метаформул. Метасимвол « ∣» (смысл — «или») отделя- ет все допустимые конструкции в правой части формулы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Описание синтаксиса алгоритмических языков 17 Пример <переменная> ::= A | B <выражение> ::= <переменная> | <переменная> − <переменная> | <переменная> + <переменная> Понятие <выражение> допускает следующие синтаксические цепочки: A, B, A + A, A − A, B + B, B − B, A + B, B + A, A − B, B − A. Чтобы с помощью конечного множества правил задавать бесконечное множе- ство последовательностей символов, используют рекурсивные определения. Пример <двоичная цифра> ::= 0 | 1 <двоичный код> ::= <двоичная цифра> | <двоичный код> <двоичная цифра> Для определения понятия в правой части используется само это понятие. Чтобы не получилось «порочного круга», правая часть формулы должна содержать хотя бы одно частное определение (не содержащее определяемое понятие). Метасимволы {и} используются для задания синтаксических конструкций про- извольной длины. Таким образом, {<конструкция>} означает, что <конструкция> может повторяться ноль или более раз. Пример <двоичный код> ::= <двоичная цифра>{<двоичная цифра>} Пример Язык арифметического выражения над целыми числами с символами опера- ций +, — и ∗ образует формальный язык над символами (0, . . ., 9, (, ), +, −, ∗). Этот язык определяется через следующие БНФ-правила синтаксического понятия <арифм выраж>: <арифм выраж> ::= <число> | (<арифм выраж>) |<арифм выраж><операция><арифм выраж> <операция> ::= + | — | * <число> ::= <цифра>{<цифра> | 0} | 0 <цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 18 Глава 1. Введение в информатику Пример Пусть формальный язык «Показушка» описывается следующими формулами Бэкуса-Наура: <предложение> ::= <подлежащее><предикат> <подлежащее> ::= <именная группа> <предикат> ::= <глагол><именная группа> | <глагол><наречие> <именная группа> ::= <существительное> | <список прилагательных> <существительное> <список прилагательных> ::= <прилагательное>{,<список прилагательных>} <существительное> ::= КОШКА | МЫШКА <прилагательная> ::= ЧЕРНАЯ | БЕЛАЯ | ТОЩАЯ | УПИТАННАЯ <глагол> ::= БЕЖИТ | ЕСТ <наречие> ::= БЫСТРО | МЕДЛЕННО Следующие последовательности символов принадлежат множеству значений понятия <предложение>: МЫШКА БЕЖИТ БЫСТРО; БЕЛАЯ КОШКА ЕСТ ЧЕРНАЯ КОШКА; УПИТАННАЯ, ТОЩАЯ, ЧЕРНАЯ, БЕЛАЯ МЫШКА ЕСТ МЕДЛЕННО. Описание формальных языков может быть достигнуто в общем случае с по- мощью так называемых грамматик. БНФ-нотация представляет собой некоторую специальную форму описания для определения таких грамматик, которые называ- ются контекстно-свободными грамматиками. 1.6 Семантика программы Для недвусмысленного описания семантики целесообразно выбрать математи- ческую форму описания, т. е. сопоставление математических объектов (например, элементов из определенных множеств и функций) для конструкций языка. Суще- ственно различаются две крайние точки зрения в связи с установлением семантики. Функциональная семантика. Описание функций программы, т. е. установление отношения между входными и выходными данными (экстенсиональное или наблюдаемое отношение), называют функ- циональной семантикой. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Операционная семантика. Описание последствий отдельных ша- гов вычислений, которые имеют место при выполнении програм- мы, называют операционной семантикой. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Трансляция и выполнение 19 Функциональная семантика программы может быть получена в общем слу- чае через абстракцию, т. е. избегая частностей, что имеет место в операционной семантике. Принципиально семантика (т. е. значение) программы допускает описание бла- годаря тому, что задается специфичный способ действия при ее выполнении на конкретной ЭВМ. Однако языки программирования для того и развивались, чтобы формулирование алгоритмов можно было осуществлять единообразно для боль- шого числа различных машин, независимо от специфичных внутренних структур машины. Поэтому представляет интерес «машинно-независимое» описание алго- ритмов в виде программ, а также машинно-независимое описание значения языка программирования. При конструировании программ для решения поставленной задачи необходимо обеспечить, чтобы окончательно составленная программа соот- ветствовала требованиям, т. е. являлась корректной в смысле поставленной задачи. Эта корректность не всегда очевидна, особенно при больших структурах программ. Доказательство корректности в принципе может быть проведено с помощью семан- тики языка программирования. Впрочем, многие способы определения семантики практически мало подходящие для такого доказательства. Поэтому делаются по- пытки перевести как требования к программам, так и значение программы к логи- ческим формулам. Тогда доказательства корректности можно достичь с помощью логического вывода. Такой подход называется верификацией программ. Через пра- вила перевода программ в логические формулы неявно включается также и опре- деление семантики. Наряду с функциональным и операционным описанием семанти- ки языков программирования представляют также интерес та- кие способы описания, которые позволяют делать высказывания о свойствах программы. К ним можно отнести логические фор- мулы, которые определяют («аксиоматизируют») определенные свойства конструкций языков программирования. Тогда мы гово- рим также об аксиоматической семантике. С помощью аксиом и логических правил вывода могут быть тогда выведены и выска- зывания о программе. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Трансляция и выполнение Компьютер — это автомат, выполняющий алгоритм. Для того, чтобы решить какую-либо задачу с помощью компьютера, необходимо алгоритм ввести в память машины, затем он должен интерпретироваться (т. е. восприниматься и выполнять- ся) аппаратным путем. Запись алгоритма на языке, понятном машине, называется ма- шинной программой, а язык — машинным языком. Для разных типов компьютеров машинные языки разные. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |