2)Понятие алгоритма, требования к алгоритмам и способы записи. Разработка алгоритмов на основе структурного подхода, примеры.

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

Требования.

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

2. Детерминированность - определенность (операция на каждом шаге должна понимать однозначно).

3. Результативность - получение результата за конечное число шагов.

4. Массовость - возможность использования данного алгоритма для решения целого класса задач при различных исходных данных.

5. Понятность - понятная запись для исполнителя.

6. Эффективность. Алгоритм должен приводить к результату за как можно короткое время и использовать минимум ресурсов ЭВМ (памяти).

7. Требование конечности процесса реализации. Алгоритм д. заканчиваться.

Способы записи:

-словесный (неформальные записи на предварительном этапе);

-блок-схема;

- запись в виде программы, на одном из языков программирования.

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

3 осн. типа моделей:

1-Машины Тьюринга. В 1936 задачу уточнения понятия алг-ма и далее с его помощью опр-ть класс вычислимых ф-ий решили независимо др от др Пост и Тьюринг. Их осн идеей явл идея сущест-я некот машины, кот могла бы реализ-ть любой алгоритмич процесс. МТ состоит из следующих элементов:

2-Рекурсия – способ задания ф-ции, при к-м знач-е определяемой ф-ции для произвольных значений аргумента выражается через знач-е определяемой ф-ции для меньших аргументов (ф-я задается через обращение к самой себе). Рекурсивные ф-ции – арифм. или целочисл. ф-ции. Совок-ть таких ф-ций наз-ся множ-м рекурс-х ф-й. Ф-я, при к-й часть обл. опред-я соотносится с частью обл. знач-я назыв-ся частично-определенной ф-й. Гипотеза Клини: все частично-опред. ф-ции, вычисляемые посредством алгоритмов, явл-ся частично-рекурс-ми.

3-алгоритмы Маркова. Нормальные алгоритмы Маркова (НАМ) – это алгоритмическая система, основанная на соответствие между словами в абстрактном алфавите и включает элементарные операторы (ЭО) и распознаватели (ЭР).

ЭО – это преобразование с помощью последующего выполнения который реализует алгоритм.

ЭР – это оператор для распознавания тех или иных свойств перерабатываемой алгоритмом информации.

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

- легкочитаемость,

- легкопроверяемость,

- легкомодифицируемость.

Принципы СП:

-нисходящее проектирование «сверху-вниз»;

-модульное программирование;

-структурное кодирование (собственно программирование)

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

На 1ом этапе представить задачу в виде одного блока или словесно в виде одного предложения.

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

3.Типы и структуры данных, ср-ва для работы с ними в АЯП, примеры.

Данные – это об-ты, обраб-мые алг-мами.

Тип данных – мн-во значений, кот. может принимать переменная. (Напр. Boolean 0|1).

Структуры данных – набор перем-х, возможно, различных типов данных, объединённых определ-м образом.

1) Простые = скалярные [порядковые (цел, логич, символьн, перечисляем, интервальн) и веществ] 2) Структурир. (массивы, мн-ва, записи, файлы, строки, стек, оч-дь, деревья, графы) 3) указатели

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

1. Целый Значения: цел + - в некот диапазоне Операции: арифм. опер-ии с цел числами +-*/ mod div ><= sqrt, sqr, abs… Внутр представление: формат с фиксир точкой. целый тип (Shortint -короткое целое со знаком, диапозон (-128..127); Integer- целое со знаком, диапазон (-32768..32767); Longint-длинное целое со знаком,диапозон(-2147483648..2147483647) Byte-короткое целое без знака, диапазон(0..255) Word-целое без знака,диапозон(0..65535));

2. Веществ (real single, double, extended) Значения: целые и дробные ч в некот диапазоне. Напр., 2.5; -0.01; 45.0; 3.6*10⁹ Операции: +-/* ><= Внутр представление: формат с плав точкой. вещественный тип – для представления действительных чисел. Веществ числа отлич др от др точностью представления.

Real – позволяет представить число с мах точностью 12 знаков после запятой.

Double – 16 знаков

Extended – 18 знаков.

Все эти числа предст-ся в виде знаковых типов хранящих мантиссу и порядок числа. Пр: 123,456 >> 0,123456*10³ 3-порядок мантиссы, мантисса – разряды после запятой.

3. Логич Значения: true false Операции: AND OR NOT = ≠ Внутр представление: 1 бит: 1 true, 0 false ) логический – для представления логич инфы. В яз pascal дан тип наз-ся булевым , false – 0, True – 1. в памяти данный тип занимает 4 байта.

4. Симв Значения:  символы компьют алфавита g+$7 Операции: оп-ции отношений, конкатенация Внутр представление: код таб-цы символьной кодировки. 1 симв=1байт

5. Перечисл. type FAM=(Ivanov, Petrov, Sidorov) Var student: FAM

6. Отрезковый строится на основе простых типов, кроме веществ. путем огран-я диап-на Var ind: [1..10]; (или = Type t=1..10 Var ind: t;)

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

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

Средства для работы с данными – операции, выражения и команды. Операция – простейшее законченное дей-е над данными. Выр-е – запись в алг-ме (прог-ме), опред-щая послед-сть операций д. вычисления некоторой величины. Команда – входящее в запись алгоритма типовое предписание исполнителю выполнить некоторое законченное действие. Команды :=, вв/выв наз-ся простыми. Команды цикла и ветвления – составными, структурными.

Ф-ции бывают стандартные или нестанд. К станд. обращаются по имени с указанием аргумента. Существуют числовые и символьные функции. Round, trunc

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

Массивы – это упоряд. совок-ть данных одного типа, имеющих одно и то же имя. Хар-ся типом компонентов структуры и взаимосвязью между компонентами стр-ры. Эл-ты массива им. номера. Одномерн м-в – линейная таб-ца, или вектор. Двум. м-в прямоуг. таб-ца, или матрица. М-в хар-ся именем (=идентификатор), размером (к-во эл-тов м-ва), разм-стью (форма компоновки м-ва).

A: array[1..10] of Integer;

Очередь – стр-ра данных, представленная в виде списка Эл-тов, доступ к которым д. чтения возможен только в начале списка, а для записи – только с конца. Начало списка front, конец rear. Число эл-тов, хран-ся в очереди, определяет ее длину: length=rear-front+1. Оч-дь является одной из самых часто используемых стр-р данных ВТ. С ее помощью реализуется многозадачность в ОС Windows и Linux. Микропроцессор обраб-ет приложения в соотв-ии с очередью. Также организуется печать док-тов. Используется в быстрых алгоритмах сортировки эл-тов мн-ва и прохождении деревьев.

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

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

3) строковый - для хранения символьной инф-ции. В pascal исп-ся сл типы: короткие строки, длинные, широкие, указательные. Наиб часто использ-м типом явл string . В яз pascal 7.0 этот тип соответ-т типу коротк строки, в более поздних версиях длинным.

5) Структуриров-е типы данных – массив(array), запись (record ), файл (file).

Массив – объед-е однотипных элем-в в памяти.

A: array[1..10] of Integer;

Запись – объед разнотипн эл-в в памяти

(record <имя записи>

<переменная 1>:<тип 1>;

<переменная 2>:<тип 2>;

End;

Файл – объед разнотипн или однотипн эл-в на внеш носителе инф-ции. (опис-ся сл образом: <идентификатор >: FILE of <тип данных>;