Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I — различия между версиями

Текущая версия на 09:40, 24 января 2014

К основной странице курса

Алгоритм

Алгоритм — набор команд, определяющих порядок действий для решения поставленной задачи.

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

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

Свойства алгоритма

• Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
• Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
• Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
• Результативность — после выполнения алгоритма известно, что считать результатом.
• Массовость — применимость алгоритма ко множеству исходных данных.

Пример алгоритма.

Дано: x, y, z.

Найти max

Алгоритм 1. (словесное описание)

Если x>y и x>z, то максимум — это x
Если y>x и y>z, то максимум — это y
Если z>x и z>y, то максимум — это z

Алгоритм 2. (псевдокод)

max := x
Если y<max то max := y
Если z<max то max := z

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

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

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

1. Словесный

2. Псевдокод

3. Блок-схемы

Пример. А.2., представленный блок-схемой.

4. Язык программирования (ЯП)

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

Основные характеристики алгоритма

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

Основные характеристики программы

Те же, что и у алгоритма, а также:

• понятность при чтении
• модифицируемость (легкость изменения кода)
• масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
• безопасность

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

Обзор современных языков программирования

(самостоятельно на форуме)

Язык программирования PascalABC.NET

Правила записи программ на PascalABC.NET

Шпаргалка

Пример программы, вычисляющей длину и площадь круга

program First; // заголовок программы – необязательная строка
{ Программа вычисления длины окружности и площади круга 
  Автор: Михалкович С.С. Дата написания: 2.09.08 }
const Pi = 3.14;
var
  r: real;   // входные данные - радиус круга
  S,C: real; (* выходные данные - площадь круга и длина окружности *)
begin
  write('Введите радиус окружности: ');
  readln(r);
  S := Pi*r*r;
  C := 2*Pi*r;
  writeln('Длина окружности равна ',С);
  writeln('Площадь круга равна ',S);
end.

Структура программы на языке Паскаль

Заголовок программы
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
begin
  операторы (разделяются ;)
end.

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

Система программирования PascalABC.NET

Как скачать, инсталлировать. (сайт системы программирования PascalABC.NET)

Общая характеристика PascalABC.NET.

Отличия языка PascalABC.NET от обычного языка Паскаль.

Компиляторы и интерпретаторы

Схема компиляции в машинный код

Схема компиляции в промежуточный код. JIT-компиляция

Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения

Синтаксис - правила записи конструкций, семантика - смысл конструкций.

Синтаксис и семантика ЯП

// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.

Определения

Синтаксис — формальные правила описания конструкций ЯП.

Семантика — описывает смысл конструкций ЯП, а также задает ряд ограничений.

Способы описания синтаксиса

• БНФ (Бэкуса-Наура формы, 1960, Алгол-60).

Примеры.

<цифра> ::= 0|1|2|3|4|5|6|7|8|9
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
<список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов>

0, 1, ... 9

называют терминалами (лексемами) — это "конечные символы", т.е. по умолчанию известные в ЯП.

<цифра>

так называемый нетерминал (нетерминальный символ).

Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется рекурсивным (как определение нетерминала <идентификатор>)

• РБНФ (Расширенные БНФ)

[] — 0 или 1 повторение.

{} — 0 и более повторений

Пример.

<идентификатор> ::= <буква> {<буква> | <цифра>}

• Синтаксические диаграммы (Вирт, Паскаль)

Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.

Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.

Замечание 1. Способы 1-3 эквивалентны.

Замечание 2. Синтаксис определяет лексемы языка.

Лексемы Паскаля

1. спецсимволы: := += *
2. ключевые слова (begin, end, if, for)
3. идентификаторы (a, b1)
4. константы (2, 'ABC', #5)
5. комментарии (3 вида)

{...}

(*...*)

//...

Переменные и их описание

Основные сведения

Переменная — это ячейка памяти компьютера, имеющая имя и тип.

Тип определяет размер переменной и множество принимаемых ею значений.

В языке Pascal любая переменная перед использованием должна быть описана.
Обычно переменные описываются в разделе описаний.

<xh4> Синтаксис в виде РБНФ </xh4>

<программа> ::= [program <имя>;] 
               <раздел описаний> 
               begin
                 <операторы>
               end.
<операторы> ::= <оператор>{; <оператор>}
<раздел описаний> ::= {<секция раздела описаний>}
<секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...

Пример секции описания переменных.

var
  a,b: real;
  i: integer;

<секция описания переменных> ::= var<подсекция>{< подсекция>}
<подсекция> ::= <список имен>: <тип>;
<список имен> ::= <имя>{,<имя>}
<тип> ::= <имя>

Внутриблочные переменные

В PascalABC.NET возможно внутриблочное описание переменных:

begin
  var i,j: integer;
  var r: real := 5.2;
  var Pi := 3.14;

В последнем случае происходит автоопределение типов.

Основные типы

• Целые

integer (4 байта)

int64 (8)

byte (1)

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

real (8)

• Символьные

char (2 байта — Unicode)

• Строковые

string

string[200]

shortstring = string[255]

• Логический

boolean (1) [True False]