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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м (Откат правок Dsoftlzhlzh (обсуждение) к версии Admin)
 
(не показаны 283 промежуточные версии 9 участников)
Строка 1: Строка 1:
==Лекция 1 (2.09.08)==
+
[[Категория:Основы программирования]]
Алгоритм
+
[[Страница курса Основы программирования|К основной странице курса]]
  
Свойства А.:
+
== Алгоритм ==
 +
[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
+
Если x>y и x>z, то максимум это x
...
+
Если y>x и y>z, то максимум — это y
 +
Если z>x и z>y, то максимум — это z
  
А.2. (псевдокод).
+
Алгоритм 2. (''псевдокод'')
max := x
 
Если y<max то max := y
 
Если z<max то max := z
 
  
Эквивалентность А.
+
max := x
Способы описания А.:
+
Если y<max то max := y
 +
Если 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]]
Способы описания синтаксиса:
 
  
  1. БНФ (1960, Алгол-60). Примеры: <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
+
4. ''Язык программирования (ЯП)''
      Понятие терминалов (лексем), нетерминалов
 
  2. РБНФ. [] - 0 или 1 повторение. {} - 0 и более повторений
 
      <идентификатор> ::= <буква> {<буква> | <цифра>}
 
  3. Синтаксические диаграммы (Вирт, Паскаль)  
 
  
Способы 1-3 эквивалентны
+
Для языка программирования команды алгоритма называются '''''операторами''''' или '''''инструкциями'''''.
  
Синтаксис определяет лексемы языка
+
=== Основные характеристики алгоритма===
Лексемы Паскаля
 
  
  1. спецсимволы: := += = , ;
+
* правильность работы
  2. ключевые слова
+
* скорость выполнения
  3. идентификаторы
+
* объем занимаемой памяти
  4. константы
+
* сложность написания
  5. комментарии (3 вида)
+
* возможность распараллеливания
  
Обзор современных ЯП
+
=== Основные характеристики программы ===
 +
Те же, что и у алгоритма, а также:
  
(самостоятельно на форуме)
+
* понятность при чтении
Переменные и их описание
+
* модифицируемость (легкость изменения кода)
 +
* масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
 +
* безопасность
  
(синтаксис в виде БНФ: <программа>, <раздел описаний>)
+
Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы.
 +
Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа - достаточно простой и понятной программы.
  
Внутриблочные описания (синтаксис на дом)
+
=== [http://it.mmcs.sfedu.ru/forum?func=view&id=22184&catid=1 Обзор современных языков программирования] ===
 +
(самостоятельно на форуме)
  
Типы: integer, real, char, string, boolean
+
== Язык программирования 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>
  
Примеры: d := d + 1; d := d * 2;
+
===Структура программы на языке Паскаль===
  
Семанитика: тип выражения д.б. совместим по := с переменной (если типы одинаковые, то совместим)
+
<source lang="Pascal">
Операторы присваивания += и *=
+
Заголовок программы
 +
Раздел описаний (описываются все используемые в программе переменные и определяются их типы)
 +
begin
 +
  операторы (разделяются ;)
 +
end.
 +
</source>
  
Примеры: d += 1; d *= 2;
+
Как правило, программа начинается с ввода исходных данных, после чего следуют вычисления и вывод результатов. Ввод сопровождается приглашением к вводу.
  
==Лекция 3 (10.09.08)==
+
===Система программирования PascalABC.NET===
 +
Как скачать, инсталлировать. ([http://pascalabc.net сайт системы программирования PascalABC.NET])
  
Примеры использования := :
+
Общая характеристика PascalABC.NET.
  
    * перемена местами двух значений
+
Отличия языка PascalABC.NET от обычного языка Паскаль.
    * использование промежуточных переменных в вычислениях (x16, x15)
 
  
Оператор ввода
+
=== Компиляторы и интерпретаторы ===
 +
Схема компиляции в машинный код
  
Обработка ошибок ввода
+
Схема компиляции в промежуточный код. JIT-компиляция
Оператор вывода
 
  
Вывод по формату :a и :a:b
+
Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения
  
Вывод с помощью writelnFormat
+
'''Синтаксис''' - правила записи конструкций, '''семантика''' - смысл конструкций.
Условный оператор
 
  
Синтаксис, семантика
+
== Синтаксис и семантика ЯП ==
 +
// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.
  
Примеры
+
=== Определения ===
 +
'''Синтаксис''' — формальные правила описания конструкций ЯП.
  
  1. Поиск min(a,b)
+
'''Семантика''' — описывает смысл конструкций ЯП, а также задает ряд ограничений.
  2. Упорядочение a,b по возрастанию. Необходимость составного оператора. Синтаксис, семантика
 
  3. Вычисление функции по нескольким взаимоисключающим веткам и цепочечные if
 
  4. Найти среднее среди a,b,c (a,b,c попарно не равны)
 
  
Самостоятельно
+
=== Способы описания синтаксиса ===
  
  1. Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику
+
* ''БНФ'' (Бэкуса-Наура формы, 1960, Алгол-60).
  2. Является ли 4-угольник ABCD корректно заданным
 
  
==Лекция 4 (16.09.08)==
+
''<u>Примеры</u>.''
Арифметические выражения
+
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
Операции div и mod. x div y = x/y, округленное до ближайшего целого, x mod y = x - (x div y)*y. Примеры использования.
+
<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
 +
<список идентификаторов> ::= <идентификатор> | <идентификатор> , <список идентификаторов>
  
Порядок действий в арифметических выражениях
+
<tt>'''0, 1, ... 9'''</tt>
 +
:называют '''терминалами''' ('''лексемами''') — это "конечные символы", т.е. по умолчанию известные в ЯП.
 +
<tt>'''<цифра>'''</tt>
 +
:так называемый '''нетерминал''' ('''нетерминальный символ''').
 +
:Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется '''''рекурсивным''''' (как определение нетерминала <идентификатор>)
  
Тип арифметического выражения
+
* ''РБНФ'' (Расширенные БНФ)
  
Стандартные функции. Вычисление степени x^y.
+
:'''[]''' — 0 или 1 повторение.  
Логические выражения
+
:'''{}''' — 0 и более повторений
  
Операции and, or, not, xor. Таблицы истинности.
+
''<u>Пример</u>.''
 +
<идентификатор> ::= <буква> {<буква> | <цифра>}
  
Сокращенное использование логических выражений
+
* ''Синтаксические диаграммы'' (Вирт, Паскаль)
  
Таблица приоритетов операций
+
'''Грамматика языка''' — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.
 +
:Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные ''семантические'' правила.
  
  1. унарные
+
'''Замечание 1.''' Способы 1-3 эквивалентны.
  2. * . div mod and shl shr
 
  3. + - or xor
 
  4. in отношения
 
  
Логические переменные. Пример с определением того, лежит ли точка на границе прямоугольника
+
'''Замечание 2.''' Синтаксис определяет лексемы языка.
  
Побитовые and, or, xor.
+
=== Лексемы Паскаля ===
  
Операции shl, shr
+
# ''спецсимволы: '' <tt>''':= += *'''</tt>
Оператор case выбора варианта
+
# ''ключевые слова ''(<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>
  
Синтакстис, семантика
+
== Переменные и их описание ==
  
Примеры
+
=== Основные сведения ===
  
  1. День недели
+
'''Переменная''' — это ячейка памяти компьютера, имеющая ''имя'' и ''тип''.
  2. цифра или буква
+
:'''''Тип''''' определяет размер переменной и множество принимаемых ею значений.
  
{tab=Лекция 5}
+
В языке ''Pascal'' любая переменная перед использованием должна быть описана. <br />
 +
Обычно переменные описываются в '''''разделе описаний'''''.
  
==Лекция 5 (17.09.08)==
+
<xh4> Синтаксис в виде РБНФ </xh4>
Циклы с предусловием (while) и постусловием (repeat)
+
<программа> ::= ['''program''' <имя>;]
 
+
                <раздел описаний>
Заголовок, тело, итерации
+
                '''begin'''
 
+
                  <операторы>
Синтаксис и семантика
+
                '''end.'''
 
+
<операторы> ::= <оператор>{; <оператор>}
Отличия
+
<раздел описаний> ::= {<секция раздела описаний>}
 
+
<секция раздела описаний> ::= <секция описания переменных> | <с.о. констант> | <с.о. типов> | <с.о. подпрограмм>...
Примеры
+
 
+
''<u>Пример</u> секции описания переменных.''
  1. Факториал
+
<source lang="Pascal">
  2. Сумма четных двузначных
+
var
 
+
  a,b: real;
Моделирование repeat с помощью while
+
  i: integer;
 
+
</source>
Моделирование 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.
 
 
 
Локальные и глобальные переменные.
 
 
 
Инициализация глобальных и локальных переменных значениями по умолчанию.
 
 
 
Понятие пространства имен.
 
 
 
Глобальные переменные и побочный эффект.
 
 
 
==Лекция 10 (14.10.08)==
 
 
 
Понятие области видимости и времени жизни объекта.
 
 
 
Изменение глобальной переменной как побочный эффект. Нежелательность такого изменения. При необходимости изменения глобальной переменной - передать ее как параметр.
 
 
 
Принцип локальности: чем локальнее объявлена переменная, тем лучше. Распространение принципа локальности на внутриблочные переменнные: вспомогательные переменные, используемые в блоке алгоритма, следует делать внутриблочными.
 
 
 
Понятие ссылки как другого имени объекта. Внутренний механизм передачи параметра по ссылке.
 
 
 
Перегрузка имен подпрограмм (на примере swap).
 
 
 
==Лекция 11 (15.10.08)==
 
 
 
Параметры по умолчанию - на примере 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.
 
Массивы
 
  
Понятие структурированного типа данных.
+
<секция описания переменных> ::= '''var'''<подсекция>{< подсекция>}
 +
<подсекция> ::= <список имен>: <тип>;
 +
<список имен> ::= <имя>{,<имя>}
 +
<тип> ::= <имя>
  
Определение массива.
+
=== Внутриблочные переменные ===
  
Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.
+
В PascalABC.NET возможно ''внутриблочное'' описание переменных:
 
 
==Лекция 16 (11.11.08)==
 
 
 
Обращение к элементам массивов.
 
 
 
Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
 
 
 
Динамические массивы. Хранение в памяти.
 
 
 
Инициализация массивов.
 
 
 
Присваивание массивов. Сравнение массивов.
 
 
 
Присваивание a := nil для динамических массивов.
 
 
 
Цикл foreach.
 
 
 
Именная и структурная эквивалентность типов.
 
 
 
==Лекция 17 (12.11.08)==
 
Массивы как параметры подпрограмм
 
 
 
Cтатический массив
 
при передаче должна соблюдаться именная эквивалентность
 
  procedure xxx(a: array [1..100] of integer)
 
 
 
type IArr = array [1..100] of integer;
 
procedure yyy(a: IArr);
 
 
 
Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово const, которое также запрещает изменять данные внутри п/п.
 
 
 
Динамический массив
 
можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.
 
 
 
procedure zzz(a: array of integer);
 
 
 
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
 
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
 
Массивы как возвращаемые значения функции
 
 
 
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
 
Переменное число параметров подпрограмм
 
 
 
П/п можно создавать с переменным количеством параметров.
 
Для этого исп. ключевое слово params.
 
При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним.
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
 
 
==Лекция 18 (19.11.08)==
 
Шаблоны подпрограмм
 
 
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
 
 
Выход - шаблоны.
 
 
 
Пример:
 
 
 
  procedure Print<T> (array of T);
 
 
 
В момент вызова п/п происходит:
 
 
 
    * выведение типов шаблона по фактическим параметрам
 
 
 
    * инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.
 
 
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
Задачи на одномерные массивы
 
 
 
    * инвертирование массива (шаблон)
 
 
 
    * поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
        можно с 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]