Вопрос №1

Понятие алгоритма и его свойства. Способы задания и описания алгоритмов.

Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

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

Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение опред-х этими исходными данными результатов. Если вычислительный процесс заканчивается получением результатов, то соответствующий алгоритм применим к рассматриваемой совокупности исходных данных, иначе - неприменим. Любой применимый алгоритм обладает следующими основными свойствами:

• результативностью;

• определенностью;

• массовостью;

• дискретностью;

• конечностью.

Результативность - получение результата после выполнения конечного количества операций.

Определенность –состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств.

Массовость -применение алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных.

Дискретность - разбиение алгоритма на конечную последовательность действий или шагов при его выполнении.

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

Способы описания алгоритмов:

• словесно-формульный;

• графический(блок-схемы);

• программы;

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

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

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

Вопрос №3

Типовые этапы разработки алгоритмов. Этапы решения задач на ЭВМ.

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

Этапы подготовки и решения реальных задач :

Типовые этапы разработки алгоритмов:

• описание общего замысла алгоритма;

• формализация задачи;

• разработка обобщенной схемы алгоритма;

• разработка отдельных блоков алгоритма;

• стыковка блоков;

• определение возможности использования стандартных блоков;

• разработка блоков логического контроля;

• оптимизация схемы алгоритма;

• уточнение параметров;

• оценка машинного ресурса.

Этапы решения задач на ЭВМ:

1. постановка задачи;

2. физическое моделирование;

3. математическое или информационное моделирование;

4. алгоритмизация задач;

5. разработка программы;

6. тестирование и отладка программы;

7. анализ результата;

Вопрос №2

Основные алгоритмические структуры: линейная, ветвления, циклы.

Одним из свойств алгоритма является дискретность — возможность расчленения процесса вычислений, предписанных алгоритмом, на отдельные этапы, возможность выделения участков программы с определенной структурой. Можно выделить и наглядно представить графически три простейшие структуры:

• последовательность двух или более операций;

• выбор направления;

• повторение.

Любой вычислительный процесс может быть представлен как комбинация этих элементарных алгоритмических структур. Соответственно, вычислительные процессы, выполняемые на ЭВМ по заданной программе, можно разделить на три основных вида:

• линейные;

• ветвящиеся;

• циклические.

Линейный -вычислительный процесс, в котором операции выполняются последовательно, в порядке их записи. Каждая операция является самостоятельной, независимой от каких-либо условий. На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.

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

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

Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» — условие выполнено и «нет» — условие не выполнено.

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

Циклические - программы, содержащие циклы. Цикл — это многократно повторяемый участок программы.

В зависимости от расположения проверки условия окончания цикла различают циклы с предусловием и постусловием. Для цикла с постусловием тело цикла выполняется как минимум один раз, так как сначала производятся вычисления, а затем проверяется условие выхода из цикла. В случае цикла с предусловием, тело цикла может не выполниться ни разу в случае, если сразу соблюдается условие выхода.

Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

Вопрос №5

Основные понятия алгоритмического языка.

Алгоритмический язык содержит:

• слово(элементарная конструкция);

• словосочетание(выражение);

• предложение(оператор).

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

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

1. 26 латинских строчных и прописных букв, подчеркивание

2. 10 цифр:

3. Знаки операций:+ - * / = <> < > <= >= := @

4. Ограничители: . , ' () [ ] (. .) { } (* *) .. : ;

5. Спецификаторы:^ # $

6. Служебные (зарезервированные) слова.

Кроме перечисленных, в набор осн-х символов входит пробел. Пробелы нельзя исп-ть внутри сдвоенных символов и зарезервированных слов.

Вопрос №4

Программа на языке высокого уровня. Этапы процесса обработки программы на языке Pascal.

Программирование как процесс создания программы формально состоит из выбора языка программирования и замены элементов блок-схемы алгоритма соответствующими операторами. Правильная программа на алгоритмическом языке представляет собой формальную запись конечной последовательности действий, приводящих к решению поставленной задачи. Программа, написанная непосредственно в процессорных кодах, представляет собой последовательность из 0 и 1. Команды машинного языка в большинстве случаев состоят из двух частей — из кода операции (указания процессору, что сделать), и из операндов (указания, с чем нужно сделать операцию). Поскольку многие программы выполняют одни и те же действия (ввод/вывод данных, вычисление математических функций и т.п.), были организованы библиотеки подпрограмм, где алгоритмы этих действий хранятся уже в скомпилированном виде.

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

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

- ввод текста;

- трансляция;

- отладка.

Этапы процесса обработки программы на языке Pascal:

Вопрос №6

Структура программы языка ТР.

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

Заголовок программы содержит имя программы, например:

Program PRIM;

Описания могут включать в себя раздел подключаемых библиотек (модулей), раздел описания меток, раздел описания констант, раздел описания типов, раздел описания переменных, раздел описания процедур и функций.

Раздел описания модулей определяется служебным словом USES и содержит имена подключаемых модулей (библиотек) как входящих в состав системы Турбо Паскаль, так и написанных пользователем. Раздел описания модулей должен быть первым среди разделов описаний. Имена модулей отделяются друг от друга запятыми:

uses CRT, Graph;

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

label 3, 471, 29, Quit;

Описание констант позволяет использовать имена как синонимы констант, их необходимо определить в разделе описаний констант:

- литералы(их тип опред-ся по их внешнему виду): D:=3(целый); С:=’с’(символьный).

- типизованная форма: const K= 1024; MAX= 16384; M:=N+1; A=2.3.

В разделе описания переменных необходимо определить тип всех переменных, используемых в программе:

Var P,Q,R: Integer;
    A,B: Char;
    F1,F2: Boolean;

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

Раздел операторов представляет собой составной оператор, который содержит между служебными словами

begin.......end

последовательность операторов. Операторы отделяются друг от друга символом ;.

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

Вопрос №7

Раздел описания констант, переменных, операторов.

Описание констант позволяет использовать имена как синонимы констант, их необходимо определить в разделе описаний констант:

- литералы(их тип опред-ся по их внешнему виду): D:=3(целый); С:=’с’(символьный).

- типизованная форма: const K= 1024; MAX= 16384; M:=N+1; A=2.3.

В разделе описания переменных необходимо определить тип всех переменных, используемых в программе:

Var P,Q,R: Integer;
    A,B: Char;
    F1,F2: Boolean;

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

Раздел операторов представляет собой составной оператор, который содержит между служебными словами

begin.......end

последовательность операторов. Операторы отделяются друг от друга символом ;.

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

Кроме описаний и операторов Паскаль-программа может содержать комментарии, которые представляют собой произвольную последовательность символов, расположенную между открывающей скобкой комментариев { и закрывающей скобкой комментариев }.

Текст Паскаль-программы может содержать ключи компиляции, которые позволяют управлять режимом компиляции. Синтаксически ключи компиляции записываются как комментарии. Ключ компиляции содержит символ $ и букву-ключ с последующим знаком + (включить режим) или – (выключить режим). Например:

{$E+} – эмулировать математический сопроцессор;

{$F+} – формировать дальний тип вызова процедур и функций;

{$N+} – использовать математический сопроцессор;

{$R+} – проверять выход за границы диапазонов.

Некоторые ключи компиляции могут содержать параметр, например:

{$I имя файла} – включить в текст компилируемой программы названный файл.

Вопрос №8

Концепция типа данных. Структура типов языка ТР.

В языке Паскаль существует правило: тип явно задается в описании переменной или функции, которое предшествует их использованию. Концепция типа языка Паскаль имеет следующие основные свойства:

– любой тип данных определяет множество значений, к которому принадлежит константа, которые может принимать переменная или выражение, или вырабатывать операция или функция;

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

– каждая операция или функция требует аргументов фиксированного типа и выдает результат фиксированного типа.

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

Тип определяет:

– возможные значения переменных, констант, функций, выражений, принадлежащих к данному типу;

– внутреннюю форму представления данных в ЭВМ;

– операции и функции, которые могут выполняться над величинами, принадлежащими к данному типу.

Кроме перечисленных, Турбо Паскаль включает еще два типа – процедурный и объектный.

Из группы скалярных типов можно выделить порядковые типы, которые характеризуются следующими свойствами:

– все возможные значения порядкового типа представляют собой ограниченное упорядоченное множество;

– к любому порядковому типу может быть применена стандартная функция Ord, которая в качестве результата возвращает порядковый номер конкретного значения в данном типе;

– к любому порядковому типу могут быть применены стандартные функции Pred и Succ, которые возвращают предыдущее и последующее значения соответственно;

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

В языке Паскаль введены понятия эквивалентности и совместимости типов. Два типа Т1 и Т2 являются эквивалентными (идентичными), если выполняется одно из двух условий:

– Т1 и Т2 представляют собой одно и то же имя типа;

– тип Т2 описан с использованием типа Т1 с помощью равенства или последовательности равенств. Например:

Type
   T1 = Integer;
   T2 = T1;
   T3 = T2;

Менее строгие ограничения определены совместимостью типов. Например, типы являются совместимыми, если:

– они эквивалентны;

– являются оба либо целыми, либо действительными;

– один тип - интервальный, другой – его базовый;

– оба интервальные с общим базовым;

– один тип - строковый, другой - символьный.

В Турбо Паскаль ограничения на совместимость типов можно обойти с помощью приведения типов

Имя_Типа (переменная или значение).

Integer('Z')

Byte(534)

Вопрос №9

Стандартные числовые типы языка ТР.

Стандартные числовые типы включают целые, действительные.

Целые:

Тип	Диапозон	Обьем памяти
Shorting	-128…127	1Б
Byte	0…255	1Б
Integer	-32628…32627	2Б
Word	0…65532	2Б
Longint	-2147483048.2147783647	4Б

Вещественные:

Тип	Диапазон значений	Кол-во цифр	Обьем память
Real	2.9e-39 ... 1.7e+38	11	6
Single	1.5e-45 ... 3.4e+38	7	4
Double	5.0e-324 ... 1.7e+308	15	8
Extended	3.4e-4932...1.1e+4932	19	10
Comp	-9.2e+18... 9.2e+18	19	8

Вопрос №10

Операции языка ТР.

Операция	Действие	Тип операндов	Тип результата
+	Сложение	integer, real	integer, real
—	Вычитание	integer, real	integer, real
*	Умножение	integer, real	integer, real
/	Деление	integer, real	real
Div	Деление нацело	integer	integer
Mod	Остаток от деления	integer	integer