Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I
Содержание
Лекция 1 (2.09.08)
Алгоритм
Свойства А.:
дискретность, элементарность действий, определенность действий, конечность,результативность, массовость.
Исполнитель А. Процессор как исполнитель машинных кодов.
Спецификация задачи как точное, однозначное описание. Включает входные и выходные данные.
Пр. Дано: x,y,z. Найти max
А.1. (словесное описание). Если x>y и x>z, то максимум - это x ...
А.2. (псевдокод). max := x Если y<max то max := y Если z<max то max := z
Эквивалентность А. Способы описания А.:
* словесный * псевдокод * блок-схемы * диаграммы деятельности (activity diagram) UML * язык программирования (ЯП)
Команды А. = операторы Я.
Компилятор как преобразователь программы на ЯП в машинные коды. Программа нахождения S и C круга на Паскале
(по Шпаргалке) Общие правила записи программ на Паскале
Оформление, комментарии PascalABC.NET
Как скачать, инсталлировать
Лекция 2 (3.09.08)
Синтаксис и семантика ЯП Способы описания синтаксиса:
1. БНФ (1960, Алгол-60). Примеры: <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>
Понятие терминалов (лексем), нетерминалов
2. РБНФ. [] - 0 или 1 повторение. {} - 0 и более повторений
<идентификатор> ::= <буква> {<буква> | <цифра>}
3. Синтаксические диаграммы (Вирт, Паскаль)
Способы 1-3 эквивалентны
Синтаксис определяет лексемы языка Лексемы Паскаля
1. спецсимволы: := += = , ; 2. ключевые слова 3. идентификаторы 4. константы 5. комментарии (3 вида)
Обзор современных ЯП
(самостоятельно на форуме) Переменные и их описание
(синтаксис в виде БНФ: <программа>, <раздел описаний>)
Внутриблочные описания (синтаксис на дом)
Типы: integer, real, char, string, boolean Основные операторы, их синтаксис и семантика Оператор присваивания :=
Синтаксис: <переменная> := <выражение>
Примеры: d := d + 1; d := d * 2;
Семанитика: тип выражения д.б. совместим по := с переменной (если типы одинаковые, то совместим) Операторы присваивания += и *=
Примеры: d += 1; d *= 2;
Лекция 3 (10.09.08)
Примеры использования := :
* перемена местами двух значений * использование промежуточных переменных в вычислениях (x16, x15)
Оператор ввода
Обработка ошибок ввода Оператор вывода
Вывод по формату :a и :a:b
Вывод с помощью writelnFormat Условный оператор
Синтаксис, семантика
Примеры
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.
Локальные и глобальные переменные.
Инициализация глобальных и локальных переменных значениями по умолчанию.
Понятие пространства имен.
Глобальные переменные и побочный эффект.
Лекция 10 (14.10.08)
Понятие области видимости и времени жизни объекта.
Изменение глобальной переменной как побочный эффект. Нежелательность такого изменения. При необходимости изменения глобальной переменной - передать ее как параметр.
Принцип локальности: чем локальнее объявлена переменная, тем лучше. Распространение принципа локальности на внутриблочные переменнные: вспомогательные переменные, используемые в блоке алгоритма, следует делать внутриблочными.
Понятие ссылки как другого имени объекта. Внутренний механизм передачи параметра по ссылке.
Перегрузка имен подпрограмм (на примере swap).
