IV. Модели решения функциональных и вычислительных задач.

Моделирование – замена изучения реальной системы или процесса ("оригинала") на изучение упрощенного аналога ("модели").

Виды моделей:

а) натурные, или предметные (макеты из дерева, металла и т.п.)

б) информационные (словесные, или вербальные; графические; математические).

Абсолютно установившейся классификации тут нет. Выделяют среди математических моделей:

а) расчетные – когда система описывается набором уравнений, которые как-то решаются.

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

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

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

V. Алгоритмизация и программирование.

При разработке алгоритмов применяют приемы логики. Среди них:

А) индукция и дедукция:

Название	Логический синоним	Ход мысли	Вид программирования
Дедукция	Анализ	От общего к частному	Нисходящее
Индукция	Синтез	От частного к общему	Восходящее

(Шерлок Холмс декларирует, что применяет дедуктивный метод, хотя в основном использует индукцию!)

Б) Рекурсия – определение чего-либо через предыдущее значение (или несколько предыдущих значений). Первое из значений задается явным образом.

В логике рекурсии соответствует принцип математической индукции.

Некоторые сложные типы организации структур данных в компьютере:

А. Последовательные структуры.

1. Стек. Линейная структура, организованная по типу автоматного или пистолетного магазина:

Т.е., значение, помещенное в стек последним, извлекается из него первым.

2. Очередь. Тоже линейная структура, но организована по-другому:

З начение, помещенное в очередь первым, первым и извлекается. Такой тип организации данных подходит, в частности, для рекурсивных алгоритмов.

Б. Непоследовательная структура – дерево (иерархическая; как дерево каталогов, например, или иерархическая структура в БД)

Элементарная часть программы К – машинная команда. Она содержит (в двоичной кодировке):

а) код операции

б) адреса ячеек-операндов

в) адрес ячейки для помещения результата

Парадигмы (системы основных принципов) программирования:

а) интуитивное, или эвристическое программирование – программа пишется без особых правил и систематических приемов, ее структура просматривается от начала до конца. Программа – последовательность операторов. Применимо для небольших программ.

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

Структурное программирование предусматривает категорический отказ от применения оператора перехода GOTO, появившегося в языках на этапе использования интуитивного программирования. Вообще доказано, что любой алгоритм можно реализовать с помощью всего трех операторов: присваивания (вычисления), разветвления (условного оператора) и цикла (теорема Бёма-Якопини, иногда ошибочно именуемая теоремой Дейкстры).

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

Множество объектов одинаковой структуры образуют класс. Объект – отдельный экземпляр своего класса.

Три ключевых принципа ООП:

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

• наследование – возможность создания дочерних объектов с новыми свойствами на основе имеющихся;

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

Языки программирования:

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

2. Языки высокого уровня:

а) Императивные основаны на операторах. Каждый оператор эквивалентен целой группе команд, поэтому требуется трансляция – перевод программы на машинный язык

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

У обоих методов есть свои плюсы и минусы.

Языки называются императивными (командующими), т.к. состоят из прямых указаний компьютеру – что надо делать (отсюда "второй закон Грира": "Компьютерная программа делает не то, что Вам надо, а то, что Вы приказали"). Достоинство – машинная независимость (машинно-зависимы только трансляторы), относительная легкость написания программ, универсальность (не привязаны к конкретному типу задач). Недостаток – меньшая эффективность работы компьютера по сравнению с языками низкого уровня. Примеры: Паскаль/Delphi, С/С++, Фортран, Бейсик и др.

б) Декларативные – состоят из описания данных и действий, которые с ними надо проделать. Достоинство: легче писать и тестировать программу, часто ее можно хорошо описать формальными математическими методами, а значит, и проверить. Недостатки – проблемная ориентированность (привязка к конкретному типу задач), сложность трансляции (отдельная команда языка может на самом деле реализоваться через выполнение целого сложного алгоритма…). Отдельные группы декларативных языков:

• языки запросов в базах данных (пример: SQL);

• языки логического программирования (пример: Prolog).

в) Функциональные – состоят из набора формальных функций, которые последовательно применяются к данным и результатам вычисления предшествующих функций по типу f₁ (f₂ (f₃ (…(f_N (x)…). Таким языком является, например, язык обработки списков LISP.

г) Языки разметки для создания документов сложной структуры. В текст документа вставляются указания на размещение строк и вставленных объектов (рисунков, таблиц и др.), наличие других эффектов оформления. Такие языки могут иметь в названии сокращение ML ("Markup Language"). Примеры: XML, HTML. Последний – язык разметки гипертекстовых документов для Интернета, позволяет вставлять также гиперссылки. Также языком разметки является LaTEX – язык для создания сложных текстов, насыщенных математическими формулами и символами.

Этапы решения задачи программирования:

1. Формулировка задачи

2. Постановка задачи, которая разбивается на две части:

а) Формализация задачи (математическое описание) и выбор метода решения;

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

3. Алгоритмизация – составление алгоритма решения.

4. Выбор системы программирования и составление программы.

5. Проверка алгоритма и программы. Проверка бывает:

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

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

Сложные коммерческие программные продукты тестируются в 2 основных этапа:

1. "Альфа-тестирование". Производится программистами фирмы до начала распространения программного продукта.

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

3. Если в дальнейшем программа модифицируется, проводится регрессионное тестирование для проверки, что внесенные изменения не повлияли нежелательным образом на какие-то особенности работы программы

По принципу проведения различают:

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

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