Определение алгоритма. Пример алгоритма. Пять основных свойств алгоритма. Сущность алгоритмизации

СОДЕРЖАНИЕ (Технология программирования)

1..... Эволюция средств программирования: программирование в машинных кодах, программирование в мнемонике ассемблера, языки высокого уровня. 3

2. Определение алгоритма. Пример алгоритма. Пять основных свойств алгоритма. Сущность алгоритмизации. 4

3. Понятие алгоритмического языка. Основные достоинства и недостатки программирования на алгоритмическом языке. 6

4. Языки программирования высокого уровня. Поколения и топология языков программирования высокого уровня с примерами (по Г. Бучу). 8

5. Интерпретаторы и компиляторы. «За» и «против». Структура. Понятие Байт-кода (P-Code) в языке Java. Языки 4GL. 10

6. Транслятор. Редактор связей. Загрузчик. Назначение и принципы функционирования. 12

7. Понятие исходного, объектного, загрузочного модулей. Назначение. 13

8. Понятие программы, подпрограммы, функции. Способы передачи и возврата параметров в подпрограммы и функции. 14

9. Основные принципы структурного программирования. 16

10. Модели управления в программных системах: централизованное управление, управление, основанное на событиях. 17

11. Структура событийно-управляемой программы для платформы Win32. 18

12. Основные элементы объектно-ориентированных методов создания программных систем: абстрагирование, инкапсуляция, модульность, иерархия, типизация, параллелизм, устойчивость, полиморфизм. Понятие объектно-ориентированного программирования. 19

13. Понятие объекта и класса. Свойства объекта: состояние, поведение, идентичность. Свойства класса: структура и поведение. Описание классов в языке C++. Объект, класс и инкапсуляция как связанные понятия. 21

14. Создание объектов в языке C++. Распределение объектов в динамической памяти (куче) и автоматическое распределение памяти под объекты (на стеке). Сильные и слабые стороны. 23

15. Методы (члены-функции) в классах языка C++. Специальные методы: статические (static) методы, виртуальные методы и неизменные (immutable) методы в C++. 25

16. Конструкторы и деструкторы в языке C++. Соглашения относительно специальных функций-членов класса. Порядок вызова при наследовании. Виртуальные деструкторы. 26

17. Понятие модуля. Модуль как средство борьбы со сложностью программной системы. Принципы проектирования модулей. Модули в языке C++. Модульность и инкапсуляция как связанные понятия. 28

18. Типизация (декларация) данных в языках программирования. Задачи типизации. Слабая и сильная типизация. Достоинства и недостатки каждой. Типизация в языке C++. Встроенные типы данных. Определение new типов данных. 30

19. Соглашения по преобразованию (приведению) типов данных в языке C++. Операторы const_cast, reinterpret_cast, static_cast, dynamic_cast. 31

20. Специальный полиморфизм в языке C++. Перегрузка функций и операторов. 33

21. Параметрический полиморфизм. Параметризованные классы (template) и функции в языке C++ как средство статического полиморфизма. 34

22. Полная и частичная специализация шаблонов в языке C++. 36

23. Простое и множественное наследование в языке C++. Полиморфное поведение объектов при наследовании. Проблема «среза» в полиморфизме наследования и способы решения. 37

24. Абстрактные классы и интерфейсы. Описание на языке C++. Реализация интерфейсов. 39

25. Понятие интерфейса. Язык описания интерфейсов IDL (MIDL). 40

26. Стандартная библиотека шаблонов STL. Основные концепции: контейнер, алгоритм, итератор, поток. 41

27. Представление в машине символьной информации. Кодировки ASCII, MBCS, ANSI, Unicode. Строки ASCII-Z, Pascal, BSTR. 42

28. Признаки сложных систем согласно общей теории систем. Примеры систем (выделить в них признаки). 44

29. Сложность, присущая программному обеспечению. Составляющие сложности программного обеспечения по Ф. Бруксу. 46

30. Эволюция системного программного продукта. Понятие и составляющие программы, программного комплекса, программного продукта, системного программного продукта (по Ф. Бруксу) 47

31. Борьба со сложностью в программном обеспечении. Эволюция методов анализа и разработки (SA/SD, OOA/OOD). 48

32. Жизненный цикл программного обеспечения. Фазы ЖЦ, их характеристики артефакты. 49

33. Модели жизненного цикла разработки программного обеспечения. Сравнение моделей. 50

35. Производительность труда программиста. Различия в прогах опытного программиста и новичка по Ф. Бруксу. 52

36. Распределение стоимости разработки программного обеспечения по технологическим стадиям создания. 53

37. Язык UML. История создания. Область применения. Виды диаграмм UML для описания системы. 54

38. Программирование на основе шаблонов (паттернов). Роль шаблонов проектирования в борьбе со сложностью программного обеспечения. Будущее шаблонов. 55

39. Понятия связанности (Coupling) и зацепления (Cohesion) в сложных программных системах. Связанность и зацепление классов, модулей, компонентов. 57

40. Ошибки программирования: переполнение буфера. Понятие безопасного программного кода. 59

41. Оптимизация программного кода. Основные возможности оптимизации кода программистом и компилятором. 60

42. Оформление программ: основные пункты. 61

43. Процесс отладки программного обеспечения. Сложность отладки ПО. Методы поиска и устранения ошибок. Связь отладки с тестированием. 62

44. Понятие качества программного обеспечения. Составляющие и критерии качества. Обеспечение качества как процесс, а не этап. Международный стандарт ISO 9000/9001. 63

45. Задачи тестирования программного обеспечения. Тестирование как процесс, а не этап. Тестирование модулей, интерфейсов, сборки. Нисходящее и восходящее тестирование. Метрики тестирования и окончание тестирования. 64

46. Основы тестирования программного обеспечения методом «чёрный ящик» (функциональное тестирование). Роль прецедентов в функциональном тестировании. 66

47. Основы тестирования программного обеспечения методом «белый ящик» (структурное тестирование). 67

48. Понятие надежного ПО. Различие между надежностью аппаратуры и ПО. 68

49. Модели надёжности ПО. Сравнение моделей оценки надежности ПО. Перспективы построения «хороших» моделей оценки надежности ПО. 69

50. Динамические модели надежности программного обеспечения (Шумана). 70

51. Статические модели надежности программного обеспечения (Миллса). 71

52. CASE - технологии (инструменты, системы, средства). Эволюция CASE - средств, их классификация, характеристики современных CASE - инструментов. Перспективы развития. (По Вендрову, Калянову). 72

53. Классификация средств разработки (CASE - инструментов). 74

54. Технологический скачок (ТС) в программировании. Признаки технологического скачка. Исторические факты технологических скачков. 76

55-56. Основные нормы и принципы этики программирования. Хакерство как феномен. 77

1. Эволюция средств программирования: программирование в машинных кодах, программирование в мнемонике ассемблера, языки высокого уровня.

Существуют сотни языков программирования. Их можно разделить на три основных типа: машинные языки; языкиассемблера; языки высокого уровня

Любой компьютер может непосредственно понимать лишь свой собственный машинный язык. Машинный язык — это «язык» определенного компьютера. Он определяется при проектировании аппаратных средств этого компьютера. Машинные языки в общем случае содержат строки чисел, которые являются командами компьютеру на выполнении большинства элементарных операций в тот или иной момент времени. Машинные языки машинно-зависимы, т.е. каждый машинный язык может быть использован только на компьютере одного определенного типа. Они тяжелы для человеческого восприятия.

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

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

Очевидно, что языки высокого уровня гораздо удобнее с точки зрения программистов по сравнению с языками ассемблера. С и C++ относятся к числу наиболее мощных и наиболее распространенных языков высокого уровня.

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

Определение алгоритма. Пример алгоритма. Пять основных свойств алгоритма. Сущность алгоритмизации.

Слово «Алгоритм» происходит от лат. Algorithmi. Алгоритм есть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Для алгоритмов, встречающихся в математике, средой того или иного исполнителя могут быть числа разной природы - натуральные, действительные и т.п., буквенные выражения, уравнения, тождества и т.п.

Рассмотрим следующую задачу. Длина офисного помещения 8 метров, ширина – 10 метров, высота – 3 метра. В офисе 40 рабочих. Сколько кв. м площади и сколько куб. м воздуха приходится на одного рабочего?

Решение задачи:

1.Вычислить площадь помещения: 8х10 = 80

2. Вычислить объем помещения: 80х3 = 240

3. Вычислить, сколько кв. метров площади приходится на одного рабочего: 80/40 = 2

4. Вычислить, сколько куб. метров воздуха приходится на одного рабочего: 240/40 = 6

Ответ: на одного рабочего приходится 2 кв. метров площади и 6 куб. метров воздуха.

Если теперь убрать вычисления и оставить только “действия”, то получим алгоритм – перечень операций, которые необходимо выполнить, чтобы решить данную задачу. Такой алгоритм будет представлять собой набор указаний (команд) компьютеру.

Когда мы вычисляем какую-либо величину, мы записываем результат на бумаге. Компьютер записывает результат своей работы в память в виде переменной. Поэтому каждая команда алгоритма должна включать указание, в какую переменную записывается результат. Алгоритм решения задачи будет выглядеть так:

1. Вычислить площадь помещения и записать в переменную S. 2. Вычислить объем помещения и записать в переменную V. 3. Вычислить, сколько кв. метров площади приходится на одного рабочего, и записать в переменную S1. 4. Вычислить, сколько куб. метров воздуха приходится на одного рабочего, и записать в переменную V1. 5. Вывести на экран значения переменных S1 и V1.Теперь остается только запрограммировать данный алгоритм.

Программирование – это есть перевод алгоритма с «человеческого» языка на «компьютерный» язык.

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

5 общих свойств алгоритмов, позволяющих их отличать от других инструкций:

1. Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

2. Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

3. Результативность (конечность) –алгоритм должен приводить к решению задачи за конечное число шагов или информировать об отсутствии результата.

4. Понятность – алгоритм должен быть понятен не только автору, но и исполнителю. Если предложить исполнителю, например утюгу постирать одежду, то он никогда этого не сделает, потому, что не поймет, т.к. такой программы в нём не заложено. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя.

5. Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

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