2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Кузбасский государственный технический университет

имени Т.Ф. Горбачева»

Кафедра информационных

и автоматизированных производственных систем

Курс лекций по Дисциплине

Программирование

и основы алгоритмизации

Составил профессор кафедры,

д.т.н. Преслер В.Т.

Кемерово 2012

Оглавление

Введение в программирование и основа алгоритмизации 4

Тема 1. Программное средство. Исторический и социальный контексты программирования 6

1.1. Программа как формализованное описание процесса обработки данных. Программное средство 6

1.2. Понятие "правильной" программы 6

1.3. Надежность программного средства 7

1.4. Технология программирования как разработка надежных ПС 7

1.5. Информатизация общества 7

Тема 2. Источники ошибок в программных средствах 9

2.1. Интеллектуальные возможности человека 9

2.2. Неправильный перевод как причина ошибок в ПС 9

2.3. Модель перевода 10

2.4. Основные пути борьбы с ошибками 10

Тема 3. Общие принципы разработки программных средств 11

3.1. Специфика разработки ПС 11

3.2. Жизненный цикл ПС 11

3.3. Понятие качества ПС 12

3.4. Внешнего описания и его роль в обеспечении качества ПС 12

3.5. Обеспечение надежности – основной мотив разработки ПС 13

3.6. Борьба со сложностью систем и обеспечение точности перевода 14

Тема 4. Разработка структуры программы. Модульное и объектно-ориентированное

программирование 15

4.1. Цель модульного программирования 15

4.2. Основные характеристики программного модуля 15

4.3. Методы разработки структуры программы 16

4.4. Объектно-ориентированное программирование 18

4.5. События и событийная модель 22

Тема 5. Алгоритмизация и разработка программного модуля 24

5.1. Определение алгоритма 24

5.2. Изобразительные средства описания алгоритмов 24

5.3. Блок-схемы алгоритмов. Графические символы 25

5.4. Порядок разработки программного модуля 26

5.5. Структурное программирование 27

5.6. Пошаговая детализация и понятие о псевдокоде 28

Тема 6. Тестирование и отладка программного средства 30

6.1. Основные понятия 30

6.2. Принципы и виды отладки ПС 30

6.3. Заповеди отладки ПС 31

6.4. Автономная отладка ПС 31

Тема 7. Методы разработки алгоритмов 34

7.1. Метод частных целей 34

7.2. Метод подъема 35

7.3. Программирование с отходом назад 35

7.4. Алгоритмы ветвей и границ 38

Тема 8. Алгоритмы сортировки 43

8.1. Сортировка. Основные понятия 43

8.2. Пузырьковая сортировка 43

8.3. Сортировка с помощью дерева 44

8.4. Пирамидальная сортировка 45

8.5. Быстрая сортировка 47

Тема 9. Алгоритмы поиска и перебора 49

9.1. Поиск. Основные понятия 49

9.2. Бинарный поиск 49

9.3. Поиск в сети 50

9.4. Генератор перестановок 51

Тема 10. Событийно-управляемое программирование на языке Visual Basic 54

10.1. Историческая справка 54

10.2. Основы Visual Basic 55

10.3. Формы и элементы управления 57

10.4. Элементы управления пользователя 59

10.5. Фокус. Последовательность переходов. Меню 61

Тема 11. Управление проектами 64

11.1. Работа с проектом и его структура 64

11.2. Работа с несколькими проектами 65

11.3. Создание и запуск выполняемого файла. Компиляция 66

11.4. Установка параметров проекта 66

11.5. Дополнения и мастера 67

Тема 12. Управляющие конструкции 68

12.1. Конструкции принятия решения (ветвление) 68

12.2. Циклы 69

12.3. Работа со структурами управления и досрочный выход из них 70

Тема 13. Структура приложения. Техника написания кода 72

13.1. Структура приложения 72

13.2. Как работает событийное приложение 72

13.3. До начала кодирования 73

13.4. Техника написания кода 74

13.5. Автоматизация написания программы 75

Литература 76

Введение в программирование и основы алгоритмизации

Курс "Программирование и основы алгоритмизации" охватывает современные проблемные вопросы создания программных средств. Следует подчеркнуть – не просто программы, а программного средства определенной предметной области. Здесь выделяются два фундаментальных понятия программное средство и предметная область.

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

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

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

И здесь возникают две взаимосвязанные сложнейшие проблемы, которые в форме понятий предметная область и программное средство были выделены в самом начале.

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

Действительность (мир предметов и вещей)  Модель  Программный продукт (виртуальное воплощение модели)  Реальные результаты  Адекватность модели или программного продукта ожидаемому результату  Корректировка модели или модернизация программного продукта

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

По форме программное средство описывается простой формулой

Программы + Документация

Однако содержание гораздо богаче внешнего проявления (формы) поскольку включает:

• коллективный и индивидуальный опыт разработки проектов, накапливаемый от проекта к проекту и используемый при разработке новых проектов,

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

• базы данных и базы знаний по разработке и управлению проектами, а также разнообразные программные средства по автоматизации процессов проектирования (разработки проектов), создаваемые в ходе работ над проектами.

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

Тема 1

ПРОГРАММНОЕ СРЕДСТВО.

ИСТОРИЧЕСКИЙ И СОЦИАЛЬНЫЙ КОНТЕКСТЫ ПРОГРАММИРОВАНИЯ

1.1. Программа как формализованное описание процесса обработки данных.

Программное средство (ПС)

Целью программирования является описание процессов обработки данных, которые называются процессами. Данные  это представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором процессе. Информация  это количественная и смысловая интерпретация данных при их представлении в процессах обработки. Обработка данных  это выполнение систематической последовательности действий с данными. Данные представляются и хранятся на носителях данных. Совокупность этих носителей, используемая при обработке, называется информационной средой. Набор данных, содержащихся в некоторый момент в информационной среде, называется состоянием информационной среды. Процесс это последовательность сменяющихся состояний информационной среды. Задать процесс  это определить последовательность ее состояний.

Чтобы заданный процесс порождался автоматически на компьютере, необходимо, чтобы его описание было формализовано. Формализация процесса на компьютере называется программированием, а результат формализации - программой. Для составления программ используются формализованные или формальные языки программирования (ФЯП). В отличие от исполняемого машинного кода компьютера формальные языки программирования существенно упрощают и ускоряют процесс разработки программ, делают программы читабельными и понятными не только разработчикам, но и квалифицированным пользователям. Программа, составленная на формальном языке программирования, переводится на машинный язык компьютера с помощью другой программы  транслятора.

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

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