 |
Понятие исполнителя алгоритма.
|
|
|
|
Вопросы к экзамену 2011-2012 учебный год
1.Интуитивное понятие алгоритма и его свойства.
2.Словесный способ представления алгоритмов.
3.Графический способ представления алгоритмов.
4.Название элементов блок-схем, их геометрическое представление, переход от одного блока к другому.
5.Базовые структуры блок-схем, их название и геометрическое представление.
6.Выражение базовой структуры “цикл-До” через базовую структуру “Цикл-Пока”.
7.Понятие базисного множества базовых структур. Понятие структурированной блок-схемы.
8.Виды блок-схем (линейные, ветвящиеся, циклические).
9.Понятие транслятора, компилятора и интерпретатора.
10.”Модель – алгоритм – программа” – методологический принцип решения задач на компьютере.
11.Алфавит языка программирования ПаскальАВС, служебные слова и идентификаторы.
12.Понятие константы, объявление константы в программе, типы констант в языке программирования ПаскальАВС.
13. Понятие переменной величины, имена переменных в программе, объявление переменных в программе, типы переменных в языке программирования ПаскальАВС.
14.Простые стандартные типы в языке программирования ПаскальАВС.
15.Стандартные математические функции языка программирования ПаскальАВС, типы аргументов и типы значений функции.
16.Арифметические операции, арифметические выражения, типы значений арифметических выражений в языке ПаскальАВС.
17.Операции отношения, простые и сложные логические выражения в языке программирования ПаскальАВС.
18.Структура программы в языке программирования ПаскальАВС, характеристика каждой части программы.
19.Оператор ввода в языке программирования ПаскальАВС, перевод служебного слова, характеристика списка ввода, порядок работы оператора.
|
|
|
20.Оператор вывода на экран в языке программирования ПаскальАВС, перевод служебного слова, характеристика списка вывода, порядок работы оператора.
21.Вывод нескольких данных на экран в строку и в столбец в языке программирования ПаскальАВС, форматы вывода данных разных типов.
22.Оператор присваивания языка программирования ПаскальАВС, типы величин входящих в оператор, порядок работы и графическое представление.
23.Оператор неполного ветвления языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
24.Оператор полного ветвления языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
25.Оператор выбора языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
26.Понятие цикла, тела цикла и условия цикла в языке программирования ПаскальАВС.
27.Оператор цикла с предусловием языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
28.Оператор цикла с постусловием языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
29.Оператор цикла с известным числом повторений языка программирования ПаскальАВС, характеристика величин оператора, порядок работы и представление в виде базовой структуры.
30.Процедуры пользователя в языке программирования ПаскальАВС, входные и выходные параметры процедуры пользователя.
31.Понятие формальных и фактических параметров в программах с использованием процедур пользователя.
32.Функции пользователя в языке программирования ПаскальАВС, входные и выходные параметры функции пользователя.
|
|
|
33.Понятие формальных и фактических параметров в программах с использованием функций пользователя.
34.Понятие одномерного массива языка программирования ПаскальАВС, элемента массива, размерности массива, объявление одномерного массива в программе
35.Задание элементов одномерного массива в языке программирования ПаскальАВС с помощью функции случайных чисел и путем ввода с клавиатуры.
36.Способы вывода элементов одномерного массива в языке программирования ПаскальАВС на экран в строку и в столбец.
37.Объявление одномерного массива в языке программирования ПаскальАВС, нахождение максимального элемента в массиве.
38.Объявление одномерного массива в языке программирования ПаскальАВС, сортировка элементов массива методом пузырьков.
39.Объявление одномерного массива в языке программирования ПаскальАВС, сортировка элементов массива методом обменов.
40.Объявление одномерного массива в языке программирования ПаскальАВС, нахождение суммы элементов, стоящих на нечетных местах в массиве.
41.Объявление одномерного массива в языке программирования ПаскальАВС, нахождение суммы четных элементов массива.
42.Понятие двумерного массива в языке программирования ПаскальАВС, элемента двумерного массива, объявление двумерного массива в программе.
43.Задание элементов двумерного массива в языке программирования ПаскальАВС с помощью функции случайных чисел.
44.Ввод элементов двумерного массива в языке программирования Паскаль с клавиатуры.
45.Вывод элементов двумерного массива в языке программирования ПаскальАВС в виде матрицы на экран.
46.Понятие размерности двумерного массива в языке программирования ПаскальАВС, прямоугольный и квадратный двумерный масив, свойства элементов лежащих на диагоналях.
47.Объявление двумерного массива в языке программирования ПаскальАВС, нахождение суммы положительных элементов двумерного массива.
48.Объявление двумерного массива в языке программирования ПаскальАВС, нахождение суммы элементов, расположенных на главной диагонали двумерного массива.
49.Объявление строковой переменной в языке программирования ПаскальАВС. Процедуры перевода строковой переменной в числовую переменную и наоборот.
|
|
|
50.Процедуры и функции работы со строковыми переменными в языке программирования ПаскальАВС (длина строки, копирование подстроки, вставка подстроки, нахождение позиции и т.д.).
51.Понятие записи и поля записи в языке программирования ПаскальАВС, объявление переменной типа запись в программе.
52.Массивы записей в языке программирования ПаскальАВС, оператор над записями.
53.Понятие физического и логического файла в языке программирования ПаскальАВС.
54.Понятие типизированного файла данных, объявление файлового типа в программе языка программирования ПаскальАВС.
55.Алгоритм создания типизированного файла данных в языке программирования ПаскальАВС.
56.Понятие типизированного файла данных в языке программирования Паскаль, вывод на экран элементов типизированного файла.
57.Использование данных из типизированного файла данных в языке программирования ПаскальАВС.
Вопрос 1.
Термин «алгоритм» – транскрипция имени великого узбекского математика Мухаммеда аль-Хорезми (Мухаммеда из Хорезма, области нынешнего Узбекистана). Мухаммед аль-Хорезми еще в IX веке разработал правила выполнения четырех действий арифметики. Эти правила до сих пор служат простейшими примерами математических алгоритмов.
Многие годы понятие «алгоритм» использовалось математиками для описания правил решения математических задач. Например, существуют алгоритм вычисления квадратного корня положительного числа, алгоритм нахождения наибольшего общего делителя двух целых чисел.
Однако не следует считать алгоритм чисто математическим понятием. Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи, для описания которых используется тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний. Например, чтобы приготовить вкусное блюдо, вы раскрываете поваренную книгу, отыскиваете рецепт (иными словами, алгоритм приготовления) и, следуя его конкретным указаниям (на два стакана муки – 250 г масла, 1 яйцо,…, тесто разрезать на полоски …, в духовке 20—25 минут…), за конечное число шагов решаете поставленную перед собой задачу.
|
|
|
Носителями алгоритмов являются рецептурные справочники, инструкции по использованию бытовой и технической аппаратуры, медицинские рекомендации, кулинарные книги и многое другое.
В белорусско-русском терминологическом словаре «Информатика» (авторы Быкодоров Ю.А., Кузнецов А.Т., Павловский А.И., Пономаренко В.К., Морозов А.А.) понятие алгоритма трактуется так: «алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных».
Отметим, что все эти фразы не являются определением алгоритма в математическом смысле, а лишь отражают интуитивное понятие алгоритма, сложившееся за долгие годы. Из этого определения вытекают все свойства алгоритмов.
Точное определение понятия алгоритма было разработано в математической логике в 30-40-е годы ХХ века. Примерами могут служить: машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции и другие. На языке каждой из этих математических теорий можно дать математическое определение алгоритма. Более того, последующая математическая практика показала, что эти определения в некотором смысле эквивалентны.
Свойства алгоритмов.
Для решения любой задачи надо знать, что дано и что следует получить, т.е. у задачи есть исходные данные (некие объекты) и искомые результаты. Для получения результатов необходимо знать способ решения задачи, т.е. располагать алгоритмом (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу (получить искомые результаты).
Рассмотрим ряд присущих всем алгоритмам свойств. Перечисленные ниже свойства алгоритмов являются эмпирическими свойствами, т.е. свойствами, подмеченными в результате длительной работы с разнообразными алгоритмами.
1.Выполнение алгоритма разбивается на последовательность законченных действий-шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Этой свойство алгоритма называется дискретностью. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
2. Детерминированность – объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.
Точность – запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнить следующей.
|
|
|
Понятность (для данного исполнителя) – алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнения должно давать один и тот же результат. То есть запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя.
Рассмотрим известный пример «бытового» алгоритма – алгоритм перехода улицы: «Посмотри налево. Если машин нет – дойди до середины улицы. Если есть – подожди, пока они проедут.» и т.д. Представьте себе ситуацию: машина слева есть, но она не едет – у нее меняют колесо. Если вы думаете, что надо ждать, то вы правильно поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.
3. Результативность – каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. При точном исполнении команд алгоритма процесс должен прекратиться за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта, что задача решений не имеет.
4. Конечность – завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
5. Массовость – алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма, т.е. алгоритм пригоден для решения любой задачи из некоторого класса задач. Это свойство не следует понимать, как возможность решить много задач.
Отметим, что для каждого исполнителя набор допустимых действий всегда ограничен – не может существовать исполнителя, для которого любое действие является допустимым. Ограничение над допустимыми действиями означает, что для любого исполнителя имеются задачи, которые нельзя выполнить с его помощью.
Понятие исполнителя алгоритма.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Исполнителем будем называть человека или некоторое устройство, которое способно к восприятию и исполнению команд алгоритма. Перечень команд, которые понимает и может исполнить исполнитель, называют системой команд исполнителя.
Любой алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Исполнение алгоритма зависит от способа представления алгоритма. Если алгоритм представлен в словесной форме записи или как блок-схема, то исполнять такой алгоритм можно вручную. Если алгоритм записан в виде программы, то исполнение передается компьютеру.
Тестирование алгоритма – это проверка алгоритма на его работоспособность. Алгоритм считается работоспособным, если он успешно прошел тестирование. Для тестирования подбираются такие задачи, чтобы:
1.Их можно было решить нетрудно, т.е. устно или с помощью калькулятора.
2.Тестирующие задачи должны охватывать всевозможные варианты исходных данных и решения задачи. Поэтому подбор хороших тестов – это очень важная и трудоемкая работа.
Если ответ, полученный по алгоритму, и ответ теста совпадают, то алгоритм считается работоспособным.
Вопрос 2.
В информатике сложились вполне определенные традиции представления алгоритмов, которые рассчитаны на разных исполнителей. Если исполнителем является человек, то на первое место при описании алгоритма выступают понятность и наглядность. Сюда можно отнести представление алгоритмов в словесной форме, в графической форме, в виде таблиц и т.д. Если же исполнителем алгоритма является некоторый автомат, то на первое место выходит точная формализация записи алгоритма. К таким формам можно отнести представление алгоритмов в виде программ на языках программирования. Рассмотрим каждую из этих форм более подробно.
1.Словесно-формульное описание алгоритма. При словесной форме записи алгоритмов форма записи предложений вообще-то не формализуется, т.е. при записи предложений можно использовать как слова, так и математические символы. Однако предложения при такой записи алгоритма нумеруются, чтобы иметь возможность обратиться к нужному предложению. Также смысл предложения должен пониматься однозначно.
Пример. Записать алгоритм перехода улицы без светофора.
Начало.
1.Подойти к краю дороги.
2.Посмотреть налево.
3.Если есть идущие машины, то пропустить их.
4.Дойти до середины улицы.
5.Посмотреть направо.
6.Если есть идущие машины, то пропустить их.
7.Дойти до края дороги.
8.Конец.
В этом алгоритме все шаги были записаны только с помощью слов русского языка.
Пример. Найти наибольший общий делитель целых чисел А и В по алгоритму Евклида.
Начало.
1.Х=А.
2.У=В.
3.Если Х=У, то перейти к пункту 6.
4.Если Х>У, то Х=Х-У, иначе У=У-Х.
5.Перейти к пункту 3.
6.Наибольший общий делитель чисел А и В равен Х.
7.Конец.
Этот алгоритм кроме слов русского языка использует математическую символику.
Вопрос 3.
Графический способ представления алгоритмов. К этому способу относят блок-схемы, граф-схемы, структурограммы. Мы будем рассматривать представление алгоритмов в виде блок-схем. При таком способе представления алгоритма каждый шаг алгоритма представляется геометрической фигурой, внутри которой записана команда. Такие геометрические фигуры называются блоками. Для указания порядка исполнения блоков используются стрелки. Таким образом, под блок-схемой будем понимать графическое представление последовательности шагов алгоритма, которое наглядно показывает очередность и взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге. Иначе говоря, блок-схема служит для графического представления структуры алгоритма.
Блоки соединяются между собой, образуя более крупные структуры. Каждую структуру можно представить в виде отдельного оператора языка ПаскальАВС.
Представление алгоритмов в виде программ. Если алгоритм записывается для исполнителя автомата, то он должен быть строго формализован. Для формализации придумано множество языков программирования, такие как, Бейсик, Паскаль, Делфи, C++ и др. Запись алгоритма на таком языке является программой, а процесс перевода алгоритма на язык программирования – программированием.
Вопрос 4.
Исходными элементами блок-схемы являются следующие блоки:
1.Блоки начала и конца изображаются овалами, внутри которых записаны соответствующие слова. В блок со словом «конец» входит одна стрелка, из блока со словом «начало» выходит одна стрелка.
2.Блоки обмена информацией (информационный блок):
Блоки обмена информацией используются для ввода исходных значений, т.е. для процесса, при котором исполнитель получает исходные данные; и для вывода информации, т.е. когда исполнитель получив результат выдает его для обозрения. В эти блоки входит одна стрелка и выходит одна стрелка.
3.Функциональные блоки (арифметические):
Внутри функционального блока обычно записывается операция для вычисления какого-либо значения. Изображается прямоугольником, в который входит одна стрелка и выходит также одна стрелка.
4.Блок проверки условия (логический блок):
Блок изображается ромбом, в который входит одна стрелка, а выходят две стрелки, на которых записаны слова «Да» и «Нет».Такой блок используется для определения порядка дальнейшего исполнения алгоритма в зависимости от истинности или ложности условия. Если условие истинно, то управление передается очередному блоку по стрелке «Да». Если условие ложно, то управление передается блоку по стрелке «Нет».
5.Блок слияния изображается кружочком, в который входят две стрелки, а выходит одна.
Вопрос 5.
Из исходных элементов можно составить более крупные кирпичики блок-схем, которые носят название базовые структуры. Каждая базовая структура имеет свое название и должна состоять из блоков определенного вида. Каждая базовая структура имеет всегда один вход и один выход.
1. Следование. Эта базовая структура может состоять из блоков обмена информацией, функциональных блоков, которые должны следовать один за другим. Такую структуру схематически можно изобразить так:
2. Ветвление. Ветвление может быть двух видов:
А) полное ветвление, которое может состоять из блока проверки условия и действий, одно из которых выполняется по стрелке «да», второе – по стрелке «нет». Схематически такую структуру можно представить так:
Отметим, что данная структура имеет один вход и один выход. Словесно эту структуру можно сформулировать следующим образом: «Если условие истинно, то выполнять Действие 1, иначе (если условие ложно) Действие 2».
Б) Неполное ветвление, которое состоит из блока проверки условия и действия только по стрелке «да». Схематически такую структуру можно представить так:
Отметим, что и данная структура имеет один вход и один выход. Словесная формулировка данной структуры: «Если условие истинно, то выполнять Действие1».
3.Структура повторение (цикл). Циклы позволяют многократно выполнять некоторые действия, причем эти действия не нужно многократно записывать, достаточно записать их один раз. Цикл всегда состоит из действий, которые многократно повторяются – это тело цикла, и условия, которое позволяет выйти из цикла. Условие так и называется «условие выхода из цикла». Такая структура должна состоять из условия, т.е. блока проверки условия, и действия – любой базовой структуры.
Данная структура в блок-схемах может быть двух видов:
А) Цикл – пока. Такой цикл еще называют циклом с предусловием, т.к. сначала в структуре идет условие цикла, а затем тело цикла. Схематически такой цикл можно представить так:
Эта структура имеет один вход и один выход. Словесно этот цикл можно сформулировать так: «Пока условие истинно выполнять тело цикла». В этой структуре тело кила может не выполниться ни разу, если с самого начала условие примет значение ложь.
Б) Цикл – до. Такой цикл еще называют циклом с постусловием, т.к. в блок-схеме сначала идет тело цикла, а потом проверка условия. Схематически такую структуру можно представить в следующем виде:
Эта структура имеет один вход и один выход. Такой цикл словесно сформулировать можно так: «Выполнять тело цикла до истинности условия». В этом цикле тело цикла всегда выполнится один раз, потому что сначала идет тело цикла, а затем проверка условия.
Вопрос 6.
Цикл-пока изображается следующим образом:
Цикл-до можно представить с помощью цикла-пока и базовой структуры следование следующим образом:
Так как в цикле-до тело цикла выполнится всегда хотя бы один раз, поэтому можно вынести его за структуру цикла. Затем условие поменять на его отрицание, чтобы истина стала ложью, а ложь истиной, проверить это условие, и нарисовать тело цикла.
Вопрос 7.
В базисное множество базовых структур вошли: следование, ветвление, цикл-пока. Цикл-до в базисное множество не вошел, так как его можно представить через базовую структуру «цикл-пока».
В 1966 году Бом и Якопини доказали следующую теорему:
Любую блок-схему с одним входом и одним выходом можно построить, используя только базисное множество базовых структур { следование, ветвление, цикл-пока }.
Структурированные блок-схемы
Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур, причем базовые структуры могут следовать одна за другой или одна полностью входить как часть другой базовой структуры. Базовые структуры не могут пересекаться.
Для построения структурированных блок-схем алгоритмов нужно иметь систематическую процедуру (т.е. технологию), позволяющую строить блок-схемы по четким правилам. Такая технология имеется и называется она пошаговой детализацией. Суть пошаговой детализации, или еще говорят «проектирование сверху вниз», заключается в том, что задача делится на некоторые подзадачи. Затем в свою очередь каждая подзадача может быть разделена на собственные подзадачи. Этот процесс продолжается до тех пор, пока подзадачу можно представить в виде подзадач. В конечном счете приходим к тому, что каждый шаг выражается какой-то элементарной операцией.
Пример. 1 шаг, 2, 3 шаг
Процесс можно продолжать до тех пор, пока не останутся только простые блоки.
Вопрос 8.
Приведем примеры построения блок-схем алгоритмов для решения некоторых задач.
Задача 1. Даны координаты трех точек A(x1,y1), B(x2,y2), C(x3,y3). Найти расстояния между этими точками.
Блок-схема, которая состоит только из блоков обмена информацией и функциональных блоков называется линейной.
Задача 2. Даны три числа. Определить, могут ли эти числа быть длинами сторон треугольника.
Блок-схема, в которой присутствуют базовые структуры следование и ветвления, называется ветвящейся.
Задача 3. Даны два целых числа А и В. Найти наибольший общий делитель этих чисел по алгоритму Евклида.
Блок-схема, в которой присутствует хотя бы одна циклическая базовая структура, называется циклической.
Вопрос 9.
Уровни языков программирования.
Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. Низкий уровень в данном случае не означает плохой. Имеется в виду, что операторы языка очень близки к машинному коду. Языком низкого уровня является язык ассемблера, который просто представляет каждую команду машинного кода, но не в виде чисел, а с помощью символьных условных обозначений, называемых мнемониками. Так как наборы инструкций для каждой модели процессора отличаются, то конкретной компьютерной архитектуре соответствует свой язык ассемблера, и написанная на нем программа может быть использована только в компьютерах с такой моделью процессора.
С помощью языков низкого уровня создаются очень эффективные и компактные программы, так как разработчик программы получает доступ ко всем возможностям процессора. С другой стороны, при этом требуется очень хорошо понимать устройство компьютера и затрудняется отладка больших приложений. Подобные языки обычно применяются для написания драйверов устройств, модулей стыковки с нестандартным оборудованием.
Языки программирования высокого уровня значительно ближе и понятнее человеку, нежели компьютеру. Особенности конкретных компьютерных архитектур в них не учитываются, поэтому создаваемые программы легко переносимы на другие платформы. Разрабатывать программы на языках высокого уровня значительно проще и допускается меньше ошибок. К языкам высокого уровня можно отнести такие Фортран (Fortran), Бейсик (Basic), Паскаль (Pascal), Си (C), Си++(C++), Джава (Java) и многие другие.
Язык программирования Паскаль был разработан в 1968-1971 годах Никлаусом Виртом. Язык был назван в честь выдающегося французского математика и философа Блеза Паскаля (1623 – 1662) и первоначально создавался для обучения программированию как систематической дисциплине, однако вскоре он стал широко использоваться в профессиональном программировании.
Поскольку текст программы, записанный на языках программирования высокого уровня, непонятен компьютеру, требуется перевести его на машинный язык. Такой перевод программы с языка программирования на язык машинных кодов называется трансляцией, а выполняется специальными программами – трансляторами.
Любой транслятор решает следующие основные задачи:
1.Анализирует транслируемую программу, в частности, определяет, содержит ли она синтаксические ошибки.
2.Генерирует выходную программу на языке машинных команд.
3.Распределяет память для программы (в простейшем случае это заключается в назначении каждому фрагменту программы, переменным, константам, массивам и другим объектам программы адресов памяти).
Существует два вида трансляторов:
1. Интерпретатор – это транслятор, производящий пооператорный перевод в машинные коды, запись в память и выполнение этого одного оператора. Таким образом, интерпретатор переводит в машинные коды один оператор, если нет ошибок, то выполняет его, и только после этого переходит к следующему оператору.
2. Компилятор преобразует (транслирует) всю программу целиком в модуль на машинном языке, после чего программа записывается в память компьютера и только потом исполняется.
Современные системы программирования.
Трудоемкость создания сложных компьютерных программ и разнообразие средств, используемых в процессе разработки программы, компиляции и отладки, привело в 80-х годах ХХ века к созданию интеграции этих средств. В те годы фирма Borland International (США) разработала систему Тurbo Pascal, которую называют интегрированной средой программирования, так как она объединяет в себе возможности ранее разрозненных средств, используемых при разработке программ:
1 .Редактора текстов программ, который позволяет вносить исправления в текст программы, выделять отдельные фрагменты программы, копировать эти фрагменты, удалять, восстанавливать, выделять цветом отдельные слова, поддержка мыши, возможность открытия окон, которые можно перемещать и изменять в размере и т.п.
2. Компилятора программ.
3. Отладчика программ.
4. Справочной системы языка.
Вопрос 10.
Мы уже привыкли к тому, что все большее число задач, возникающих в нашей жизни, мы решаем, используя компьютер. Во-первых, это задачи, требующие громоздких вычислений. Во-вторых, это задачи, которые имеют несколько решений, среди которых необходимо выбрать одно решение, в некотором смысле лучшее. Кроме того, компьютер часто используется для хранения больших объемов информации, которая по мере необходимости извлекается из памяти компьютера по частям или целиком в виде, удобном для пользователя.
Но при решении всех этих задач компьютеру обязательно нужно сформулировать задачу во вполне определенном виде, а также указать последовательность действий, которые приведут к ее решению, причем эта последовательность действий также должна быть записана на специальном языке. Иначе говоря, для решения задачи на компьютере ее нужно специальным образом подготовить.
Методологический принцип решения задач на компьютере можно сформулировать как триаду «модель – алгоритм – программа». Любая практическая задача, как правило, формулируется вначале на естественном языке. Затем человек, пытающийся решить эту задачу, ищет закономерности, позволяющие получить результат, имея заданный набор исходных данных. Как правило, эти закономерности записываются в виде математических соотношений. Совокупность математических соотношений, описывающих данную задачу, называют ее математической моделью.
Поясним сказанное выше примером. Пусть необходимо решить такую задачу. В классе 32 мальчика и 24 девочки, а всего учащихся в классе 100. В какой системе счисления ведется счет и сколько мальчиков и девочек в классе в системе счисления с основанием 10?
1 этап – построение математической модели задачи. Обозначим через х основание неизвестной системы счисления. Тогда 3х+2 – число мальчиков в классе, 2х+4 – число девочек в классе, 1х2+0х+0 – число учеников в классе. В итоге получаем 3х+2+2х+4=х2 или х2-5х-6=0. Итак, моделью нашей задачи является квадратное уравнение х2 – 5х – 6=0.
2 этап – построение алгоритма решения задачи. Алгоритмом решения данной задачи будет являться алгоритм решения квадратного уравнения по известной формуле, которая и будет определять алгоритм решения задачи, если только зафиксировать порядок действий.
Выполнив эту программу для исходных данных р=-5, q=-6, получим результат х1=6, х2=-1. Поскольку в нашем случае основание системы счисления не может быть отрицательным числом, то получили, что основанием системы счисления должно быть число 6. Значит в классе 3*6+2=20 девочек и 2*6+4=16 мальчиков, а всего в классе 62=36 учеников, что верно так как 20+16=36.
Разработка алгоритма по его математической модели.
Когда модель построена и есть уверенность в ее соответствии условию решаемой задачи, необходимо разработать алгоритм решения, пользуясь полученной моделью. Часто одной и той же модели могут соответствовать несколько различных алгоритмов. Например, пусть моделью некоторой задачи является система линейных алгебраических уравнений. Но решить эту систему можно различными методами. Тогда можно сказать, что каждый метод решения системы линейных уравнений определяет свой конкретный алгоритм, хотя модель одна и та же.
Следующий шаг – это преобразование алгоритма в программу для компьютера, т.е. необходимо представить алгоритм в виде последовательности операторов некоторого языка программирования. После этого исходная задача готова для решения на компьютере, необходимо лишь задать начальные данные.
Вернемся к примеру предыдущего пункта и выполним 3 этап – представление алгоритма в виде программы. Запишем алгоритм в виде программы на языке Паскаль.
Алгоритмически неразрешимые задачи.
Неправильно было бы думать, что для любой задачи существует алгоритм ее решения. Известна задача древнегреческой математики – задача о трисекции угла, т.е. о делении угла на три равные части с помощью циркуля и линейки. Неразрешимость этой задачи была доказана в 19 веке алгебраическими методами. В этом примере речь идет о задаче, для которой не существует алгоритма решения в рамках фиксированного набора допустимых действий, в данном случае – построения с помощью циркуля и неразмеченной линейки. Однако отсюда не следует, что эту задачу нельзя решить, применяя какие-либо другие средства. Те же древние греки находили для этого хитроумные способы.
Есть также множество проблем, о которых мы и сейчас не можем сказать, разрешимы они или нет, и если разрешимы, то каким образом. Так известна гипотеза о том, что любое четное число представимо в виде суммы двух простых чисел. Но утверждение это пока не доказано, и не ясно, удастся ли его когда-либо доказать или опровергнуть.
Из сказанного выше вытекает, что для некоторых задач существует несколько алгоритмов их решения, для некоторых задач таких алгоритмов вообще не существует, и, наконец, есть задачи, для которых мы не знаем, существуют или нет алгоритмы их решения.
Вопрос 11.
Языки программирования, как и любые другие языки, имеют свой алфавит. Алфавит языка программирования Pascal состоит из символов трех видов:
1.Прописные и строчные буквы латинского алфавита: A, B, C, D, T, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, причем прописная и строчная буква считаются одним символом.
2.Арабские цифры 0,1,2,3,4,5,6,7,8,9.
3.Специальные символы: (,), [, ], {, }, ’ (апостроф),. (точка),, (запятая),: (двоеточие),; (точка с запятой), + (плюс), - (минус), * (звездочка), / (правый слеш), = (равно), > (больше), < (меньше), _ (знак подчеркивания), пробел (не имеет начертания).
Из символов алфавита составляются слова. Слова бывают двух типов:
-зарезервированные (служебные) – это слова, которые придумали разработчики языка программирования, вложили в них определенный смысл, который остается постоянным для всех программ языка Паскаль. Служебных слов не очень много:
| and | array | as | begin |
| break | case | class | const |
| constructor | continue | destructor | div |
| do | downto | else | end |
| exit | external | externalsync | file |
| finalization | for | forward | function |
| if | in | inherited | initialization |
| is | mod | not | of |
| or | private | procedure | program |
| property | protected | public | |
| record | repeat | set | shl |
| shr | sizeof | string | |
| then | to | type | unit |
| until | uses | var | while |
| with | xor |
-идентификаторы (имена) – это слова, котор
|
|
|
