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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin)
 
(не показаны 62 промежуточные версии 4 участников)
Строка 1: Строка 1:
 +
[[Категория:Основы программирования]]
 +
[[Страница курса Основы программирования|К основной странице курса]]
 +
 
== Алгоритм ==
 
== Алгоритм ==
=== Свойства алгоритма ===
+
[http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC '''Алгоритм'''] — набор команд, определяющих порядок действий для решения поставленной задачи.
* ''дискретность''
 
* ''элементарность команд''
 
* ''определенность команд''
 
:каждая команда имеет четкое однозначное значение
 
* ''конечность''
 
:каждый А. должен когда-то завершаться при любом наборе исходных данных
 
* ''результативность''
 
:после выполнения А. известно, что считать результатом
 
* ''массовость'' 
 
:применимость ко множеству исходных данных
 
  
=== Связанные понятия ===
+
С алгоритмом всегда связан '''исполнитель алгоритма''' - устройство, имеющее систему команд.
'''Спецификация задачи''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
 
  
'''Исполнитель алгоритма''' устройство, имеющее некоторую систему команд, и способное их исполнять.
+
В частности, процессор компьютера выступает исполнителем машинных команд.
:'''''Процессор''''' исполнитель машинных кодов.
+
=== Свойства алгоритма ===
 +
* Дискретность алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
 +
* Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
 +
* Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
 +
* Результативность — после выполнения алгоритма известно, что считать результатом.
 +
* Массовость применимость алгоритма ко множеству исходных данных.
  
''<u>Пример</u>.''
+
''<u>Пример алгоритма</u>.''
 
:Дано: <tt>x, y, z</tt>.  
 
:Дано: <tt>x, y, z</tt>.  
 
:Найти <tt>max</tt>
 
:Найти <tt>max</tt>
Строка 24: Строка 21:
 
Алгоритм 1. (''словесное описание'')
 
Алгоритм 1. (''словесное описание'')
  
  Если x>y и x>z, то максимум - это x
+
  Если x>y и x>z, то максимум это x
  Если y>x и y>z, то максимум - это y
+
  Если y>x и y>z, то максимум это y
  Если z>x и z>y, то максимум - это z
+
  Если z>x и z>y, то максимум это z
  
 
Алгоритм 2. (''псевдокод'')
 
Алгоритм 2. (''псевдокод'')
Строка 35: Строка 32:
  
 
'''Эквивалентными''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.
 
'''Эквивалентными''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.
 +
Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.
 +
 +
 +
'''Спецификация задачи''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
  
 
=== Способы описания алгоритмов ===
 
=== Способы описания алгоритмов ===
* ''словесный''
+
1. ''Словесный''
* ''псевдокод''
+
 
* ''блок-схемы''
+
2. ''Псевдокод''
 +
 
 +
3. ''Блок-схемы''
 +
 
 +
''<u>Пример</u>.'' А.2., представленный блок-схемой.
 +
[[Изображение:max_flowchart.png|none]]
 +
 
 +
4. ''Язык программирования (ЯП)''
 +
 
 +
Для языка программирования команды алгоритма называются '''''операторами''''' или '''''инструкциями'''''.
 +
 
 +
=== Основные характеристики алгоритма===
 +
 
 +
* правильность работы
 +
* скорость выполнения
 +
* объем занимаемой памяти
 +
* сложность написания
 +
* возможность распараллеливания
 +
 
 +
=== Основные характеристики программы ===
 +
Те же, что и у алгоритма, а также:
 +
 
 +
* понятность при чтении
 +
* модифицируемость (легкость изменения кода)
 +
* масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
 +
* безопасность
 +
 
 +
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы.
 +
Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
 +
 
 +
=== [http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных языков программирования] ===
 +
(самостоятельно на форуме)
 +
 
 +
== Язык программирования PascalABC.NET ==
 +
===Правила записи программ на PascalABC.NET===
 +
'''[http://it.mmcs.sfedu.ru/files?func=fileinfo&id=24 Шпаргалка]'''
 +
 
 +
===Пример программы, вычисляющей  длину и площадь круга===
 +
<source lang="Pascal">
 +
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.
 +
</source>
  
<u>Пример</u>.'' А.2., представленный блоксхемой.
+
===Структура программы на языке Паскаль===
[[Изображение:2.JPG|none]] <br />
 
  
* ''диаграммы деятельности (activity diagram) UML''
+
<source lang="Pascal">
 +
Заголовок программы
 +
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
 +
begin
 +
  операторы (разделяются ;)
 +
end.
 +
</source>
  
''<u>Пример</u>.'' А.2., представленный диаграммой деятельности
+
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
[[Изображение:2-1.JPG|none]] <br />
 
* ''язык программирования (ЯП)''
 
  
'''Команды алгоритма''' также называются:
+
===Система программирования PascalABC.NET===
:* '''''операторы''''' языка
+
Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
:* '''''инструкции''''' языка
 
  
== Правила записи программ на Object Pascal ==
+
Общая характеристика PascalABC.NET.  
'''По [http://it.mmcs.sfedu.ru/files?func=fileinfo&id=24 Шпаргалке]'''
 
:Пример программы, вычисляющей  длину и площадь круга.
 
:Общие правила записи программ на Паскале. Оформление, комментарии
 
  
'''PascalABC.NET'''. Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
+
Отличия языка PascalABC.NET от обычного языка Паскаль.
 +
 
 +
=== Компиляторы и интерпретаторы ===
 +
Схема компиляции в машинный код
 +
 
 +
Схема компиляции в промежуточный код. JIT-компиляция
 +
 
 +
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
 +
 
 +
'''Синтаксис''' - правила записи конструкций, '''семантика''' - смысл конструкций.
 +
 
 +
== Синтаксис и семантика ЯП ==
 +
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
  
== Синтаксис и семантика ЯП ==
 
 
=== Определения ===
 
=== Определения ===
 
'''Синтаксис''' — формальные правила описания конструкций ЯП.
 
'''Синтаксис''' — формальные правила описания конструкций ЯП.
Строка 71: Строка 136:
 
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
 
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
  
''<u>Пример</u>.''
+
''<u>Примеры</u>.''
 
  <цифра> ::= 0|1|2|3|4|5|6|7|8|9
 
  <цифра> ::= 0|1|2|3|4|5|6|7|8|9
 
  <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
 
  <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
 +
<список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов>
  
 
<tt>'''0, 1, ... 9'''</tt>
 
<tt>'''0, 1, ... 9'''</tt>
Строка 79: Строка 145:
 
<tt>'''<цифра>'''</tt>
 
<tt>'''<цифра>'''</tt>
 
:так называемый '''нетерминал''' ('''нетерминальный символ''').
 
:так называемый '''нетерминал''' ('''нетерминальный символ''').
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''рекурсивным''' (как определение нетерминала <идентификатор>)
+
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>)
  
 
* ''РБНФ'' (Расширенные БНФ)
 
* ''РБНФ'' (Расширенные БНФ)
Строка 108: Строка 174:
 
::<span style="color: green">(*...*)</span>
 
::<span style="color: green">(*...*)</span>
 
::<span style="color: green">//...</span>
 
::<span style="color: green">//...</span>
 
=== [http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных ЯП] ===
 
(самостоятельно на форуме)
 
  
 
== Переменные и их описание ==
 
== Переменные и их описание ==
Строка 119: Строка 182:
 
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
 
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
  
В языке Pascal любая переменная перед использованием должна быть описана. <br />
+
В языке ''Pascal'' любая переменная перед использованием должна быть описана. <br />
 
Обычно переменные описываются в '''''разделе описаний'''''.
 
Обычно переменные описываются в '''''разделе описаний'''''.
  
Строка 132: Строка 195:
 
  <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
 
  <секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
 
   
 
   
''<u>Пример секции описания переменных</u>.''
+
''<u>Пример</u> секции описания переменных.''
<source lang="Pascal">var
+
<source lang="Pascal">
  a,b: real;
+
var
  i: integer;</source>
+
  a,b: real;
 +
  i: integer;
 +
</source>
  
 
  <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>}
 
  <секция описания переменных> ::= '''var'''<подсекция>{< подсекция>}
Строка 155: Строка 220:
 
В последнем случае происходит '''''автоопределение''''' типов.
 
В последнем случае происходит '''''автоопределение''''' типов.
  
==Типы==
+
== Основные типы ==
 
* ''Целые''
 
* ''Целые''
:integer (4 байта)
+
:<tt>'''integer'''</tt> (4 байта)
:shortint (1)
+
:'''<tt>int64</tt>''' (8)
:smallint (2)
+
:'''<tt>byte</tt>''' (1)
:int64 (8)
 
  
 
* ''Вещественные''
 
* ''Вещественные''
:real (8)
+
:'''<tt>real</tt>''' (8)
:single (4)
 
  
 
* ''Символьные''
 
* ''Символьные''
:char (2 — Unicode)
+
:'''<tt>char</tt>''' (2 байта — Unicode)
  
 
*''Строковые''
 
*''Строковые''
:string
+
:'''<tt>string</tt>'''
:string[200]
+
:'''<tt>string</tt>'''[200]
:shortstring = string[255]
+
:'''<tt>shortstring</tt>''' = <tt>string</tt>[255]
  
 
* ''Логический''
 
* ''Логический''
:boolean (1) | ['''True''' '''False''']
+
:'''<tt>boolean</tt>''' (1) ['''<tt>''True''</tt>''' '''<tt>''False''</tt>''']

Текущая версия на 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., представленный блок-схемой.

Max flowchart.png

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]