Ответы на билеты по предмету: Программирование (Пример)
Содержание
1. Модели решения функциональных и вычислительных задач.
Модель
Способы моделирования
Классификация видов моделирования.
Математические модели.
Этапы компьютерного математического моделирования
Классификация математических моделей
Информационные модели.
Основные этапы решения задачи с использованием комьтерного моделирования.
2. Алгоритмизация и программирование.
Алгоpитм
Свойства алгоритмов
Формы представления алгоритмов
Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Графический способ представления алгоритмов
Псевдокод
Программная форма
3. Языки программирования высокого уровня.
4. Основы и методы защиты информации.
Защита информации
Система защиты информации
Основные средства
Управление доступом
Маскировка
5. Структура программного обеспечения с точки зрения пользователя, средства и алгоритмы представления, хранения и обработки текстовой и числовой информации.
6. Программные среды; организация и средства человеко-машинного интерфейса, мультисреды и гиперсреды.
Понятие аппаратно-операционной и программной сред
Основные принципы человеко-машинного интерфейса
Мультисреда
Гиперсреда
7. Назначение и основы использования систем искусственного интеллекта.
8. Понятие об информационных технологиях на сетях.
Сеть
Клиент
Сервер
Host-ЭВМ
Коммутационная сеть
Сетевая операционная система и архитектура сетей
Уровни сетей ISO
9. Основные этапы компьютерного решения задач.
Постановка задачи.
Моделирование.
Построение алгоритма.
Программирование.
Отладка и тестирование программы.
Анализ результатов. Уточнение модели.
10. Модульные программы. Объектно-ориентированное программирование.
11. Критерии качества программы.
12. Программирование в телекоммуникациях и распределенной обработки информации.
13. Постановка задачи и спецификация программы, стандартные типы данных.
14. Представление основных структур: итерации, ветвления.
15. Процедуры: построение и использование; типы данных, определяемые пользователем; записи; файлы.
16. Динамические структуры данных; списки: основные виды и способы реализации.
17. Программирование рекурсивных алгоритмов.
Выдержка из текста
1. Модели решения функциональных и вычислительных задач.
Модель — это искусственно созданный объект, дающий упрощенное представление о реальном объекте, процессе или явлении, отражающий существенные стороны изучаемого объекта с точки зрения цели моделирования. Модель играет системообразующую и смыслообразующую роль в научном познании, позволяет понять явление, структуру изучаемого объекта. Не построив модель, вряд ли удастся понять логику действия системы. Это означает, что модель позволяет разложить систему на элементы, связи, механизмы, требует объяснить действие системы, определить причины явлений, характер взаимодействия составляющих.
Задачи, которые мы решаем, по своему назначению можно разделить на две категории:
• вычислительные задачи, целью которых является определение некоторой величины;
• функциональные задачи, предназначенные для создания некоего аппарата, выполняющего некоторые действия, функции.
Этапы решения задачи:
Реальный объект — модель — алгоритм — программа — результат.
Способы моделирования:
• Аналитическое моделирование заключается в построении модели, основанной на описании или поведения объекта или системы объектов в виде аналитических выражений – формул. Объект описывается системой линейных или нелинейных алгебраических или дифференциальных уравнений, решение которых может дать представление о свойствах объекта.
• Имитационное моделирование предполагает построение модели с характеристиками, адекватными оригиналу, на основе какого-либо его физического или информационного принципа. При таком моделировании отсутствует общая аналитическая модель большой размерности, а объект представлен системой , состоящей из элементов, взаимодействующих между собой и внешним миром. Задавая внешние воздействия, можно получить характеристики системы и провести их анализ.
Классификация видов моделирования.
По цели использования: научный эксперимент, комплексные испытания и производственный эксперимент, оптимизационные модели.
По наличию воздействий на систему: детерминированные, стохастические.
По отношению ко времени: статистические, динамические (дискретные и непрерывные).
По возможности реализации: мысленные, реальные.
По области применения: универсальные, специализированные.
Математические модели.
Математическая модель — приближенное описание объекта моделирования, выраженное с помощью математической символики. Математическая модель — это уравнения, системы уравнений, системы неравенств, дифференциальные уравнения или системы таких уравнений и пр. Математические модели появились вместе с математикой много веков назад. Огромный толчок развитию математического моделирования придало появление ЭВМ. Применение вычислительных машин позволило проанализировать и применить на практике многие математические модели, которые раньше не поддавались аналитическому исследованию. Реализованная на компьютере математическая модель называется компьютерной математической моделью, а проведение целенаправленных расчетов с помощью компьютерной модели называется вычислительным экспериментом.
Этапы компьютерного математического моделирования:
Первый этап: определение целей моделирования. Эти цели могут быть различными:
• Понимание – модель нужна для того, чтобы понять, как устроен конкретный объект, какова его структура, основные свойства, законы развития и взаимодействия с окружающим миром;
• Управление – модель нужна для того, чтобы научиться управлять объектом или процессом и определить наилучшие способы управления при заданных целях и критериях;
• Прогнозирование – модель нужна для того, чтобы прогнозировать прямые и косвенные последствия реализации заданных способов и форм воздействия на объект.
Второй этап: определение входных и выходных параметров модели; разделение входных параметров по степени важности влияния их изменений на выходные. Такой процесс называется ранжированием, или разделением по рангам.
Третий этап: построение математической модели. На этом этапе происходит переход от абстрактной формулировки модели к формулировке, имеющей конкретное математическое представление.
Четвертый этап: выбор метода исследования математической модели. Чаще всего здесь используются численные методы, которые хорошо поддаются программированию. Как правило, для решения одной и той же задачи подходит несколько методов, различающихся точностью, устойчивостью и т.д. От верного выбора метода часто зависит успех всего процесса моделирования.
Пятый этап: разработка алгоритма, составление и отладка программы для ЭВМ — трудно формализуемый процесс.
Шестой этап: тестирование программы. Работа программы проверяется на тестовой задаче с заранее известным ответом. Обычно тестирование заканчивается тогда, когда пользователь по своим профессиональным признакам сочтет программу верной.
Седьмой этап: вычислительный эксперимент, в процессе которого выясняется, соответствует ли модель реальному объекту или процессу. Модель достаточно адекватна реальному процессу, если некоторые характеристики процесса, полученные на ЭВМ, совпадают с экспериментально полученными характеристиками с заданной степенью точности. В случае несоответствия модели реальному процессу возвращаемся к одному из предыдущих этапов.
Классификация математических моделей
В основу классификации математических моделей можно положить различные принципы. Можно классифицировать модели по отраслям наук (математические модели в физике, биологии, социологии и т.д.).
Можно классифицировать по применяемому математическому аппарату (модели, основанные на применении обыкновенных дифференциальных уравнений, дифференциальных уравнений в частных производных, стохастических методов, дискретных алгебраических преобразований и т.д.).
Если исходить из общих задач моделирования в разных науках, наиболее естественна такая классификация:
• дескриптивные (описательные) модели;
• оптимизационные модели;
• многокритериальные модели;
• игровые модели.
Информационные модели.
Информационная модель- это совокупность информации об объекте, описывающая свойства и состояние объекта, процесса или явления, а также связи и отношения с окружающим миром. Информационные модели представляют объекты в виде словесных описаний, текстов, рисунков, таблиц, схем, чертежей, формул и т.д. Информационную модель нельзя потрогать, у нее нет материального воплощения, она строится только на информации. Ее можно выразить на языке описания (знаковая модель) или языке представления (наглядная модель).
Информационные модели во многих случаях опираются на математические модели, так как при решении задач математическая модель исследуемого объекта, процесса или явления неизбежно преобразуется в информационную для её реализации на компьютере. Информационным объектом называется описание реального объекта, процесса или явления в виде совокупности его характеристик (информационных элементов), называемых реквизитами. Информационный объект определённой структуры (реквизитного состава) образует тип (класс), которому присваивают уникальное имя.
Информационный объект с конкретными характеристиками называют экземпляром. Каждый экземпляр идентифицируется заданием ключевого реквизита (ключа).
Одни и те же реквизиты в различных информационных объектах могут быть как ключевыми, так и описательными. Информационный объект может иметь несколько ключей.
Технология решения задач (анализа, прогнозирования, управления) с использованием компьютерного моделирования включает основные этапы:
1)Постановка задачи – описание исходной задачи и исходных данных («что дано») и определение целей моделирования, требований к результатам («что нужно найти»).
2)Разработка концептуальной модели («расчетной схемы», упрощенного представления) или структуризация или качественный анализ – формулировка предположений и упрощений, выделение существенных элементов и взаимосвязей (результаты этапа желательно представить максимально наглядно – в виде схем, диаграмм или, по крайней мере, сжатого лаконичного описания).
3)Разработка математической модели, формализация задачи – описание объекта (точнее, разработанной ранее его упрощенной концептуальной модели) на искусственном математическом («формальном») языке с использованием наиболее адекватного математического аппарата.
4)Алгоритмизация задачи – разработка алгоритма расчета, представляющего математическую модель в виде четкой и однозначной последовательности операций, которые могут быть выполнены на компьютере.
5)Кодирование алгоритма с помощью выбранных средств программирования (языка и системы программирования, электронных таблиц, набора запросов, форм и отчетов базы данных и т.п.).
6)Тестирование (отладка) компьютерной системы (программы, расчетной таблицы, базы данных) для выявления и устранения ошибок. Этот этап является обязательным и, зачастую, наиболее длительным, потому что, в силу причин, объясняемых в соответствующем разделе курса, создать сразу программу без ошибок невозможно.
7)Использование компьютерной системы для решения поставленных задач объяснения функционирования моделируемой системы, прогнозирования ее поведения, принятия управленческих решений и т.п.
8)Интерпретация результатов компьютерного моделирования – формулировка выводов из анализа явления и следствий полученных прогнозов, выработка мер по реализации выбранного решения.
Процесс решения задачи с использованием компьютерного моделирования является итеративным (циклическим): на любом из этапов может потребоваться возврат на любой из предыдущих и внесение изменений. Так, даже на этапе интерпретации результатов может оказаться, что полученные выводы неприменимы практически и нужно вернуться к постановке задачи, пересмотрев состав исходных данных и цели моделирования (требования к результатам).
Список использованной литературы
Программирование рекурсивных алгоритмов.
Чтобы рекурсия не зациклилась, внутри рекурсивной процедуры/функции ОБЯЗАТЕЛЬНО должен присутствовать оператор IF. Общая схема построения рекурсивных программ такова:
P = IF B THEN P[S,P]
END;
или
P = P[S, IF B THEN P END]
Пусть n – параметр рекурсии. Тогда:
P(n) = IF n>0 THEN P[S,P(n-1)]
END
или
P(n) = P[S, IF n>0 THEN P(n-1) END]
Если есть возможность заменить рекурсию циклом – заменяйте! Например, факториал можно спокойно вычислить в обычном цикле без рекурсии:
FUNCTION fact(n:WORD):LONGINT;
VAR I:WORD;
BEGIN
fact := 1;
FOR I := 1 TO n DO
fact := fact * n
END;
Такой алгоритм снимает ограничения по памяти (экспериментальная проверка показала, что при рекурсии n£ 608, затем возникает ошибка переполнения памяти).
В то же время в ряде случаев очень легко написать рекурсивную программу, а превратить ее в обычную не так-то просто. Яркий пример рекурсивного "по своей природе" алгоритма – вычисление чисел Фибоначчи. Числа Фибоначчи определяются как:
fn+1= fn + fn-1 при n>0; f 1=1; f 0=0
Проще говоря, каждое число Фибоначчи является суммой двух предыдущих. Последовательность имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… Числа Фибоначчи играют важную роль в технике и даже в биологии (в соответствии с законом Фибоначчи растет численность живых организмов).
Рекурсивно вычислять числа Фибоначчи очень просто:
FUNCTION Fib(n:WORD):WORD;
BEGIN
IF n=0 THEN Fib := 0 ELSE
IF n=1 THEN Fib := 1 ELSE
Fib := Fib(n-1) + Fib(n-2)
END;
Алгоритм получается простым и очевидным.
Рекурсия широко используется в алгоритмах сортировки. Самый лучший на сегодняшний день алгоритм, который так и называется QuickSort(быстрая сортировка), является рекурсивным и был предложен С. Хоаром (C. Hoare) в 1970. Лежащая в основе QuickSort идея проста: для большей скорости работы лучше сначала производить перестановки элементов на большие расстояния. Алгоритм можно описать следующим образом:
1. Берем любой элемент массива х
2. Ищем в массиве слева элемент ai>x
3. Ищем в массиве справа элемент a
