Понятие алгоритма. Основные свойства алгоритмов

Понятие алгоритма. Основные свойства алгоритмов

Алгоритм — заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов

Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя.

Основные свойства алгоритмов следующие: 1) понятность; 2) дискретность; 3) определенность; 4)результативность; 5) массовость.

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

2. Дискpетность (прерывность, раздельность) — алгоритм должен представлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

3. Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.

4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения,

5. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными.

Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма

(далее рассказать Формы представления алгоритмов).

Структура программы на языке Pascal

Язык программирования – это совокупность соглашений и правил для описания алгоритма выполнения задачи компьютером. Используя язык программирования, программист создает описание алгоритма (как правило, в виде текстового файла), а затем компилятор на основе этого файла создает последовательность инструкций процессору.

Программа в Pascal состоит из двух разделов

1. Раздел описаний. – указываются все необходимые компоненты для программы.

2. Раздел операторов – описываются все вычисления и операции.

В общем случае программа на языке Pascal имеет следующий вид:

program <имя>;	название программы
uses …	перечисление используемых стандартных модулей
const …	описание используемых констант
var …	описание переменных
function …	описание функций
procedure …	описание процедур
begin	начало собственно программы
операторы;	тело программы
end.	обозначение конца программы

Каждая законченная порция сведений (оператор) отделяется от других точкой с запятой «;»

Раздел описания переменных имеет вид: Var <Идентификатор>: <тип>;

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

Процедуры в языке Pascal

Подпрограмма – это часть программы, оформленная как самостоятельная (автономная) программная единица и выполняющая определенную задачу.

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

Структура описания процедуры и функции такая же, как и обычной программы: заголовок, раздел описаний и раздел операторов. Заголовок процедур и функций имеет вид: procedure <имя>(<параметры>);

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

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

При вызове подпрограмму ей передаются значения переменных. Эти значения называются фактическими параметрами. Фактические параметры подставляются вместо формальных при вызове подпрограммы. Их количество, последовательность и типы должны строго соответствовать количеству и типам формальных параметров.

(далее рассказать о передаче параметров по значению и по ссылке)

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

Функции в языке Pascal

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

Заголовок функций имеет вид: function <имя>(<параметры>):тип_результата;

Заголовок функции (только заголовок) рекомендуется помещать в раздел описаний программы.

Заголовок функции определяет идентификатор функции, формальные параметры (если есть), и тип результата функции. Допустимы порядковые, вещественные, строковые, логические и указательные типы результата.

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

Функция содержит:

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

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

Пример заголовка функции: function Func(a:integer; var b:real; var sum:real):boolean; В теле такой функции должен присутствовать хотя бы один оператор присваивания значения переменной Func, например:

Func:=false; if sum>b*b then Func:=true;

В языке Pascal нет стандартной функции возведения действительного числа в степень с действительным показателем. Поэтому программисты часто создают функцию

function power(x,b: double):double;

begin

power:=exp(b*ln(x));

end;

Пример вызова функции: z:=Power(x, 0.333) – соответствует извлечению кубического корня из x.

Методы сортировки массивов

Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Существует много методов сортировки массивов. Эффективность метода определяют путем сравнения времени сортировки и размера массива.

Простейшими методами сортировки являются метод пузырька (обменами) и метод отбора (последовательных минимумов). Время сортировки массивов этими методами пропорционально квадрату размера массива (т.е. при увеличении размера массива в 10 раз время сортировки увеличивается в среднем в 100 раз).

(быть готовым рассказать алгоритм одного из этих методов)

Более сложными являются алгоритмы: «быстрая сортировка» (Quick Sort), сортировка «кучей» (Heap Sort), сортировка слиянием, пирамидальная сортировка. Время сортировки этими методами пропорционально N· log N, где N – размер массива.

Идея метода сортировки вставками: последовательное пополнение ранее упорядоченных элементов. На первом шаге сортируются два первые элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным добавляется четвертый, который занимает свое место в четверке и т.д. Примерно так игроки упорядочивают свои карты при сдаче их по одной.

Идея метода быстрой сортировки (Quick Sort): Сначала выбирается средний элемент в сортируемом массиве. Все, что больше этого элемента переносится в правую часть массива, а все, что меньше – в левую. После первого шага средний элемент оказывается на своем месте. Затем аналогичная процедура повторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемого фрагмента массива уменьшается вдвое.

Строки в языке Pascal.

< Дать определение типа данных >

Для работы с текстом в языке Turbo Pascal был введён специальный тип данных string, предназначенный для работы с фрагментами текста - строками (цепочками символов).

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

Например: VAR s1: string[70]; Если размер строки не указан, он считается равным 255.

Значение строковой переменной может быть присвоено оператором присваивания, либо введено оператором ввода: s1:= 'Пример строки.';

< Для продвинутых: рассказать о внутреннем представлении строк в Pascal >

< Далее рассказать об операциях над строками >

Нормальные формы баз данных

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

Отношение находится в первой нормальной форме, если:1) отсутствуют одинаковые кортежи(записи);2) каждый атрибут является атомарным (то есть не содержит значений типа списка и т.д.).

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

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

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

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

Обработка событий

Окно Инспектора объектов имеет две закладки: Properties (Свойства) и Events (События).

Событие (Event) – это то, что происходит во время работы программы. В Lazarus каждому событию присвоено имя. Например, щелчок кнопкой мыши – это событие OnClick, двойной щелчок мышью событие OnDblClick

Обработка требует какого-либо действия в ответ на событие. Многие компоненты уже имеют готовые реакции на стандартные события. В Lazarus обработка события определяется специальной процедурой, которую должен написать программист.

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

Синтаксис процедур обработки события такой же, как и для всех процедур на языке Pascal.

Для некоторых стандартных событий среда Lazarus имеет уже готовые обработчики. Например, для кнопки Close не требуется ввод процедуры обработки щелчка на кнопке – среда генерирует ее автоматически.

Компонент StringGrid

Значок компонента StringGrid (Решетка, Таблица) находится на вкладке Additional ( Дополнительный ). Компонент StringGrid представляет собой таблицу, ячейки которой содержат строки символов. В таблице перечислены некоторые свойства компонента StringGrid.

Name	Имя компонента. Используется в программе для доступа к свойствам компонента
ColCount	Количество колонок таблицы
RowCount	Количество строк таблицы
Cells	Соответствующий таблице двумерный массив. Ячейка таблицы, находящаяся на пересечении столбца номер col и строки номер row определяется элементом cells[col,row]
FixedCols	Количество зафиксированных слева колонок таблицы. Зафиксированные колонки выделяются цветом и при горизонтальной прокрутке таблицы остаются на месте
FixedRows	Количество зафиксированных сверху строк таблицы. Зафиксированные строки выделяются цветом и при вертикальной прокрутке таблицы остаются на месте
Options. goEditing	Признак допустимости редактирования содержимого ячеек таблицы. True — редактирование разрешено, False — запрещено

Компонент StringGrid часто используется для вывода таблиц и двумерных массивов. Следует помнить, что в обозначении элемента таблицы cells[col,row] первый индекс определяет столбец, а второй – строку. Кроме того, массив Cells – это массив строк, а не чисел. Поэтому при занесении чисел в таблицу и считывании чисел из таблицы необходимо использовать функции преобразования.

< Кратко: какие функции преобразования строки в число и числа в строку вы знаете? >

Оператор SELECT языка SQL

Оператор SQL SELECT является одним из основных операторов языка SQL. Именно с его помощью происходит выборка значений, хранящихся в базе данных. В структуру запроса оператора SQL SELECT могут быть включены многие дополнительные операторы: уточняющие условие выборки, производящие группировку, сортировку выходных значений и т.д.

SELECT список_полей FROM имя_таблицы

[WHERE условие] [GROUP BY условие] [HAVING условие] [ORDER BY условие];

SELECT Ключевое слово, которое сообщает базе данных о том, что оператор является запросом. Все запросы начинаются с этого слова, за ним следует пробел.

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

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

WHERE условие задает дополнительные условия выборки.

GROUP BY условие используют для группирования результата по столбцу или по нескольким столбцам.

HAVING условие включают в запрос для задания условия агрегатных функций.

ORDER BY условие используется для сортировки значений.

Код в квадратных скобках является не обязательным в операторе SELECT. Он необходим для более точного определения запроса.

SQL код является регистронезависимым. Это означает, что запись SELECT можно написать как select. СУБД не отличит эти две записи, однако рекомендуется все операторы SQL писать прописными буквами, чтобы его легко можно было отличить от другого кода.

Порядок следования ключевых слов изменять нельзя: если GROUP BY присутствует, то должно находиться после WHERE и перед HAVING.

< Привести пример выборки >

Понятие алгоритма. Основные свойства алгоритмов

Алгоритм — заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов

Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя.

Основные свойства алгоритмов следующие: 1) понятность; 2) дискретность; 3) определенность; 4)результативность; 5) массовость.

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

2. Дискpетность (прерывность, раздельность) — алгоритм должен представлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

3. Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.

4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения,

5. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными.

Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма

(далее рассказать Формы представления алгоритмов).