Презентация на тему: Информатика и программирование

Информатика и программирование
Вопросы по дисциплине «Информатика и программирование»
1 Информация и информационное взаимодействие. Свойства информации: достоверность, полнота, актуальность, ясность, ценность.
2
3
4
5
6
7
8
9
10
11
12
13 2 Современные методологии и языки программирования высокого уровня. Классификация языков программирования.
14
15
Бурное развитие языков…
17 Семантика языков
18
19
20
21
3 Алгоритмы и программы. Основные алгоритмические управляющие структуры. Стиль программирования.
23
24
25
26
27
28пример блок-схемы
29
30
31
32
33
34 4. Процедуры и функции. Параметры и аргументы процедуры (функции). Передача аргументов в функции (процедуры) по значению и по ссылке. Локальные и глобальные
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
5 Структуры данных. Классические структуры данных: массивы, списки, деревья. Стеки и очереди.
51
52
53
Информатика и программирование
55
56
57
58
59
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
6 Задачи поиска и сортировки. Алгоритмы поиска. Последовательный и бинарный поиск в упорядоченном массиве. Алгоритм сортировки обменами (метод пузырька).
68
69
70
71
72
73
74
7 Объектно-ориентированный подход в программировании. Понятие класса и объекта. Структура объекта. Поля, методы и свойства объектов. Создание и удаление
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
Информатика и программирование
8 Принцип наследования. Перекрытие полей и методов. Области видимости. Полиморфизм. Родительский, дочерний классы. Поля, методы объектов. Инкапсуляция.
Информатика и программирование
93
Инкапсуляция (encapsulation) - это сокрытие реализации класса и отделение его внутреннего представления от внешнего (интерфейса). При использовании
93
94
1/96
Средняя оценка: 4.3/5 (всего оценок: 58)
Код скопирован в буфер обмена
Скачать (985 Кб)
1

Первый слайд презентации: Информатика и программирование

Лебедева Т.Ф. КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Изображение слайда
2

Слайд 2: Вопросы по дисциплине «Информатика и программирование»

Информация и информационное взаимодействие. Свойства информации: достоверность, полнота, актуальность, ясность, ценность. Современные методологии и языки программирования высокого уровня. Классификация языков программирования. Алгоритмы и программы. Основные алгоритмические управляющие структуры. Стиль программирования. Процедуры и функции. Параметры и аргументы процедуры (функции). Передача аргументов в функции (процедуры) по значению и по ссылке. Локальные и глобальные переменные. Вложенные процедуры. Организация рекурсии. Структуры данных. Классические структуры данных: массивы, списки, деревья. Стеки и очереди. Задачи поиска и сортировки. Алгоритмы поиска. Последовательный и бинарный поиск в упорядоченном массиве. Алгоритм сортировки обменами (метод пузырька). Алгоритм сортировки выбором. Объектно-ориентированный подход в программировании. Понятие класса и объекта. Структура объекта. Поля, методы и свойства объектов. Создание и удаление объектов. Принцип наследования. Перекрытие полей и методов. Области видимости. Полиморфизм. Родительский, дочерний классы. Поля, методы объектов. Инкапсуляция. Свойства объектов. Методы доступа к свойствам объектов. Правило инкапсуляции. 2

Изображение слайда
3

Слайд 3: 1 Информация и информационное взаимодействие. Свойства информации: достоверность, полнота, актуальность, ясность, ценность

Термин  "информация"  происходит от латинского слова  "informatio",  что означает  сведения,  разъяснения,  изложение. Несмотря на широкое распространение этого термина, понятие информации является одним из самых дискуссионных в науке: в обиходе информацией называют любые данные или сведения, которые кого-либо интересуют, неизвестные раньше ; в технике под информацией понимают сообщения, передаваемые в форме знаков или сигналов; в кибернетике под информацией понимает ту часть знаний, которая используется для ориентирования, активного действия, управления, т.е. в целях сохранения, совершенствования, развития системы (Н. Винер).

Изображение слайда
4

Слайд 4: 2

Существуют 3 наиболее распространенные концепции информации, каждая из которых по-своему объясняет ее сущность. Первая концепция ( концепция К. Шеннона), отражая количественно-информационный подход, определяет информацию как меру неопределенности (энтропию) события. Количество информации в том или ином случае зависит от вероятности его получения: чем более вероятным является сообщение, тем меньше информации содержится в нем. При таком понимании информация - это снятая неопределенность, или результат выбора из набора возможных альтернатив. Для расчета энтропии Шеннон предложил уравнение H = ∑ P i  log 2  1/ P i  = -∑ P i  log 2    P i, где Н – энтропия Шеннона,  P i   - вероятность некоторого события.

Изображение слайда
5

Слайд 5: 3

Вторая концепция рассматривает информацию как свойство материи. Ее появление связано с развитием кибернетики и основано на утверждении, что информацию содержат любые сообщения, воспринимаемые человеком или приборами. Наиболее ярко и образно эта концепция информации выражена академиком В.М. Глушковым. Он писал, что "информацию несут не только испещренные буквами листы книги или человеческая речь, но и солнечный свет, складки горного хребта, шум водопада, шелест травы". То есть, информация как свойство материи создает представление о ее природе и структуре, упорядоченности и разнообразии. Она не может существовать вне материи, а значит, она существовала и будет существовать вечно, ее можно накапливать, хранить и перерабатывать.

Изображение слайда
6

Слайд 6: 4

Третья концепция основана на логико-семантическом подходе, при котором информация трактуется как знание, причем не любое знание, а та его часть, которая используется для ориентировки, для активного действия, для управления и самоуправления. Иными словами, информация - это действующая, полезная часть знаний. Представитель этой концепции В. Г. Афанасьев, развивая логико-семантический подход, дает определение социальной информации : "Информация, циркулирующая в обществе, используемая в управлении социальными процессами, является социальной информацией. Она представляет собой знания, сообщения, сведения о социальной форме движения материи и о всех других формах в той мере, в какой она используется обществом..."

Изображение слайда
7

Слайд 7: 5

Информация - сведения, снимающие неопределенность об окружающем мире, которые являются объектом хранения, преобразования, передачи и использования Одно и то же информационное сообщение (статья в газете, объявление, письмо, телеграмма, справка, рассказ, чертёж, радиопередача и т.п.) может содержать разное количество информации для разных людей — в зависимости от их предшествующих знаний, от уровня понимания этого сообщения и интереса к нему. Информация есть характеристика не сообщения, а соотношения между сообщением и его потребителем. Без наличия потребителя, хотя бы потенциального, говорить об информации бессмысленно. Применительно к компьютерной обработке данных под информацией понимают некоторую последовательность символических обозначений (букв, цифр, закодированных графических образов и звуков и т.п.), несущую смысловую нагрузку и представленную в понятном компьютеру виде. Каждый новый символ в такой последовательности символов увеличивает информационный объём сообщения.

Изображение слайда
8

Слайд 8: 6

Представление и классификация информации Информация может существовать в виде: текстов, рисунков, чертежей, фотографий; световых или звуковых сигналов; радиоволн; электрических и нервных импульсов; магнитных записей; жестов и мимики; запахов и вкусовых ощущений; хромосом, посредством которых передаются по наследству признаки и свойства организмов и т.д.

Изображение слайда
9

Слайд 9: 7

1. Информация подразделяется по форме представления на 2 вида: - дискретная форма представления информации - это последовательность символов, характеризующая прерывистую, изменяющуюся величину (количество дорожно-транспортных происшествий, количество студентов и т.п.); - аналоговая или непрерывная форма представления информации - это величина, характеризующая процесс, не имеющий перерывов или промежутков (температура тела человека, скорость автомобиля на определенном участке пути и т.п.).

Изображение слайда
10

Слайд 10: 8

2. По области возникновения выделяют информацию: - элементарную (механическую), которая отражает процессы, явления неодушевленной природы; - биологическую, которая отражает процессы животного и растительного мира; - социальную, которая отражает процессы человеческого общества. 3. По способу передачи и восприятия различают следующие виды информации: - визуальную, передаваемую видимыми образами и символами; - аудиальную, передаваемую звуками; - тактильную, передаваемую ощущениями; - органолептическую, передаваемую запахами и вкусами; - машинную, выдаваемую и воспринимаемую средствами вычислительной техники.

Изображение слайда
11

Слайд 11: 9

4. По способам кодирования выделяют следующие типы информации: числовую; текстовую, основанную на использовании комбинаций символов. Здесь используются символы: буквы, цифры, математические знаки; графическую, основанную на использовании произвольного сочетания в пространстве графических примитивов. К этой форме относятся фотографии, схемы, чертежи, рисунки. Свойства информации можно рассматривать в трех аспектах: техническом - это точность, надежность, скорость передачи сигналов и т.д.; семантическом - это передача смысла текста с помощью кодов и прагматическом - это насколько эффективно информация влияет на поведение объекта.

Изображение слайда
12

Слайд 12: 10

1.3 Передача информации Информация передаётся в форме сообщений от некоторого источника информации к её приёмнику посредством канала связи между ними. Источник посылает передаваемое сообщение, которое кодируется в передаваемый сигнал. Этот сигнал посылается по каналу связи. В результате в приёмнике появляется принимаемый сигнал, который декодируется и становится принимаемым сообщением.   Примеры: Cообщение, содержащее информацию о прогнозе погоды, передаётся приёмнику (телезрителю) от источника — специалиста-метеоролога посредством канала связи — телевизионной передающей аппаратуры и телевизора. Живое существо своими органами чувств воспринимает информацию из внешнего мира, перерабатывает её в определенную последовательность нервных импульсов, передает импульсы по нервным волокнам, хранит в памяти в виде состояния нейронных структур мозга, воспроизводит в виде звуковых сигналов, движений и т.п., Передача информации по каналам связи часто сопровождается воздействием помех, вызывающих искажение и потерю информации.

Изображение слайда
13

Слайд 13: 11

1.4 Измерение количества информации А возможно ли объективно измерить количество информации? В качестве единицы информации Клод Шеннон предложил принять  один   бит    ( англ. bit — binary digit — двоичная цифра). Бит в теории информации — количество информации, необходимое для различения двух равновероятных сообщений   (типа "орел"—"решка", "чет"—"нечет" и т.п.). В вычислительной технике битом называют наименьшую "порцию" памяти компьютера, необходимую для хранения одного из двух знаков "0" и "1", используемых для внутримашинного представления данных и команд. 1 байт= 8 бит,  Именно восемь битов требуется для того, чтобы закодировать любой из 256 символов алфавита клавиатуры компьютера (256=2 ^ 8). 1 Килобайт (Кбайт) = 1024 байт = 2 ^ 10 байт, 1 Мегабайт (Мбайт) = 1024 Кбайт = 2 ^ 20 байт, 1 Гигабайт (Гбайт) = 1024 Мбайт = 2 ^ 30 байт. 1 Терабайт (Тбайт) = 1024 Гбайт = 2 ^ 40 байт, 1 Петабайт (Пбайт) = 1024 Тбайт = 2 ^ 50 байт.

Изображение слайда
14

Слайд 14: 12

1.5. Свойства информация Достоверность. Достоверная информация со временем может стать недостоверной, так как она обладает свойством устаревать 1 Понятность. Информация становится понятной, если она выражена языком, на котором говорят те, кому предназначена эта информация. 3 Доступность. Информация должна преподноситься в доступной (по уровню восприятия) форме. 4 Полнота. Информация полна, если её достаточно для понимания и принятия решений. 2 Ценность. Ценность информации зависит от того, насколько она важна для решения задачи 5 Своевременность. Только своевременно полученная информация может принести ожидаемую пользу. 6

Изображение слайда
15

Слайд 15: 13 2 Современные методологии и языки программирования высокого уровня. Классификация языков программирования

Методология программирования – совокупность методов, применяемых в процессе разработки программ методология императивного программирования языки программирования: FORTRAN (1954), ALGOL (1960), PASCAL (1972), C (1974) методология объектно-ориентированного программирования языки программирования: Simula (1962), Smalltalk (1972), C++ (1983), Object Pascal (1984), Java (1995), C# (2000) методология функционального программирования языки программирования: LISP (1958), Refal (1968), Miranda (1985), F# (2002) методология логического программирования языки программирования: PROLOG (1971) методология программирования в ограничениях языки программирования: УТОПИСТ (1980), IDEAL (1981), OPS5 (1987) Ядра методологий определяются способом описания алгоритма.

Изображение слайда
16

Слайд 16: 14

Понятие алгоритмического языка Языки программирования ( алгоритмические языки ) – специально разработанные искусственные языки, предназначенные исключительно для записи алгоритмов, исполнение которых поручается ЭВМ. Наиболее общей классификацией языков программирования является по степени зависимости от машинного языка: Машинно-зависимые – машинные, машинно-ориентированные – низкий уровень Машинно-независимые – процедурные, проблемные – высокий уровень Машинно-зависимые языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, адресности, структуры памяти и т.д.). Машинный язык – это система команд компьютера. Программы, написанные на машинном языке не требуют компиляции. Пример фрагмента программы для трехадресной ЭВМ: 001 0 0 1 1 0 1 1 0 0 1 0 1 код операции адрес 1-го операнда адрес 2-го операнда адрес результата Машинно-ориентированные языки - языки символического кодирования: (Автокод, Ассемблер). Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена, например: ADD 1, B

Изображение слайда
17

Слайд 17: 15

Языки программирования высокого уровня машинно-независимы, т.к. они ориентированы не на систему команд той или иной ЭВМ, а на систему операндов, характерных для записи определенного класса алгоритмов. Однако программы, написанные на языках высокого уровня, занимают больше памяти и медленнее выполняются, чем программы на машинных языках. В  процедурных языках программа явно описывает действия, которые необходимо выполнить, а результат задается только способом получения его при помощи некоторой процедуры, которая представляет собой определенную последовательность действий. Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал. Проблемно-ориентированные языки предназначены для пользователей-непрограммистов и направлены для решения узкого круга задач. На них определяется что делать, а не как это делать. К непроцедурному программированию относятся функциональные и логические языки

Изображение слайда
18

Слайд 18: Бурное развитие языков…

18

Изображение слайда
19

Слайд 19: 17 Семантика языков

Изображение слайда
20

Слайд 20: 18

2. 5 Основные понятия императивного языка программирования Обычный разговорный язык состоит из четырех основных элементов: символов, слов, словосочетаний и предложений. Алгоритмический язык содержит подобные элементы, только слова называют элементарными конструкциями, словосочетания - выражениями, предложения - операторами. Алгоритмический язык (как и любой другой язык), образуют три его составляющие: алфавит, синтаксис и семантика. Алфавит – фиксированный для данного языка набор символов (букв, цифр, специальных знаков и т.д.), которые могут быть использованы при написании программы. Синтаксис - правила построения из символов алфавита специальных конструкций, с помощью которых составляется алгоритм. Семантика - система правил толкования конструкций языка. Таким образом, программа составляется с помощью соединения символов алфавита в соответствии с синтаксическими правилами и с учетом правил семантики.

Изображение слайда
21

Слайд 21: 19

Методология императивного программирования – это исторически первая поддерживаемая аппаратно методология программирования. Она ориентирована на модель фон Неймана. Императивное программирование пригодно для решения задач, в которых последовательное исполнение каких-либо команд является естественным. Основным синтаксическим понятием является оператор. Первая группа – атомарные или простые операторы, у которых никакая их часть не является самостоятельным оператором, например оператор присваивания, оператор перехода, оператор вызова процедуры. Вторая группа – структурные (составные) операторы, объединяющие другие операторы в новый, более крупный оператор, например, составной оператор, оператор цикла, операторы выбора. Для описания синтаксиса языка программирования будет использована расширенная система обозначений Бэкуса-Наура. В ней одни понятия определяются через другие последовательно. Основные понятия заключаются в угловые скобки. Символ ::= означает «определяется как» Символ | означает «или» Символ * означает «произвольное количество повторений (в том числе ноль раз) того символа, за которым он указан» Символы, указанные в квадратных скобках, являются необязательными.

Изображение слайда
22

Слайд 22: 20

< оператор > ::= < простой оператор > | < структурный оператор > < простой оператор > ::= < оператор присваивания > | < оператор вызова > < структурный оператор > ::= < оператор последовательного исполнения > | < оператор ветвления > | < оператор цикла > < оператор присваивания > ::= < переменная > = < выражение > < оператор вызова > ::= < имя подпрограммы >[ ( < параметр > * ) ] < оператор последовательного исполнения > ::= begin < оператор > * end < оператор ветвления > ::= if < логическое выражение > then < оператор > * [ else < оператор > *] < оператор цикла > ::= while < логическое выражение > do < оператор >

Изображение слайда
23

Слайд 23: 21

< оператор > ::= < простой оператор > | < структурный оператор > < простой оператор > ::= < оператор присваивания > | < оператор вызова > < структурный оператор > ::= < оператор последовательного исполнения > | < оператор ветвления > | < оператор цикла > < оператор присваивания > ::= < переменная > = < выражение > < оператор вызова > ::= < имя подпрограммы >[ ( < параметр > * ) ] < оператор последовательного исполнения > ::= begin < оператор > * end < оператор ветвления > ::= if < логическое выражение > then < оператор > * [ else < оператор > *] < оператор цикла > ::= while < логическое выражение > do < оператор >

Изображение слайда
24

Слайд 24: 3 Алгоритмы и программы. Основные алгоритмические управляющие структуры. Стиль программирования

Изображение слайда
25

Слайд 25: 23

Математическая постановка представляет описание задачи с помощью математических выражений и/или словесное описание частей задачи и логических связей между ними. Под алгоритмом решения задачи будем понимать конечную последовательность действий, определяющую процесс переработки исходных данных в результат. Выбор метода решения необходим при наличии нескольких методов решения математически формализованной задачи. Алгоритмический язык представляет собой набор символов, систем правил написания (синтаксиса) и истолкования (семантики) конструкций из этих символов, предназначенных для описания алгоритмов. Ввод программы в ЭВМ осуществляется с помощью клавиатуры или из внешней памяти или из компьютерной сети. При необходимости программа "переводится" на машинный язык с помощью специальных программ - трансляторов или интерпретаторов. Отладка программы представляет собой процесс обнаружения и исправления ошибок. Тестирование - установление факта достоверности получаемых результатов. Правильность работы программы устанавливается с помощью специальных контрольных просчетов – тестов. Для тестов подбираются наборы исходных данных, для которых заранее известен результат. Анализ результатов тестирования (сравнение полученных на ЭВМ с ожидаемыми) позволяет выявить ошибки в алгоритме и программе.

Изображение слайда
26

Слайд 26: 24

2.3 Алгоритм и его свойства Разработка алгоритма предполагает установление последовательности вычислительных действий, управляющих связей и проверок логических условий, а также определение действий ЭВМ по вводу данных и выводу результатов. Термин "алгоритм" произошел от имени средневекового узбекского математика Аль Хорезми, который еще в 9-м веке предложил правила выполнения 4-х арифметических действий в десятичной системе счисления. Алгоритм – конечная последовательность действий, ведущая от исходных данных к результату. Алгоритмизация не является только прерогативой математики. В обычной жизни всякой целенаправленной деятельности сопутствует заранее созданный алгоритм. таким образом, алгоритм можно трактовать как технологическую инструкцию из отдельных предписаний, выполнение которых в заданной последовательности приводит к заранее предвидимому результату. Основные свойства алгоритмов: Массовость - возможность использовать один алгоритм для решения серии однотипных задач с различными вариантами исходных данных. Однозначность или детерминированность - алгоритм должен содержать конечное число предписаний, не допускающих произвола исполнителя, не оставляющих исполнителю свободы выбора. Многократное повторение алгоритма с одинаковыми исходными данными должно приводить к одному и тому же результату. Дискретность - разделение выполнения решения задачи на отдельные операции. Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Конечность - возможность получения результата через конечное число шагов, выполненных за конечное время. Несмотря на кажущуюся очевидность последнего свойства, оно является чрезвычайно важным, так как очень часто создаются бесконечные алгоритмы. Такая ситуация в программировании носит название «зацикливание».

Изображение слайда
27

Слайд 27: 25

Способы записи алгоритмов Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов: - вербальный, когда алгоритм описывается на естественном языке; - символьный, когда алгоритм описывается с помощью набора символов; - графический, когда алгоритм описывается с помощью набора графических изображений. Текстовая запись алгоритмов имеет следующие недостатки: неоднозначность слов и понятий; отсутствие наглядности. Первого недостатка удается избежать, если для описания алгоритмов использовать псевдокоды. В этом случае используются не любые слова естественного языка, а вполне определенные: начало, конец, ввод, вывод, если … и т.д. Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

Изображение слайда
28

Слайд 28: 26

Блок-схема отличается следующим: каждому действию соответствует определенный вид фигуры (овал, прямоугольник, параллелограмм, ромб, шестиугольник); внутри фигур записываются формулы или краткая инструкция; фигуры соединяются линиями со стрелками, которые называются линиями потока и указывают направления перехода от одной операции к другой. Причем, если выбирается направление вниз или вправо, то стрелки можно не ставить; фигуры или блоки в блок-схемах могут иметь номера, проставляемые слева в разрыве верхней линии; линии потока не должны пересекаться, поэтому при необходимости используются соединители – элементы с буквой или цифрой внутри. Конфигурация элементов схем определена ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем»

Изображение слайда
29

Слайд 29: 27

Блок-схема отличается следующим: каждому действию соответствует определенный вид фигуры (овал, прямоугольник, параллелограмм, ромб, шестиугольник); внутри фигур записываются формулы или краткая инструкция; фигуры соединяются линиями со стрелками, которые называются линиями потока и указывают направления перехода от одной операции к другой. Причем, если выбирается направление вниз или вправо, то стрелки можно не ставить; фигуры или блоки в блок-схемах могут иметь номера, проставляемые слева в разрыве верхней линии; линии потока не должны пересекаться, поэтому при необходимости используются соединители – элементы с буквой или цифрой внутри. Конфигурация элементов схем определена ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем»

Изображение слайда
30

Слайд 30: 28пример блок-схемы

Изображение слайда
31

Слайд 31: 29

В 1977 году математики Бем и Якопини доказали, что алгоритмы сколь угодно сложной структуры могут быть реализованы с использованием всего 3-х управляющих структур: Последовательное выполнение операций - следование ; Ветвление алгоритма на группы операций в зависимости от выполнения некоторых условий - ветвление ; Циклическое многократное выполнение группы операций до выполнения некоторого условия, формируемого в процессе вычислений - цикл. Соответствующие операторы в записи алгоритмов называются условными операторами и операторами циклов (следование не имеет специального оператора и выражается просто последовательной записью инструкций вычисления, ввода, вывода).

Изображение слайда
32

Слайд 32: 30

Условные операторы в наших примерах звучат как: если < условие выполнено > то последовательность операций иначе другая последовательность операций. Операторы циклов в описаниях на естественном языке мы формулируем словами: 1. "Пока истинно некоторое условие - повторять заданные действия" (цикл с предусловием); 2. "Повторять заданные действия пока ложно некоторое условие" (цикл с постусловием); 3. "Повторять заданные действия N раз" (цикл со счетчиком).

Изображение слайда
33

Слайд 33: 31

Программа - 1) Упорядоченная последовательность команд обработки данных 2) Последовательность предложений языка программирования, описывающая последовательность решения задачи 3) Завершенный продукт, пригодный для запуска своим автором на системе, на которой он разработан. Программный продукт – программа, которую любой специалист может запускать, тестировать. Программное средство – программа или совокупность программ, снабженная программной документацией. Стиль программирования - набор приемов или методов программирования, которые и используют программисты, чтобы получить правильные, эффективные,  удобные для применения и легкочитаемые программы.

Изображение слайда
34

Слайд 34: 32

Хороший стиль программирования Последовательность кода. Один из признаков хорошего стиля программирования — последовательность — чем меньше сюрпризов, тем лучше. Ясность кода. Хороший стиль нужен для того, чтобы ваша программа была ясна и понятна, а также легко изменяемая. Пробелы и форматирование. Пробелы могут уменьшить нагрузку на глаза читателя. Пробелы используются для форматирования отступов, пространства вокруг операторов, подписи функций и размещения аргументов функций. Отступ. Вам следует делать отступы в каждом блоке кода. Соглашения об именовании. Как правило, лучше выбрать набор соглашений об именовании для использования во всем коде. Соглашения об именовании обычно регулируют такие вещи, как использование переменных, классов и функций, будете ли вы включать префикс для указателей, статические или глобальные данные, и как вы указываете то, что является закрытым полем класса.

Изображение слайда
35

Слайд 35: 33

Стиль программирования — это набор правил, которым следует программист (осознано или потому, что "так делают другие") в процессе своей работы. Очевидно, что хороший программист должен следовать правилам хорошего стиля. Хороший стиль программирования предполагает: использование комментариев; использование несущих смысловую нагрузку имен переменных, процедур и функций; использование отступов; использование пустых строк. Следование правилам хорошего стиля программирования значительно уменьшает вероятность появления ошибок на этапе набора текста, делает программу легко читаемой, что, в свою очередь, облегчает процессы отладки и внесения изменений. Четкого критерия оценки степени соответствия программы хорошему стилю программирования не существует. Вместе с тем достаточно одного взгляда, чтобы понять, соответствует программа хорошему стилю или нет. Сводить понятие стиля программирования только к правилам записи текста программы было бы неверно. Стиль, которого придерживается программист, проявляется во время работы программы. Хорошая программа должна быть прежде всего надежной и дружественной по отношению к пользователю. Надежность подразумевает, что программа, не полагаясь на "разумное" поведение пользователя, контролирует исходные данные, проверяет результат выполнения операций, которые по какой-либо причине могут быть не выполнены, например, операций с файлами. Дружественность предполагает хорошо спроектированные диалоговые окна, наличие справочной системы, разумное и предсказуемое, с точки зрения пользователя, поведение программы.

Изображение слайда
36

Слайд 36: 34 4. Процедуры и функции. Параметры и аргументы процедуры (функции). Передача аргументов в функции (процедуры) по значению и по ссылке. Локальные и глобальные переменные. Вложенные процедуры. Организация рекурсии

Процедуры и функции позволяют включать в основной программный блок дополнительные блоки. Каждое описание процедуры или функции содержит заголовок, за которым следует программный блок. Процедура активизируется с помощью оператора процедуры. Функция активизируется при вычислении выражения, содержащего вызов функции, и возвращаемое функцией значение подставляется в это выражение. Описание процедуры позволяет связать идентификатор с процедурным блоком. Процедуру можно затем активизировать с помощью оператора процедуры.

Изображение слайда
37

Слайд 37: 35

Функции и процедуры Подпрограммой (п/п) называется поименованная, логически законченная группа операторов языка, которую можно запустить на выполнение по имени любое количество раз из различных мест программы. Существуют подпрограммы двух видов: процедуры и функции. Процедуры и функции дают возможность снабдить последовательность операторов именем и обращаться к ней с помощью этого имени из любых частей программы. Подпрограммы решают три важные задачи: • избавляют от необходимости многократно повторять в тексте программы аналогичные фрагменты; • улучшают структуру программы, облегчая ее понимание; • повышают устойчивость к ошибкам программирования и непредвидимым последствиям при модификациях программы.

Изображение слайда
38

Слайд 38: 36

Использование п/п оправдано в следующих случаях: Последовательность операторов повторяется в программе несколько раз с различными параметрами. Большая программа разделяется на части, реализующие отдельные подзадачи, что делает эту программу более обозримой, надежной и удобной для отладки. В виде п/п представляются стандартные, часто используемые алгоритмы, которые могут быть использованы в любых программах. В языке Паскаль существуют стандартные процедуры и функции, используемые нами ранее, например : delete, sin, clrscr, ord, copy, odd, inc, trunc, read и т.д. Стандартная подпрограмма (процедура или функция) - подпрограмма, включенная в библиотеку программ ЭВМ, доступ к которой обеспечивается средствами языка программирования. Вызывается она по имени с заданием фактических параметров определенного типа. Стандартные процедуры и функции расположены в модулях System, Graph, Crt. Подпрограммы, определяемые пользователем, имеет такой же набор разделов, как и основная программа.

Изображение слайда
39

Слайд 39: 37

В заголовке п/п используются формальные параметры. Формальные параметры – это список входных и выходных параметров, через которые подпрограмма осуществляет взаимодействие с основной программой. Формальные параметры удовлетворяют следующим требованиям : при вызове п/п заменяются фактическими; резервируют место под фактические параметры; при вызове фактические параметры должны совпадать с формальными параметрами по: числу, типу, месту в списке; имена формальных параметров выбираются произвольно.

Изображение слайда
40

Слайд 40: 38

Функции Функция – это подпрограмма, вызываемая в выражениях в качестве операнда и вычисляющая значение данных простого типа. Функция может содержать параметры, осуществляющие ее взаимодействие с основной программой. Формат объявления функции: Function <имя функции> [(формальные параметры)] : <тип результата>; [<разделы объявления локальных данных>]         begin             <исполняемый раздел>         end; где тип результата – тип данных возвращаемого результата, один из простых типов. В точке вызова функции происходит неявное присваивание фактических значений формальным переменным, имена которых перечислены в заголовке функции при ее описании. В разделе операторов функции обязательно должен присутствовать оператор присваивания вида: <имя функции>:=<выражение>; Этот оператор определяет значение, которое будет возвращено функцией в точку ее вызова. Пример 1 объявления функции, вычисляющей сумму трех чисел: Function Summa (x, y, z: real) : real; begin Summa := x + y + z; end; Здесь x, y, z – формальные параметры

Изображение слайда
41

Слайд 41: 39

Функции Функция – это подпрограмма, вызываемая в выражениях в качестве операнда и вычисляющая значение данных простого типа. Функция может содержать параметры, осуществляющие ее взаимодействие с основной программой. Формат объявления функции: Function <имя функции> [(формальные параметры)] : <тип результата>; [<разделы объявления локальных данных>]         begin             <исполняемый раздел>         end; где тип результата – тип данных возвращаемого результата, один из простых типов. В точке вызова функции происходит неявное присваивание фактических значений формальным переменным, имена которых перечислены в заголовке функции при ее описании. В разделе операторов функции обязательно должен присутствовать оператор присваивания вида: <имя функции>:=<выражение>; Этот оператор определяет значение, которое будет возвращено функцией в точку ее вызова. Пример 1 объявления функции, вычисляющей сумму трех чисел: Function Summa (x, y, z: real) : real; begin Summa := x + y + z; end; Здесь x, y, z – формальные параметры

Изображение слайда
42

Слайд 42: 40

При работе с п/п рекомендуется использовать инструкцию, которую обычно размещают в виде комментариев Инструкция при работе с подпрограммами Назначение подпрограммы, используемые методы Классификация параметров: а) входные параметры б) выходные параметры в) внутренние параметры Другие подпрограммы, вызываемые данной подпрограммой

Изображение слайда
43

Слайд 43: 41

Запуск функции на исполнение осуществляется указанием имени функции и списка фактических параметров, отделенных друг от друга запятыми и заключенных в круглые скобки. Формат вызова функции: <имя функции> [(фактические параметры)] Пример вызова функции Summa: k := Summa (a, b, 7) / Sin (a – b); В качестве фактических параметров могут быть выражения. Пример 2 объявления функции, вычисляющий десятичный логарифм Function Lg ( z : real) : real; begin lg := ln(z)/ln(10) ; end; Пример вызова функции lg : y := (lg(3*x)+2*lg(a))/ (lg(a+b) – lg(sqr(x)));

Изображение слайда
44

Слайд 44: 42

Процедуры Процедура – это подпрограмма, запускаемая на выполнение из программы оператором вызова процедуры и осуществляющая связь с основной программой через параметры. Формат объявления процедуры: Procedure <имя процедуры> [(<список входных параметров>[; var <выходные параметры>])]; [<разделы объявления локальных данных>]         begin              <исполняемый раздел>         end; где <имя> - идентификатор процедуры (те же ограничения, что и для функции); <список параметров> - список аргументов процедуры с указанием их типов (список параметров-значений); var   <выходные параметры>- имя параметров-переменных, т.е. тех переменных, значение которых будет возвращено в точку вызова процедуры. Процедура может не содержать никаких параметров. В этом случае выполняются операторы, стоящие в теле процедуры. Если же в заголовке процедуры указаны параметры, то в точке вызова процедуры происходит неявное присваивание фактических значений параметрам-значениям (входным параметрам), а по окончании действия процедуры в точку вызова возвращаются значения параметров-переменных (выходных параметров). Формальные параметры в заголовке процедуры отделяются друг от друга точкой с запятой. Каждый формальный параметр задаются в формате: [ Var ] <идентификатор> : <тип данных>

Изображение слайда
45

Слайд 45: 43

Разделы объявления данных и исполняемый раздел имеют такой же смысл и формат, как и в программе. Пример объявления процедуры: Procedure proc ( a : integer ; var b, c : integer ); begin if a > 5 then b := a else c := a end ; В процедуре proc объявлен параметр-значение а и параметры-переменные b и с целого типа. Запуск процедуры на исполнение осуществляется оператором вызова процедуры. Он состоит из имени процедуры и списка фактических параметров, отделенных друг от друга запятыми и заключенных в круглые скобки. Формат оператора вызова процедуры: <имя процедуры> [(фактические параметры)]; Пример вызова процедуры proc: proc (10,y,z); Список фактических параметров должен отсутствовать, если в заголовке объявления процедуры отсутствовал список формальных параметров. Каждый фактический параметр должен соответствовать (в порядке следования) формальному параметру, указанному в заголовке, и иметь тот же тип.

Изображение слайда
46

Слайд 46: 44

Локальные и глобальные переменные. Переменные описываются в программе в разделе описания переменных. Если же программа содержит описание процедуры или функции, то некоторые переменные могут быть описаны в этой процедуре или функции в разделе локальных описаний. Глобальными называются переменные, объявленные в основной программе и доступные как программе, так и всем ее подпрограммам. Ими можно пользоваться и в главной программе, и в процедуре или функции. Локальными называются переменные, объявленные внутри подпрограммы и доступные только ей самой. Ими можно пользоваться только в той процедуре или функции, где они описаны. Вне тела процедуры или функции значения таких переменных не определены. Обмен информацией между основной программой и подпрограммой может осуществляться только с помощью глобальных переменных. При использовании локальных переменных необходимо следить за тем, чтобы их идентификаторы не совпадали с именами глобальных переменных. Если процедура или функция изменяет значение глобальной переменной, то говорят, что она имеет побочный эффект.

Изображение слайда
47

Слайд 47: 45

Заголовки процедур именуют идентификаторы процедур и задают формальные параметры (если они имеются). Процедура активизируется с помощью оператора процедуры, в котором содержатся имя процедуры и необходимые параметры. Опера- торы, которые должны выполняться при запуске процедуры, содержатся в операторной части модуля процедуры. Если в содержащемся в процедуре операторе внутри модуля процедуры используется идентификатор процедуры, то процедура будет выполняться рекурсивно (будет при выполнении обращаться сама к себе). Приведем пример описания процедуры: procedure NumString (N: integer ; var S: string ); var V: integer ; begin V := Abs (N); S := ''; repeat S := Chr (N mod 10 + Ord ('0')) + S; N := N div 10; until N = 0; if N < 0 then S := '-' + S; end ;

Изображение слайда
48

Слайд 48: 46

Функции и процедуры: Рекурсия Рекурсия  — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается  сама к себе. Вообще,  рекурсивным  называется любой объект, который частично определяется через себя. Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит. Приведём примеры рекурсивных определений. Пример 1.  Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n ! = 1 * 2 * 3 *...* n.

Изображение слайда
49

Слайд 49: 47

С другой стороны, Граничным условием в данном случае является  n <=1. Пример 1 рекурсивной функции вычисления факториала Function factorial(N: integer) : longint;  Begin     If N= 0 then     Factorial := 1     Else Factorial := factorial(N-1) * N  End;

Изображение слайда
50

Слайд 50: 48

Функции и процедуры: Рекурсия Рекурсивные процедуры и функции (подпрограммы) имеют одну из двух форм:  прямую  рекурсию и  косвенную  рекурсию. В первом случае подпрограмма содержит оператор вызова этой же подпрограммы (как в примере с процедурой REVERSE). Во втором случае одна подпрограмма вызывает другую подпрограмму, которая либо сама, либо посредством других процедур или функций вызывает исходную подпрограмму. Если А,В - имена подпрограмм, то схема вызова может быть такой: А-В-А. В случае косвенной рекурсии возникает проблема: как и где описать вызываемую подпрограмму. По правилам языка Паскаль каждая подпрограмма должна быть описана до её вызова. Но если подпрограмма А вызывает В, а В вызывает А, то получается замкнутый круг. Для подобных ситуаций принято следующее правило: одна из рекурсивных подпрограмм, вызывающих друг друга, описывается предварительно следующим образом:

Изображение слайда
51

Слайд 51: 49

Функции и процедуры: Рекурсия PROCEDURE P(<Список формальных параметров>); FORWARD ; Здесь P - имя процедуры,  FORWARD  - ключевое слово. Это описание указывает транслятору, что текст процедуры Р помещен ниже. Подобным же образом описывается функция: к оператору  FUNCTION  добавляется слово  FORWARD. Список формальных параметров и тип результата (для  FUNCTION ) включается только в это предварительное описание и опускается в заголовке соответствующей функции. Пример3. Пусть функция В при работе вызывает функцию А которая, в свою очередь, вызывает функцию В. Тогда эти модули можно описать так: FUNCTION B(X: INTEGER ): REAL ; FORWARD ; FUNCTOIN A(Y: INTEGER ): REAL ; BEGIN :. A:=B(I)+3.5; END ; FUNCTION B; BEGIN.......... B:=A(D)-1.8; END ; Заголовок ( FUNCTON  B) перед текстом функции В содержит только имя функции, а список формальных параметров и тип функции не указываются.

Изображение слайда
52

Слайд 52: 5 Структуры данных. Классические структуры данных: массивы, списки, деревья. Стеки и очереди

Под массивом в программировании будем понимать упорядоченную конечную группу данных одного типа. Индекс указывает порядковый номер элемента массива. Он может быть числом или выражением целого типа ( в общем случае любого порядкового типа) Количество элементов,содержащихся в массиве, называется его размерностью. В зависимости от числа индексов, массивы бывают одномерными, двумерными, и т. д. Формат объявления массива: Type <имя типа> = array [<тип индекса>] of <тип компонент>; Var <идентификатор> [,<идентификатор>] : <имя типа>; Тип индекса – один из порядковых типов, чаще всего диапазон, например: 1..10. Тип компонент – может быть любым, кроме файла и множества. Массив может быть объявлен также непосредственно при описании переменной в разделе описания переменных: Var <идентификатор [,<идентификатор> * ] : array [<тип индекса>] of <тип компонент>; Примеры объявления массива: Type r = array [1.. 10] of real ; Var mas_int : array [1.. 45] of integer ; mas_rel : r;

Изображение слайда
53

Слайд 53: 51

Тип данных Массив позволяет одному идентификатору задать несколько значений, которые отличаются порядковым номером. Номер элемента массива указывается после идентификатора в квадратных скобках (M[5] – пятый элемент массива М). При описании массива указывается диапазон номеров элементов массива и тип, к которому относится каждый его элемент. Массивы могут быть одно-, двух- и многомерными. Пример описания и заполнения элементов массива. Var {описание массивов} M: array [1..5] of integer; {одномерный массив М с номерами элементов от 1 до 5, состоящий из целых чисел} M1: array [2..3,11..15] of char; {двумерный массив М1 с номерами строк от 2 до 3, с номерами столбцов от 11 до 15, состоящий из символов} Begin {заполнение массива} М[2]:=100; {второму элементу численного массива М присвоено значение 100} М1[2,3]:=’d’; {элементу второй строки и третьего столбца символьного двухмерного массива М1 присвоено значение ’d’}

Изображение слайда
54

Слайд 54: 52

Наиболее распространенные алгоритмы обработки одномерных массивов: нахождение суммы, произведения, среднего значения; нахождение суммы или количества элементов массива, удовлетворяющих некоторым условиям; нахождение минимального (максимального) элемента массива и его номера; создание нового массива из элементов имеющегося; поиск элемента в массиве по заданным критериям; сортировка элементов массива.

Изображение слайда
55

Слайд 55: 53

Представим алгоритм определение максимального оборота предприятия за данный период в виде блок-схемы начало i=1, 30 ввод A[i] M =A[1] i=2, 30 A[i]>M M=A[ I ] вывод M, NM конец Да Нет NM=i NM=1

Изображение слайда
56

Слайд 56

54

Изображение слайда
57

Слайд 57: 55

Часто в серьезных программах надо использовать данные, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку заранее нельзя сказать, сколько памяти надо выделить – это выясняется только в процессе работы. Например, надо проанализировать текст и определить, какие слова и в каком количество в нем встречаются, причем эти слова нужно расставить по алфавиту. В таких случаях применяют данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент (узел) состоит из двух областей памяти: поля данных и ссылок. Ссылки – это адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Си для организации ссылок используются переменные-указатели. При добавлении нового узла в такую структуру выделяется новый блок памяти и (с помощью ссылок) устанавливаются связи этого элемента с уже существу

Изображение слайда
58

Слайд 58: 56

На следующем уровне абстракции сугубо физические аспекты данных отходят на второй план вследствие введения  механизма доступа  ( data engine ) к данным, то есть механизма  сохранения  и  получения  информации. По существу, физические данные связываются с механизмом доступа, который управляет работой с данными из программы. Существует четыре механизма доступа: Очередь ( queue ) Стек ( stack ) Связанный список ( linked list ) Двоичное дерево ( binary tree ) Очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" ( first-in, first-out ); этот принцип (и очередь как структура данных) иногда еще называется FIFO Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается. В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.

Изображение слайда
59

Слайд 59: 57

Стек  ( stack ) является как бы противоположностью очереди, поскольку он работает по принципу "последним пришел — первым вышел" ( last-in, first-out, LIFO ). Чтобы наглядно представить себе стек, вспомните стопку тарелок. Первая тарелка, стоящая на столе, будет использована последней, а последняя тарелка, положенная наверх — первой. Стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы. При работе со стеками операции занесения и извлечения элемента являются основными. Данные операции традиционно называются " затолкать в стек" ( push )  и "вытолкнуть из стека« Связанные списки Очереди и стеки имеют две характерные особенности: обе структуры данных имеют строгие правила доступа к хранящимся в них данным, причем в результате выполнения операций извлечения данные, в сущности, уничтожаются. Другими словами, доступ к элементу в стеке или очереди приводит к его удалению, и если этот элемент не сохранить где-либо в другом месте, он теряется.

Изображение слайда
60

Слайд 60: 58

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

Изображение слайда
61

Слайд 61: 59

Динамические структуры Линейные односвязные списки (однонаправленные цепочки). Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой. Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.

Изображение слайда
62

Слайд 62

Выделим типовые операции над списками: добавление элемента в начало списка; удаление элемента из начала списка; добавление элемента в произвольное место списка, отличное от начала (например, после элемента, указатель на которое задан); удаление элемента из произвольного места списка, отличного от начала (например, после элемента, указатель на которое задан); проверка, пуст ли список; очистка списка; печать списка. 60

Изображение слайда
63

Слайд 63

Бинарные деревья В математике бинарным (двоичным) деревом называют конечное множество вершин, которое либо пусто, либо состоит из корня и не более чем двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Таким образом, каждая вершина бинарного дерева может включать одно или два поддерева или не включать поддеревьев вовсе. Первое поддерево обычно называют левым, а второе - правым. Соответственно ветвь, исходящую из вершины и ведущую в корень левого поддерева, называют левой, а ветвь, ведущую в корень правого поддерева - правой. Вершины, из которых не выходит ни одной ветви, называют листьями. В программах для реализации бинарных деревьев используют n -связные списки. С вершинами бинарного дерева обычно связывают записи, хранящие некоторую информацию. 61

Изображение слайда
64

Слайд 64

62 Корень дерева листья листья листья Левая ветвь Корень левого поддерева Правая ветвь Корень правого поддерева Рис. 1 Пример бинарного дерева

Изображение слайда
65

Слайд 65

Построение дерева выполняется следующим образом. Если дерево пусто, то первая же вершина становится корнем дерева. Добавление остальных вершин регламентируется в зависимости от условия задачи: в соответствии с заданной дисциплиной построения дерева отыскивается подходящая вершина, к которой и подсоединяется новая вершина. Достаточно часто используют регулярные бинарные деревья с разными законами построения. Примером могут служить сортированные бинарные деревья, построение которых осуществляется по правилу: ключевое поле левого поддерева всегда должно содержать значение меньше, чем в корне, а ключевое поле правого поддерева - значение больше или равное значению в корне. Рассмотрим основные операции с сортированными бинарными деревьями. 63

Изображение слайда
66

Слайд 66

Исходные установки. В начале программы необходимо описать элемент и его тип: Туре top_ptr = ^top; {тип «указатель на вершину»} top=record value: integer; { число } left, {указатель на левое поддерево} right:top _ ptr; {указатель на правое поддерево} end; Описываем указатель корня дерева и несколько указателей, используемых при выполнении операций с деревом: Var root, {указатель структуры - адрес корня дерева} pass, next, q : top _ ptr; {вспомогательные указатели} Исходное состояние - «пустое дерево»: root:=nil; 64

Изображение слайда
67

Слайд 67

1. Построение дерева. Дерево строится в соответствии с главным правилом. Например, пусть дана последовательность целых чисел {5, 2, 8, 7, 2, 9, 1, 5}. Первое число 5 будет записано в корень дерева (рис. 2, а). Второе число 2 меньше значения в корне дерева, следовательно, оно будет записано в левое поддерево (рис. 2, б). Следующее число 8 больше значения в корне, соответственно оно будет записано в правое поддерево (рис. 2, в). Следующее число 7 больше, чем значение в корне дерева, значит, оно должно быть записано в правое поддерево, но правое поддерево уже построено. Сравниваем 7 со значением в корне правого поддерева - числом 8. Так как добавляемое значение меньше значения в корне правого поддерева, то добавляем левое поддерево уже к этому корню (рис. 2, г). Полностью сформированное бинарное дерево представлено на рис. 3. 65

Изображение слайда
68

Слайд 68

66 5 2 8 7 1 2 6 9 Рис. 4. Обход дерева «слева направо»

Изображение слайда
69

Слайд 69: 6 Задачи поиска и сортировки. Алгоритмы поиска. Последовательный и бинарный поиск в упорядоченном массиве. Алгоритм сортировки обменами (метод пузырька). Алгоритм сортировки выбором

Поиск элементов массива по заданным критериям Примерами подобного рода задач могут служить поиск первого отрицательного, первого положительного и любого первого элемента, отвечающего некоторому условию, а также поиск единственного или определенного количества элементов, равных некоторому конкретному значению. Особенность задач этого класса в том, что нет необходимости просматривать весь массив. Просмотр можно закончить сразу, как только требуемый элемент будет найден. Однако в худшем случае для поиска элемента требуется просмотреть весь массив, причем нужного элемента в нем может не оказаться. а) Поиск первого элемента, удовлетворяющего заданным критериям Существует несколько методов поиска. Самый простой заключается в последовательном просмотре каждого элемента массива. Если массив не очень большой, затраты времени линейного поиска не столь заметны. Но при солидных объемах информации время поиска становится критичным. Поэтому существуют методы, позволяющие уменьшить время поиска, например двоичный поиск, который применяется только, если элементы массива сортированы по возрастанию или убыванию. Чаще всего при программировании поисковых задач используют циклы while или repeat, в которых условие выхода из цикла формируется из двух условий : 1) пока искомый элемент не найден, 2) пока есть элементы массива. После выхода из цикла осуществляют: проверку, по какому из условий произошел выход.

Изображение слайда
70

Слайд 70: 68

Для ускорения обработки можно реализовать двоичный (бинарный) поиск. Э т от метод применим, когда массив отсортирован по возрастанию значений. Метод двоичного поиска заключается в следующем : Определяют примерную середину массива проверяют, совпадает ли искомый элемент с элементом в середине массива. Если совпадает, поиск завершен. Если не совпадает, то, если искомый элемент меньше элемента, находящегося в с е ред и не, то поиск продолжают в левой половине массива, иначе - в правой половине. Таким образом, диапазон элементов на каждом шаге уменьшается больше, чем вдвое. Если диапазон сократился до нуля, а элемент не найден, то такой элемент в массиве отсутствует.

Изображение слайда
71

Слайд 71: 69

Пусть, к примеру, нужно найти элемент 6 в таком массиве: [2 4 6 8 10 12 14 16 18] Найдем элемент, стоящий в середине этого массива, ( 10 ) и сравним с ним 6. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения: [2 4 6 8] 10 12 14 16 18 Снова возьмем середину в отмеченной части массива, чтобы сравнить ее с 6. Однако здесь нас поджидает небольшая проблема: точной середины у нового массива нет, поэтому нужно решить, который из двух центральных элементов станет этой "серединой". От того, к какому краю будет смещаться выбор в таких "симметричных" случаях, зависит окончательная реализация нашего алгоритма. Давайте договоримся, что новой "серединой" массива всегда будет становиться левый центральный элемент. Это соответствует вычислению номера "середины" по формуле nomer_sred:= (nomer_lev + nomer_prav) div 2 { (1 + 4 ) div 2 =2} Итак, отсечем левую половину массива: 2 4 [6 8] 10 12 14 16 18 Из приведенных примера уже видно, что поиск ведется до тех пор, пока не будет найден элемент или левая граница не окажется правее(!) правой границы.

Изображение слайда
72

Слайд 72: 70

Алгоритмы сортировки Алгоритмы сортировки, предназначенные для упорядочивания расположения элементов (по алфавиту, по убыванию или возрастанию значений), являются важнейшими среди алгоритмов обработки массивов. Достоинство упорядоченного массива состоит в значительном облегчении поиска нужного элемента по сравнению с неупорядоченным массивом. Критериями оценки различных методов сортировки могут быть: количество сравнений и пересылок записей; время сортировки заданного объема данных; требуемый объем оперативной памяти для сортировки; сложность алгоритмов. Методы сортировки можно подразделить на внутренние (обрабатывающие массивы) и внешние (занимающиеся только обработкой файлов). Внутренние сортировки делятся на группы: сортировки посредством выбора; обменные сортировки; сортировки вставками; сортировки слиянием – объединение двух или более упорядоченных массивов в один. Эту лекцию мы посвятим только внутренним сортировкам. Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти: вся работа по упорядочению производится внутри одного и того же массива. Рассмотрим алгоритмы сортировки из первых трех групп. При этом будем использовать один массив вещественных чисел и выполнять сортировку по возрастанию значений элементов. Сортировка по убыванию производится аналогичным образом, отличия лишь в знаке операции отношения.

Изображение слайда
73

Слайд 73: 71

1 Сортировка простым выбором Алгоритм ПрВыб На каждом шаге (всего их будет ровно N -1) будем производить такие действия: 1) найдем минимум среди всех еще не упорядоченных элементов; 2) поменяем его местами с первым "по очереди" не отсортированным элементом. Последний (N-й) элемент массива автоматически окажется максимальным. Пример сортировки Предположим, что нужно отсортировать набор чисел: 5 3 4 3 6 2 1 Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а красным цветом выделен ее минимальный элемент): 1 шаг: 5 3 4 3 6 2 1 { меняем 1 и 5 местами } 2 шаг: 1 3 4 3 6 2 5 { меняем 2 и 3 местами } 3 шаг: 1 2 4 3 6 3 5 { меняем 3 и 4 местами } 4 шаг: 1 2 3 3 6 4 5 {ничего не делаем} 5 шаг: 1 2 3 3 6 4 5 { меняем 4 и 6 местами } 6 шаг: 1 2 3 3 4 6 5 { меняем 5 и 6 местами } результат: 1 2 3 3 4 5 6

Изображение слайда
74

Слайд 74: 72

Блок-схема алгоритма сортировки посредством выбора да I = 1, n-1 Ввод n i =1, n Ввод a [I] A Вывод а [ 1..n ] A нет a [j] ≤ a [m_i] m_i = i j = i + 1, n m_i : = j начало конец x : = a[ i ]; a[ i ] := a[ m_i ] a[ m_i ] := x

Изображение слайда
75

Слайд 75: 73

2 Сортировка прямыми обменами (метод пузырьков) Алгоритм ПрОбм На каждом шаге (пока есть перестановки) будем производить такие действия: - сравниваем каждый элемент, начиная с первого, с соседним; если он больше следующего, то меняем их местами. Таким образом элементы с меньшим значением продвинутся к началу массива («всплывут»), а элементы с большим значением – к концу массива («тонут»). Пример сортировки Предположим, что нужно отсортировать набор чисел: 5 3 4 3 6 2 1 Теперь мы будем придерживаться алгоритма ПрОбм (подчеркнуты переставляемые элементы): 1 шаг: 5 3 4 3 6 2 1 → 3 5 4 3 6 2 1 → 3 4 5 3 6 2 1 → 3 4 3 5 6 2 1 → 3 4 3 5 2 6 1 → 3 4 3 5 2 1 6 2 шаг: 3 4 3 5 2 1 6 → 3 3 4 5 2 1 6 → 3 3 4 2 5 1 6 → 3 3 4 2 1 5 6 3 шаг: 3 3 4 2 1 5 6 → 3 3 2 4 1 5 6 → 3 3 2 1 4 5 6 4 шаг: 3 3 2 1 4 5 6 → 3 2 3 1 4 5 6 → 3 2 1 3 4 5 6 5 шаг: 3 2 1 3 4 5 6 → 2 3 1 3 4 5 6 → 2 1 3 3 4 5 6 6 шаг: 2 1 3 3 4 5 6 → 1 2 3 3 4 5 6 результат: 1 2 3 3 4 5 6

Изображение слайда
76

Слайд 76: 74

Блок-схема алгоритма обменной сортировки ( методом пузырьков) да да Ввод n i =1, n Ввод a i A A k=n-1 k  1 f= true f f = false нет i=1, k a i ≤ a i+1 да p= a i a i = a i+1 a i+1 =p f= true k=k-1 нет нет Вывод a[ 1..n ] начало B B конец

Изображение слайда
77

Слайд 77: 7 Объектно-ориентированный подход в программировании. Понятие класса и объекта. Структура объекта. Поля, методы и свойства объектов. Создание и удаление объектов

Гради Буч: «Объектно-ориентированное программирование (ООП) – это методология программирования, которая основана на представлении программы в виде совокупности объектов, каждый из которых является реализацией (экземпляром) определенного класса (типа особого вида), а классы образуют иерархию на принципах наследуемости». Как следует из определения, ООП в отличие от процедурного программирования, базируется на объектной декомпозиции предметной области программы. ООП обладает рядом преимуществ при создании больших программ. В частности, к ним можно отнести: использование более естественных с точки зрения повседневной практики понятий, простота введения новых понятий; некоторое сокращение размера программ за счет того, что повторяющиеся (наследуемые) свойства и действия можно не описывать многократно, как это делается при использовании подпрограмм; кроме того, использование динамических объектов позволяет более эффективно использовать оперативную память; возможность создания библиотеки объектов;

Изображение слайда
78

Слайд 78

76 сравнительно простая возможность внесения изменений в программу без изменения уже написанных частей, а в ряде случаев и без перекомпиляции этих написанных и уже скомпилированных частей, используя свойства наследования и полиморфизма; возможность написания подпрограмм с различными наборами формальных параметров, но имеющих одно и то же имя, используя свойство полиморфизма; более четкая локализация свойств и поведения объекта в одном месте (используется свойство инкапсуляции), позволяющая проще разбираться со структурой программы, отлаживать ее, находить ошибки; возможность разделения доступа к различным объектам программы и т. д.

Изображение слайда
79

Слайд 79

77 Однако следует иметь в виду, что ООП обладает и рядом недостатков и эффективно не во всех случаях. Как правило, использование ООП приводит к уменьшению быстродействия программы, особенно в тех случаях, когда используются виртуальные методы Неэффективно ООП применительно к небольшим программам, поэтому его можно рекомендовать при создании больших программ, а лучше даже класса программ (как, например, создание интерактивных программ с использованием Turbo Vision, где основой является ООП). Можно, по-видимому, даже сказать, что ООП скорее не упрощает саму программу, а упрощает технологию ее создания.

Изображение слайда
80

Слайд 80

Гради Буч выделяет две разновидности декомпозиции: алгоритмическую (поддерживаемую структурными методами) и объектно-ориентированную, основанную на разделении по объектам. На практике рекомендуется применять обе разновидности декомпозиции: При создании крупных проектов целесообразно сначала применить объектно-ориентированный подход для создании общей иерархии объектов, отражающей сущность программируемой задачи, а затем использовать алгоритмическую декомпозицию на модули для упрощения разработки и сопровождения разрабатываемого программного комплекса 78

Изображение слайда
81

Слайд 81

Объектная декомпозиция Объектной декомпозицией называют процесс представления предметной области задачи в виде совокупности функциональных элементов (объектов), обменивающихся в процессе выполнения программы входными воздействиями ( сообщениями). Каждый выделяемый объект предметной области отвечает за выполнение некоторых действий, зависящих от полученных сообщений и параметров самого объекта. Гради Буч дает следующее определение объекта: «Объект - это мыслимая или реальная сущность, обладающая характерным поведением и отличительными характеристиками и являющаяся важной в предметной области. Каждый объект имеет состояние, обладает четко определенным поведением и уникальной идентичностью». Объект – это тип данных, который включает не только поля данных объекта, но и подпрограммы (процедуры и функции) для их обработки, называемые методами. 79

Изображение слайда
82

Слайд 82

Объектная декомпозиция Алан Кей  в свое время вывел пять основных черт языка Smalltalk — первого удачного ОО языка: 1 Все является объектом.  Объект как хранит информацию, так и способен ее преобразовывать. В принципе любой элемент решаемой задачи (дом, собака, услуга, химическая реакция, город, космический корабль и т. д.) может представлять собой объект. Объект можно представить себе как швейцарский нож: он является набором различных ножей и «открывашек» (хранение), но в то же самое время им мы можем резать или открывать что-либо (преобразование). 2 Программа — совокупность объектов, указывающих друг другу что делать.  Для обращения к одному объекту другой объект «посылает ему сообщение». Как вариант возможно и «ответное сообщение». 3 Каждый объект имеет свою собственную «память» состоящую из других объектов.  Таким образом программист может скрыть сложность программы за довольно простыми объектами. К примеру, дом (достаточно сложный объект) состоит из дверей, комнат, окон, проводки и отопления. Дверь, в свою очередь, может состоять из собственно двери, ручки, замка и петель. 4 У каждого объекта есть тип.  Иногда тип называют еще и классом. Класс (тип) определяет какие сообщения объекты могут посылать друг другу. Например, аккумуляторная батарея может передавать электролампе ток, а вот момент или физическое усилие - нет. 5 Все объекты одного типа могут получать одинаковые сообщения.  К примеру у нас есть 2 объекта: синяя и красная кружки. Обе разные по форме и материалу. Но из обеих мы можем пить (или не пить, если они пустые). В данном случае кружка — это тип объекта. Самое лаконичное описание объекта предложил  Буч : «Объект обладает  состоянием,  поведением  и  индивидуальностью ». 80

Изображение слайда
83

Слайд 83

Объект характеризуется как совокупностью всех своих свойств и их текущих значений, так и совокупностью допустимых для данного объекта действий. Указанное объединение в едином объекте как «материальных» составных частей, так и действий, манипулирующих этими частями называется инкапсуляцией. Совокупность значений параметров объекта называют его состоянием, а совокупность реакций на получаемые сообщения - поведением. Состояние (state) - совокупный результат поведения объекта: одно из стабильных условий, в которых объект может существовать, охарактеризованных количественно; в любой момент времени состояние объекта включает в себя перечень (обычно статический) свойств объекта и текущие значения (обычно динамические) этих свойств. 81

Изображение слайда
84

Слайд 84

Поведение Для каждого объекта существует определенный набор действий, которые с ним можно произвести. Например, возможные действия с некоторым файлом операционной системы ПК (объектом): создать; открыть; читать из файла; писать в файл; закрыть; удалить. Результат выполнения действий зависит от состояния объекта на момент совершения действия, т.е. нельзя, например, удалить файл, если он открыт кем-либо (заблокирован). В то же время действия могут менять внутреннее состояние объекта - при открытии или закрытии файла свойство "открыт" принимает значения "да" или "нет", соответственно. 82

Изображение слайда
85

Слайд 85

Поведение (behavior) - действия и реакции объекта, выраженные в терминах передачи сообщений и изменения состояния; видимая извне и воспроизводимая активность объекта. Программа, написанная с использованием ООП, обычно состоит из множества объектов, и все эти объекты взаимодействуют между собой. Обычно говорят, что взаимодействие между объектами в программе происходит посредством передачи сообщений между ними. Параметры состояния и элементы поведения объектов определяются условием задачи. 83

Изображение слайда
86

Слайд 86

Классы и объекты-переменные В программе для представления объектов предметной области используют переменные специальных типов - классы. Класс - это структурный тип данных, который включает описание полей данных, а также процедур и функций, работающих с этими полями данных. Применительно к классам такие процедуры и функции получили название методов. Поля, описанные в классе, используют для хранения составляющих состояния или атрибутов объекта. Например, если объект Функция должен хранить номер функции, то реализующий его класс должен содержать соответствующее поле. Класс изображается в виде прямоугольника, состоящего из трех частей. В верхней части помещается название класса, в средней - свойства объектов класса, в нижней - действия, которые можно выполнять с объектами данного класса (методы). В двух словах,  класс  - это тип данных, а  объект  - экземпляр типа класс. "Кружка" - это класс (тип). А уж которая, - синяя или красная, - это два разных объекта (экземпляра), типа "кружка" Каждый класс также может иметь специальные методы, которые автоматически вызываются при создании и уничтожении объектов этого класса: конструктор (constructor) - выполняется при создании объектов; деструктор (destructor) - выполняется при уничтожении объектов. 84

Изображение слайда
87

Слайд 87

Имя объекта Имя класса Имя объекта Состояние Поля Значения Поведение Методы Методы Объект предметной области Класс Объект- переменная Рис.2 Соответствие объектов предметной области, классам и объектам-переменным

Изображение слайда
88

Слайд 88

Переменные типа класса также обычно называют объектами. На рис. 2 показана связь объектов предметной области, классов и объектов-переменных. Согласно общим правилам языка программирования объект-переменная должен быть: создан - для него должна быть выделена память; инициализирован - полям объекта должны быть присвоены значения; уничтожен - память, выделенная под объект, должна быть освобождена. 86

Изображение слайда
89

Слайд 89

Как нам теперь использовать объекты в языках, использующих различные объектные модели? C++ : если у нас есть класс  MyClass  с методом  MyMethod, мы можем написать: MyClass Obj; Obj.MyMethod(); и получить объект класса  MyClass  с именем  Obj. Память для этого объекта обычно выделяется в стеке, и вы можете сразу начать использовать объект, как это сделано во второй строке. Также возможно выделить память для объекта в куче и оперировать указателем на объект: MyClass *obj = new MyClass(); obj->MyMethod(); delete obj;//освобождаем память Java : подобная инструкция выделяет только место для хэндла объекта, а не для самого объекта: MyClass Obj; Obj = new MyClass(); Obj.MyMethod(); 88

Изображение слайда
90

Слайд 90

Прежде чем использовать объект, вы должны вызвать "new" для выделения под него памяти. Конечно, вы можете объявить и проинициализировать объект в одном предложении, избегая использования неинициализированных объектных хэндлов: MyClass Obj = new MyClass(); Obj.MyMethod(); Object Pascal : использует подобный подход, но требует отдельных предложений для объявления и инициализации: var Obj: MyClass; begin Obj := MyClass.Create; Obj.MyMethod; В  C#  работа с объектами классов и структур внешне выглядит похоже: MyClass obj1 = new MyClass(); obj1.Method1(); MyStruct1 obj2 = new MyStruct("Hello!"); obj2.Method2(); MyStruct2 obj3; obj3.Method3(); 89

Изображение слайда
91

Слайд 91: 8 Принцип наследования. Перекрытие полей и методов. Области видимости. Полиморфизм. Родительский, дочерний классы. Поля, методы объектов. Инкапсуляция. Свойства объектов. Методы доступа к свойствам объектов. Правило инкапсуляции

Наследование ( inheritance ) - это отношение между классами, при котором класс использует структуру или поведение другого класса (одиночное наследование), или других (множественное наследование) классов. Наследование вводит иерархию "общее/частное", в которой подкласс наследует от одного или нескольких более общих суперклассов. Подклассы обычно дополняют или переопределяют унаследованную структуру и поведение. Одним из наиболее значимых достоинств ООП является то, что большинство классов для реализации объектов не приходится разрабатывать «с нуля». Обычно классы строят на базе уже существующих, используя механизмы, реализующие определенное отношение существующего и строящего классов между собой: наследование, композицию, агрегацию и полиморфное наследование. Наследованием или обобщением называют отношение между классами, при котором один класс строится на базе второго посредством добавления полей и определения новых методов. При этом исходный класс, на базе которого выполняется построение, называют родительским, или базовым, или супертипом, а строящийся класс - потомком, или производным классом, или подтипом.

Изображение слайда
92

Слайд 92

8 ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ 91 Класс-родитель Класс-потомок Класс-родитель Класс-потомок 1 Класс-потомок 2 Рис. 6 Примеры иерархий классов Отношение обобщения обозначается сплошной линией с треугольной стрелкой на конце. Стрелка указывает на более общий класс (класс-предок или суперкласс), а ее отсутствие - на более специальный класс (класс-потомок или подкласс). Использование наследования способствует уменьшению количества кода, созданного для описания схожих сущностей, а также способствует написанию более эффективного и гибкого кода.

Изображение слайда
93

Слайд 93: 93

Области видимости (доступности). При описании класса важно соблюсти разумный компромисс. С одной стороны, требуется скрыть ряд внутренних методов и полей, одни из которых бесполезны пользователю класса и только усложняют его интерфейс, а доступ к другим полям нужно организовать через систему проверок или свойств (инкапсуляция). С другой стороны, если слишком ограничивать возможного пользователя класса, то данный класс может стать ему неинтересен. В языке Object Pascal применяют следующие виды доступа к полям, методам и свойствам: Public (общие). Поля, методы и свойства из этой секции не имеют ограничений на видимость. Они доступны из других функций и методов объектов как в данном модуле, так и в других модулях, ссылающихся на него. Protected (защищенные). Поля, методы и свойства этой секции доступны всем функциям и методом данного модуля. В других модулях доступны только в классах, порожденных от данного класса. Private (личные). Наибольшее ограничение доступности. Поля, методы и свойства из этой секции доступны только в данном модуле и недоступны из других модулей.

Изображение слайда
94

Слайд 94: Инкапсуляция (encapsulation) - это сокрытие реализации класса и отделение его внутреннего представления от внешнего (интерфейса). При использовании объектно-ориентированного подхода не принято применять прямой доступ к свойствам какого-либо класса из методов других классов. Для доступа к свойствам класса принято задействовать специальные методы этого класса для получения и изменения его свойств. Несмотря на непривычность слова это просто связывание полей и методов в одну структуру (складывание их в одну "капсулу"). Инкапсуляция позволяет в максимальной степени изолировать объект от внешнего окружения. Она существенно повышает надёжность разрабатываемых программ, т.к. локализованные в объекте алгоритмы обмениваются с программой сравнительно небольшими объёмами данных, причём количество и тип этих данных обычно тщательно контролируется. Полиморфизм Этот принцип неразрывно связан с наследованием и гласит, что каждый класс наследник может обладать не только свойствами, унаследованными от предка, но и своими собственными. В частности, свойства предка могут быть перекрыты наследником - на место свойств предка могут быть подставлены свойства наследника. Существование принципа полиморфизма является естественным следствием существования принципа наследования: наследование без изменения набора свойств не имеет смысла. Кроме того, без полиморфизма невозможно реализовать объединение различных объектов (классов) по некоторому набору свойств (невозможно абстрагироваться от части свойств объектов), а без этого теряется весь смысл подхода

Изображение слайда
95

Слайд 95: 93

Полиморфизм – это свойство родственных объектов (т.е. объектов, имеющих одного общего родителя) решать схожие по смыслу проблемы разными способами. В рамках ООП поведенческие свойства объекта определяются набором входящих в него методов. Изменяя алгоритм того или иного метода в потомках объекта, программист может придавать этим потомкам отсутствующие у родителя специфические свойства. Для изменения метода необходимо перекрыть его в потомке, т.е. объявить в потомке одноимённый метод и реализовать в нём нужные действия. В результате в объекте-родителе и объекте-потомке будут действовать два одноимённых метода, имеющие разную алгоритмическую основу и, следовательно, придающие объектам разные свойства. Это и называется полиморфизмом объектов. Описание объекта должно помещаться в разделе описания типов: type MyObject = object {поля объекта} {методы объекта} end;

Изображение слайда
96

Последний слайд презентации: Информатика и программирование: 94

Если объект порождается от какого-либо родителя, имя родителя указывается в круглых скобках сразу за словом object : type MyDescendantObject = object ( MyObject ) ............................................................ ............................................................ end; Если объектный тип создается "на базе" другого существующего объекта, то имя родительского типа должно быть указано в скобках после слова object при описании потомка: Type <Потомок> = object (<Родитель>) <Добавленные поля> <Добавленные и переопределенные методы> end ; Как уже говорилось выше, такие объекты автоматически наследуют от родителя его поля и методы. Поля могут быть добавлены ( но не переопределены ), а методы переопределены и добавлены.

Изображение слайда