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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Лекция 17 (12.11.08))
м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin)
 
(не показано 277 промежуточных версий 9 участников)
Строка 1: Строка 1:
==Лекция 1 (2.09.08)==
+
[[Категория:Основы программирования]]
<H3>Алгоритм</H3>
+
[[Страница курса Основы программирования|К основной странице курса]]
  
Свойства А.:
+
== Алгоритм ==
 +
[http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC '''Алгоритм'''] — набор команд, определяющих порядок действий для решения поставленной задачи.
  
дискретность, элементарность действий, определенность действий, конечность,результативность, массовость.
+
С алгоритмом всегда связан '''исполнитель алгоритма''' - устройство, имеющее систему команд.
  
Исполнитель А. Процессор как исполнитель машинных кодов.
+
В частности, процессор компьютера выступает исполнителем машинных команд.
 +
=== Свойства алгоритма ===
 +
* Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
 +
* Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
 +
* Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
 +
* Результативность — после выполнения алгоритма известно, что считать результатом.
 +
* Массовость — применимость алгоритма ко множеству исходных данных.
  
Спецификация задачи как точное, однозначное описание. Включает входные и выходные данные.
+
''<u>Пример алгоритма</u>.''
 +
:Дано: <tt>x, y, z</tt>.  
 +
:Найти <tt>max</tt>
  
Пр. Дано: x,y,z. Найти max
+
Алгоритм 1. (''словесное описание'')
  
А.1. (словесное описание).
+
Если x>y и x>z, то максимум — это x
 +
Если y>x и y>z, то максимум — это y
 +
Если z>x и z>y, то максимум — это z
  
Если x>y и x>z, то максимум - это x
+
Алгоритм 2. (''псевдокод'')
Если y>x и y>z, то максимум - это x
 
Если z>x и z>y, то максимум - это x
 
 
 
А.2. (псевдокод).
 
  
 
  max := x
 
  max := x
Строка 24: Строка 31:
 
  Если z<max то max := z
 
  Если z<max то max := z
  
Эквивалентность А.
+
'''Эквивалентными''' называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных.
 +
Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.
  
Способы описания А.:
 
* словесный
 
* псевдокод
 
* блок-схемы
 
* диаграммы деятельности (activity diagram) UML
 
* язык программирования (ЯП)
 
  
Команды А. = операторы Я.
+
'''Спецификация задачи''' — точное, однозначное описание задачи. Включает формулировку входных и выходных данных.
  
''Компилятор'' как преобразователь программы на ЯП в машинные коды.
+
=== Способы описания алгоритмов ===
Программа нахождения S и C круга на Паскале
+
1. ''Словесный''
  
(по Шпаргалке)
+
2. ''Псевдокод''
Общие правила записи программ на Паскале. Оформление, комментарии
 
  
PascalABC.NET. Как скачать, инсталлировать
+
3. ''Блок-схемы''
  
==Лекция 2 (3.09.08)==
+
''<u>Пример</u>.'' А.2., представленный блок-схемой.
Синтаксис и семантика ЯП
+
[[Изображение:max_flowchart.png|none]]
Способы описания синтаксиса:
 
  
* БНФ (1960, Алгол-60).
+
4. ''Язык программирования (ЯП)''
  
Пример.  
+
Для языка программирования команды алгоритма называются '''''операторами''''' или '''''инструкциями'''''.
  
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
+
=== Основные характеристики алгоритма===
  
Понятие терминалов (лексем), нетерминалов
+
* правильность работы
 +
* скорость выполнения
 +
* объем занимаемой памяти
 +
* сложность написания
 +
* возможность распараллеливания
  
* РБНФ.
+
=== Основные характеристики программы ===
 +
Те же, что и у алгоритма, а также:
  
[] - 0 или 1 повторение. {} - 0 и более повторений
+
* понятность при чтении
 +
* модифицируемость (легкость изменения кода)
 +
* масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
 +
* безопасность
  
<идентификатор> ::= <буква> {<буква> | <цифра>}
+
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы.
 +
Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
  
* Синтаксические диаграммы (Вирт, Паскаль)  
+
=== [http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных языков программирования] ===
 +
(самостоятельно на форуме)
  
Способы 1-3 эквивалентны
+
== Язык программирования 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>
  
<H3>Лексемы Паскаля</H3>
+
===Структура программы на языке Паскаль===
  
# спецсимволы: := += = , ;
+
<source lang="Pascal">
# ключевые слова
+
Заголовок программы
# идентификаторы
+
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
# константы
+
begin
# комментарии (3 вида)  
+
  операторы (разделяются ;)
 +
end.
 +
</source>
  
Обзор современных ЯП (самостоятельно на форуме)
+
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
  
<H3>Переменные и их описание</H3>
+
===Система программирования PascalABC.NET===
 +
Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
  
(синтаксис в виде БНФ: <программа>, <раздел описаний>)
+
Общая характеристика PascalABC.NET.
  
Внутриблочные описания (синтаксис на дом)
+
Отличия языка PascalABC.NET от обычного языка Паскаль.
  
Типы: integer, real, char, string, boolean
+
=== Компиляторы и интерпретаторы ===
 +
Схема компиляции в машинный код
  
<H3>Оператор присваивания :=</H3>
+
Схема компиляции в промежуточный код. JIT-компиляция
  
Синтаксис: <переменная> := <выражение>
+
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
  
Пример.  
+
'''Синтаксис''' - правила записи конструкций, '''семантика''' - смысл конструкций.
d := d + 1;
 
d := d * 2;
 
  
Семанитика: тип выражения д.б. совместим по := с переменной (если типы одинаковые, то совместим)
+
== Синтаксис и семантика ЯП ==
 +
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
  
Операторы присваивания += и *=
+
=== Определения ===
 +
'''Синтаксис''' — формальные правила описания конструкций ЯП.
  
Пример.  
+
'''Семантика''' — описывает смысл конструкций ЯП, а также задает ряд ограничений.
d += 1;
 
d *= 2;
 
  
==Лекция 3 (10.09.08)==
+
=== Способы описания синтаксиса ===
  
Примеры использования := :
+
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
  
    * перемена местами двух значений
+
''<u>Примеры</u>.''
    * использование промежуточных переменных в вычислениях (x16, x15)
+
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
 +
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
 +
<список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов>
  
Оператор ввода
+
<tt>'''0, 1, ... 9'''</tt>
 +
:называют '''терминалами''' ('''лексемами''') — это "конечные символы", т.е. по умолчанию известные в ЯП.
 +
<tt>'''<цифра>'''</tt>
 +
:так называемый '''нетерминал''' ('''нетерминальный символ''').
 +
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>)
  
Обработка ошибок ввода
+
* ''РБНФ'' (Расширенные БНФ)
Оператор вывода
 
  
Вывод по формату :a и :a:b
+
:'''[]''' — 0 или 1 повторение.
 +
:'''{}''' — 0 и более повторений
  
Вывод с помощью writelnFormat
+
''<u>Пример</u>.''
Условный оператор
+
<идентификатор> ::= <буква> {<буква> | <цифра>}
 
 
Синтаксис, семантика
 
 
 
Примеры
 
 
 
  1. Поиск min(a,b)
 
  2. Упорядочение a,b по возрастанию. Необходимость составного оператора. Синтаксис, семантика
 
  3. Вычисление функции по нескольким взаимоисключающим веткам и цепочечные if
 
  4. Найти среднее среди a,b,c (a,b,c попарно не равны)
 
 
 
Самостоятельно
 
 
 
  1. Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику
 
  2. Является ли 4-угольник ABCD корректно заданным
 
 
 
==Лекция 4 (16.09.08)==
 
Арифметические выражения
 
Операции div и mod. x div y = x/y, округленное до ближайшего целого, x mod y = x - (x div y)*y. Примеры использования.
 
 
 
Порядок действий в арифметических выражениях
 
 
 
Тип арифметического выражения
 
 
 
Стандартные функции. Вычисление степени x^y.
 
Логические выражения
 
 
 
Операции and, or, not, xor. Таблицы истинности.
 
 
 
Сокращенное использование логических выражений
 
 
 
Таблица приоритетов операций
 
 
 
  1. унарные
 
  2. * . div mod and shl shr
 
  3. + - or xor
 
  4. in отношения
 
 
 
Логические переменные. Пример с определением того, лежит ли точка на границе прямоугольника
 
 
 
Побитовые and, or, xor.
 
 
 
Операции shl, shr
 
Оператор case выбора варианта
 
 
 
Синтакстис, семантика
 
 
 
Примеры
 
 
 
  1. День недели
 
  2. цифра или буква
 
 
 
{tab=Лекция 5}  
 
 
 
==Лекция 5 (17.09.08)==
 
Циклы с предусловием (while) и постусловием (repeat)
 
 
 
Заголовок, тело, итерации
 
 
 
Синтаксис и семантика
 
 
 
Отличия
 
 
 
Примеры
 
 
 
  1. Факториал
 
  2. Сумма четных двузначных
 
 
 
Моделирование repeat с помощью while
 
 
 
Моделирование while с помощью repeat
 
 
 
Зацикливание
 
Оператор цикла с параметром (for)
 
 
 
Синтаксис, семантика: моделирование for с помощью while, ограничения
 
 
 
Примеры
 
 
 
  1. Факториал
 
  2. Сумма четных двузначных
 
 
 
Примеры использования циклов
 
 
 
  1. Табулирование функции. использование for и while
 
 
 
Погрешность округления вещественных чисел и вычислительная погрешность.
 
 
 
==Лекция 6 (24.09.08)==
 
 
 
Поиск минимального среди введенных.
 
 
 
Рекуррентные последовательности.
 
 
 
Числа Фибоначчи.
 
 
 
Суммирование рядов (конечных и бесконечных).
 
 
 
Алгоритм Евклида нахождения НОД.
 
 
 
Разложение целого числа на простые множители.
 
 
 
==Лекция 7 (30.09.08)==
 
 
 
Поиск заданного значения среди введенных.
 
 
 
Операторы break и continue. Как обойтись без них.
 
 
 
Схема Горнера.
 
 
 
Поиск нуля функции на отрезке.
 
 
 
==Лекция 8 (01.10.08)==
 
 
 
Вложенные циклы. Метод окаймления и метод последовательной детализации.
 
 
 
Переборные задачи. Необходимость оптимизации самого внутреннего цикла.
 
 
 
Вспомогательные алгоритмы и их параметры. Подпрограммы. Мотивировка введения подпрограмм.
 
 
 
Процедуры. Пример вычисления среднего арифметического и среднего геометрического.
 
 
 
==Лекция 9 (8.10.08)==
 
 
 
Синтаксис описания процедуры. Синтаксис вызова процедуры.
 
 
 
Входно-выходные параметры. Процедура Swap.
 
 
 
Формальные и фактические параметры. Семантические правила при вызове.
 
 
 
Функции. Синтаксис. Вызов функции. Переменная Result.
 
 
 
Примеры: Sign, ReadInteger и т.п., SumN.
 
 
 
Сравнение с процедурами на примере Sign.
 
  
Нежелательность var-параметров в функциях.
+
* ''Синтаксические диаграммы'' (Вирт, Паскаль)
  
Стандартные подпрограммы с передачей по ссылке: readln, Inc, Dec.
+
'''Грамматика языка''' — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
 +
:Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила.
  
Локальные и глобальные переменные.
+
'''Замечание 1.''' Способы 1-3 эквивалентны.
  
Инициализация глобальных и локальных переменных значениями по умолчанию.
+
'''Замечание 2.''' Синтаксис определяет лексемы языка.
  
Понятие пространства имен.
+
=== Лексемы Паскаля ===
  
Глобальные переменные и побочный эффект.
+
# ''спецсимволы: '' <tt>''':= += *'''</tt>
 +
# ''ключевые слова ''(<tt>'''begin, end, if, for'''</tt>)
 +
# ''идентификаторы ''(<tt>'''a, b1'''</tt>)
 +
# ''константы ''(<tt>'''2, 'ABC', #5'''</tt>)
 +
# ''комментарии (3 вида)''
 +
::<span style="color: green">{...}</span>
 +
::<span style="color: green">(*...*)</span>
 +
::<span style="color: green">//...</span>
  
==Лекция 10 (14.10.08)==
+
== Переменные и их описание ==
  
Понятие области видимости и времени жизни объекта.
+
=== Основные сведения ===
  
Изменение глобальной переменной как побочный эффект. Нежелательность такого изменения. При необходимости изменения глобальной переменной - передать ее как параметр.
+
'''Переменная''' — это ячейка памяти компьютера, имеющая ''имя'' и ''тип''.
 +
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
  
Принцип локальности: чем локальнее объявлена переменная, тем лучше. Распространение принципа локальности на внутриблочные переменнные: вспомогательные переменные, используемые в блоке алгоритма, следует делать внутриблочными.
+
В языке ''Pascal'' любая переменная перед использованием должна быть описана. <br />
 +
Обычно переменные описываются в '''''разделе описаний'''''.
  
Понятие ссылки как другого имени объекта. Внутренний механизм передачи параметра по ссылке.
+
<xh4> Синтаксис в виде РБНФ </xh4>
 
+
<программа> ::= ['''program''' <имя>;]
Перегрузка имен подпрограмм (на примере swap).
+
                <раздел описаний>
 
+
                '''begin'''
==Лекция 11 (15.10.08)==
+
                  <операторы>
 
+
                '''end.'''
Параметры по умолчанию - на примере DoOp(a,b: integer; var res: integer; op: char := '+').
+
<операторы> ::= <оператор>{; <оператор>}
 
+
<раздел описаний> ::= {<секция раздела описаний>}
Предварительное объявление подпрограмм.
+
<секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
 
 
Процедурные переменные.
 
 
 
Процедурные переменные как параметры подпрограмм. Функции обратного вызова (callback).
 
 
 
    Пример: DoActions(Act1, Act2, Act3: procedure)
 
 
 
    Пример: вычисление определённого интеграла методом прямоугольников - Integral(a,b,N,f)
 
 
 
Вызов нескольких действий. Операции += и -=.
 
 
 
==Лекция 12 (22.10.08)==
 
 
 
Оператор exit досрочного завершения подпрограммы
 
 
 
Методы разработки подпрограмм
 
 
 
Метод "сверху вниз" и метод "снизу вверх" (на примере таблицы простых чисел).
 
 
 
Когда эффективен каждый метод:
 
 
 
    * сверху-вниз - когда задача четко поставлена и имеется четкий алгоритм ее решения;
 
    * сниз-вверх - когда задача нечетко поставлена. когда решается группа взаимосвязанных задач из дной области, когда в задаче нет четко выделенного главного алгоритма, когда необходимо приступать к решению задачи, попутно уточняя алгоритм.
 
 
 
Семантика вызова подпрограммы на этапе выполнения.
 
 
 
Понятие программного стека.
 
 
 
Запись активации, ее структура.
 
 
 
Алгоритм вызова процедуры на этапе выполнения.
 
 
 
==Лекция 13 (28.10.08)==
 
 
 
Пример, иллюстрирующий алгоритм вызова процедуры.
 
 
 
Замечания:
 
 
 
    * о накладных расходах, связанных с вызовом маленьких и больших подпрограмм
 
    * о проблеме переполнения программного стека при наличии больших локальных переменных и при передаче больших локальных переменных п значению
 
    * о проблеме доступа к глобальным переменным
 
 
 
Модули
 
 
 
Определение
 
 
 
Структура модуля с разделами интерфейса и реализации.
 
 
 
Принцип сокрытия информации.
 
 
 
Преимущества разделения модуля на интерфейс и реализацию.
 
 
 
==Лекция 14 (29.10.08)==
 
 
 
Упрощенная структура модуля.
 
 
 
Разделы инициализации и финализации.
 
 
 
Схема компиляции программы с модулями.
 
 
 
Алгоритм поиска имен в модулях. Модуль как пространство имен.
 
 
 
Системный модуль PABCSystem
 
 
 
==Лекция 15 (5.11.08)==
 
 
 
Документирующие комментарии ///
 
 
 
Библиотеки. Отличие библиотек от модулей. Подключение библиотек в PascalABC.NET.
 
 
 
Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.
 
 
 
Использование перечислимого типа в for и case.
 
Массивы
 
 
 
Понятие структурированного типа данных.
 
 
 
Определение массива.
 
 
 
Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.
 
 
 
==Лекция 16 (11.11.08)==
 
 
 
Обращение к элементам массивов.
 
 
 
Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
 
 
 
Динамические массивы. Хранение в памяти.
 
 
 
Инициализация массивов.
 
 
 
Присваивание массивов. Сравнение массивов.
 
 
 
Присваивание a := nil для динамических массивов.
 
 
 
Цикл foreach.
 
 
 
Именная и структурная эквивалентность типов.
 
 
 
==Лекция 17 (12.11.08)==
 
<H3>Массивы как параметры подпрограмм</H3>
 
 
 
При передаче статического массива должна соблюдаться именная эквивалентность
 
procedure xxx(a: array [1..100] of integer); // неверно
 
 
   
 
   
type IArr = array [1..100] of integer;
+
''<u>Пример</u> секции описания переменных.''
procedure yyy(a: IArr);
+
<source lang="Pascal">
 
+
var
Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово <tt>const</tt>, которое также запрещает изменять данные внутри п/п.
+
  a,b: real;
 
+
  i: integer;
procedure zzz(const a: IArr);
+
</source>
procedure sss(var a: IArr);
 
 
 
Динамический массив
 
можно передавать в виде <tt>array of integer</tt>, т.к. для него определена структурная эквивалентность типов.
 
 
 
procedure ttt(a: array of integer);
 
  
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
+
<секция описания переменных> ::= '''var'''<подсекция>{< подсекция>}
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
+
<подсекция> ::= <список имен>: <тип>;
Массивы как возвращаемые значения функции
+
<список имен> ::= <имя>{,<имя>}
 +
<тип> ::= <имя>
  
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
+
=== Внутриблочные переменные ===
  
<h3>Переменное число параметров подпрограмм</h3>
+
В PascalABC.NET возможно ''внутриблочное'' описание переменных:
 
 
П/п можно создавать с переменным количеством параметров.
 
Для этого исп. ключевое слово params.
 
При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним.
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
 
 
==Лекция 18 (19.11.08)==
 
<H3>Шаблоны подпрограмм</H3>
 
 
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
 
 
Выход - шаблоны.
 
 
 
Пример:
 
 
 
  procedure Print<T> (array of T);
 
 
 
В момент вызова п/п происходит:
 
 
 
* выведение типов шаблона по фактическим параметрам
 
* инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.
 
 
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
 
 
<H3>Задачи на одномерные массивы</H3>
 
 
 
* инвертирование массива (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
 
 
можно с for и break,
 
 
 
можно и другим способом - с while
 
 
 
* поиск с барьером (шаблон). Его преимущества
 
* минимальный элемент массива и его индекс
 
* слияние двух упорядоченных массивов в один упорядоченный (барьер)
 
* сдвиг элементов массива влево (шаблон)
 
 
 
знакомство со значением default(T), Т - тип
 
 
 
==Лекция 19 (25.11.08)==
 
 
 
Задачи на одномерные массивы
 
 
 
pas-файл с задачами
 
 
 
doc-файл
 
 
 
используется тип IArr =  array [1..size] of integer
 
 
 
    * сдвиг элементов массива вправо (ShiftRight)
 
 
 
    [ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]
 
 
 
    * циклический сдвиг элементов массива вправо (CycleShiftRight)
 
    * удаление элемента по заданному индексу (Delete)
 
    * вставка элемента по заданному индексу (Insert)
 
 
 
Задачи с процедурными переменными в качестве параметров
 
определяется тип IUnPred = function (x: integer): boolean
 
 
 
    * поиск элемента по заданному условию (Find)
 
    * количество элементов, удовлетворяющих условию (Count)
 
    * условный минимум (MinElem)
 
    * удаление всех элементов, удовлетворяющих условию (DeleteAll)
 
 
 
Примечание
 
  для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
 
 
 
==Лекция 20 (26.11.08)==
 
 
 
Сортировки
 
 
 
    * Выбором  (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)
 
 
 
    * Пузырьковая
 
 
 
        это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.
 
 
 
    * Вставками  (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)
 
 
 
Замечание. Рассмотренные виды сортировки не являются самыми эффективными.
 
Асимптотическая сложность алгоритмов
 
 
 
Определение. Число шагов алгоритма асимптотически равно  Θ (f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
 
 
 
    c1*f(n) ≤число шагов≤ c2*f(n)
 
 
 
Замечание 1. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n2).
 
 
 
Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью =  Θ( n*logn) (они будут рассмотрены в следующем семестре).
 
{tab=Лекция 21}
 
 
 
==Лекция 21 (3.12.08)==
 
 
 
Алгоритм бинарного поиска в отсортированном массиве.
 
 
 
Его асимптотическая сложность - Θ(logn).
 
Двумерные массивы
 
 
 
Двумерный массив как матрица (соответствие индексов строкам и столбцам)
 
 
 
Элементы строки. Элементы столбца (рисунки)
 
 
 
Понятие замороженного индекса
 
 
 
Задачи на двумерные массивы
 
 
 
    * Вывод матрицы
 
          o внешний цикл по строкам
 
          o если внешним сделать цикл по столбцам будет выведена транспонированная матрица
 
 
 
    * Сумма элементов в j-том столбце
 
 
 
    * Сумма элементов в каждом столбце
 
          o использование функции для нахождения суммы в j-ом столбце
 
 
 
    * Минимальный элемент в каждой строке
 
          o в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.
 
 
 
    Замечание.  Решать такие задачи можно и реализуя алгоритм полностью,  и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.
 
 
 
    * Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
 
 
 
==Лекция 22 (9.12.08)==
 
 
 
Поиск элемента в матрице
 
 
 
    если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,
 
 
 
    иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА
 
 
 
Записи
 
 
 
type <имя записи>= record
 
 
 
  <поля записи>
 
 
 
end;
 
 
 
    * Поля записей
 
 
 
    * Инициализация записей при описании (на примере Student)
 
 
 
    * Доступ к полям записей. Точечная нотация.
 
 
 
Замечание. Для записей имеет место именная эквивалентность типов.
 
 
 
    * Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).
 
 
 
    Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке  (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.
 
 
 
    * Оператор with.
 
 
 
    with <переменная типа запись> do
 
    begin
 
      <поле>:=<значение>
 
    end;
 
 
 
    Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)
 
 
 
    * Методы в записях (на примере Student.Print).
 
 
 
    * Запись как пространство имен.
 
 
 
    Запись выступает для своих полей и методов в качестве модуля (поскольку является набором данных и связанных с ними процедур и функций, оформленных как единое целое).
 
 
 
    Методы работают в некотором окружении, в роли которого выступают поля записи и другие методы.
 
 
 
    Создается окружение при описании переменной типа запись.
 
 
 
    * Сравнение s.Print и Print(s)
 
 
 
    s.Print - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.
 
 
 
    Print(s) - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.
 
 
 
    * Метод Init - инициализатор полей записи.
 
 
 
==Лекция 23 (10.12.08)==
 
 
 
Создание простейших графических объектов:
 
 
 
RPoint = record x, y: integer end;
 
 
 
RRectangle = record p1,p2: RPoint end;
 
 
 
Для каждого типа - методы Print, Draw, MoveOn
 
 
 
Записи как средство упаковки параметров
 
 
 
Пример использования определенных типов перегруженной процедурой Rectangle
 
 
 
    Rectangle(x1,y1, x2,y2: integer)
 
 
 
    Rectangle(p1,p2: RPoint)
 
 
 
    Rectangle(r: RRectangle)
 
 
 
    Line(x1,y1, x2,y2: integer)
 
 
 
    Line(p1,p2: RPoint)
 
 
 
    Line(r: RRectangle)
 
 
 
Переменная типа запись как объект
 
 
 
    В модуле можно выносить реализацию методов записи в раздел реализации. При этом в разделе интерфейса внутри определения типа запись описываются только заголовки методов, а в разделе реализации перед именем метода необходимо писать <Имя записи>.
 
 
 
Поля записи как состояние объекта.
 
 
 
Методы записи как действия, воздействующие на состояние объекта.
 
 
 
    Методы делятся на две категории
 
 
 
        * меняющие состояние объекта (MoveOn для RPoint)
 
        * осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)
 
 
 
Сортировка массива записей.
 
 
 
==Лекция 24 (17.12.08)==
 
 
 
Индексная сортировка.
 
 
 
Множества
 
 
 
Описание множеств.
 
 
 
Множества-константы.
 
 
 
Основные операции с множествами.
 
 
 
Цикл по множеству.
 
 
 
Пример использования множеств: решето Эратосфена.
 
 
 
 
Символы
 
  
Коды символов. Литеральные константы-символы.
+
<source lang="Pascal">
 +
begin
 +
  var i,j: integer;
 +
  var r: real := 5.2;
 +
  var Pi := 3.14;
 +
</source>
  
Стандартные подпрограммы работы с символами.
+
В последнем случае происходит '''''автоопределение''''' типов.
Строки
 
  
Виды строк в PascalABC.NET
+
== Основные типы ==
 +
* ''Целые''
 +
:<tt>'''integer'''</tt> (4 байта)
 +
:'''<tt>int64</tt>''' (8)
 +
:'''<tt>byte</tt>''' (1)
  
Основные подпрограммы работы со строками.
+
* ''Вещественные''
 +
:'''<tt>real</tt>''' (8)
  
==Лекция 25 (23.12.08)==
+
* ''Символьные''
Некоторые алгоритмы работы со строками.
+
:'''<tt>char</tt>''' (2 байта — Unicode)
  
==Лекция 26 (24.12.08)==
+
*''Строковые''
 +
:'''<tt>string</tt>'''
 +
:'''<tt>string</tt>'''[200]
 +
:'''<tt>shortstring</tt>''' = <tt>string</tt>[255]
  
Текстовые файлы.
+
* ''Логический''
Типизированные файлы.
+
:'''<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]