Теоретические основы информатики. Имитационное Имитационное моделирование. моделирование. Юрий Романович Кофтан koftan@obninsk.org icq: 380720879 т. 910-912-1220. - презентация

1 Теоретические основы информатики. Имитационное Имитационное моделирование. моделирование. Юрий Романович Кофтан icq: т Кафедра ИКД (Информационно компьютерных дисциплин) ИАТЭ НИЯУ "МИФИ"

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

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

4 Теоретические основы информатики - Имитационное моделирование ТОИ-ИМ 4 Задачи Теоретической Информатики? - Построение фундамента Информатики как науки. - Обеспечение развития Прикладной Информатики, Практической Информатики и Технической Информатики. Предмет Теоретической Информатики? -Математические методы изучения процессов хранения, передачи и преобразования информации. Для освоения Теоретических основ информатики предварительно необходимо изучить, как минимум, математические дисциплины, краткий перечень которых приведен на предыдущем слайде. Для освоения методов Имитационного моделирования надо, кроме вышеперечисленных учебных дисциплин, ещё изучить Теорию систем и системный анализ, Моделирование систем, Исследование операций и ряд других дисциплин. ПОЭТОМУ При изучении дисциплины "Теоретические ОСНОВЫ информатики. Имитационное моделирование" будет сделан упор на именно на ОСНОВЫ, а также Практическую информатику и отдельные разделы Теоретической, Прикладной и Технической информатики, необходимые для формирования умений (и компетенций) бакалавров в направлении Бизнес-информатика.

5 Информатика Смысловая ориентировка (зачем делать) – 1. Владеть основами алгоритмизации и методами решения типовых задач 2. Понимать особенности выполнения программ на ЭВМ Функционально-целевая ориентировка (что делать) – 1. Изучить способы составления алгоритмов и их применения для решения типовых задач 2. Изучить машинное представление данных и распределение памяти выполняемых программ Исполнительская ориентировка (как делать) – 1. Освоить составление графических схем алгоритмов с описанием действий/операций в псевдокоде 2. Изучение системы счисления, размещение данных в ПЭВМ с Intel-совместимыми процессорами и распределение памяти выполняемых программ на Pascal в среде MS DOS ТОИ-ИМ 5

6 Языки программирования высокого уровня (ЯП) Pascal и С Смысловая ориентировка (зачем делать) – овладеть инструментом, позволяющим решать задачи с использованием ЭВМ Функционально-целевая ориентировка (что делать) – 1. Программированию невозможно научить, ему можно только научиться ! 2. Необходимо изучить синтаксис и семантику изучаемых языков программирования и правила использования их для реализации алгоритмов Исполнительская ориентировка (как делать) – 1. Будем изучать ЯП Pascal и С в оболочках Borland Pascal v.7.0 и Borland С v Изучение ЯП осуществляется на примере реализации алгоритмов, решающих наиболее типовые задачи программирования ИП 6

7 Язык программирования PASCAL C / С++ Borland C++ v.3.1Borland Pascal v.7.0 Создание индивидуальных настроек на компьютерах студентов На Вашем индивидуальном рабочем диске Z: создать папки (диск размещён на сервере ) : BP – настройки и исходные тексты Pascal, BC – настройки и исходные тексты С / С++, – задания для проверки преподавателем, Koftan – проверенные преподавателем задания. В папку BP поместить файлы: BP.TP BP.DSK BP.PIF не обязательно BP.BAT, - часть файлов создать автоматически в оболочке BP -> Option -> Save as, а часть переместить вручную из папки BP\BIN с диска Y: (с сервера - Y:\Temp\!Koftan\Compiler). Файл BP.BAT скачать с диска Y: В папку BC поместить файлы: TCCONFIG.TC TCDEF.DSK TCDEF.DPR BС.PIF не обязательно BС.BAT, - файлы надо переместить вручную из папки BC\BIN с диска С: или с диска Y: (с сервера - Y: (с сервера - Y:\Temp\!Koftan\Compiler). Файл BP.BAT скачать с диска Y: В файлах BP.BAT (BС.BAT) надо вызвать программу русификации оболочки языка программирования, а затем исполняемый файл компилятора (bp.exe или bc.exe): z:\RUSFNT.com, а затем c:\bp\bin\bp.exe или c:\bc\bin\bc.exe. Для файлов BP.PIF (BС. PIF ) надо отредактировать Свойства: в закладке Программа указать в Команде путь к файлам.BAT (z:\BP\BP.bat, z:\BC\BC.BAT), а в закладке Экран – вид Режима: Полноэкранный или Оконный. И 7

8 Язык программирования PASCAL C / С++ Borland C++ v.3.1Borland Pascal v.7.0 Создание индивидуальных настроек на компьютерах студентов (продолжение) ТОИ-ИМ 8 Для входа в среду программирования (оболочку) надо запустить (двойным щелчком левой клавиши мыши) выполняемые файлы bp.bat и bc.bat, соответственно для входа в оболочку Borland Pascal v.7.0 и Borland C++ v.3.1. Теперь надо осуществить настройку оболочек и сохранит эти настройки на диске Z: в своих папках BP и BC. Требуется настроить: 1. Папку (Directory) по умолчанию: File -> Change dir…; 2. Создать окно исходного кода программ: File -> New; 3. Создать окно для ввода входных значений в программу и просмотра выходных сообщений Вашей программы (Output) - в Pascal: Debug->Output, а в С/C++: Windows-> Output; 4. Для оболочки Pascal установить размер основного окна 43/50 строк ( в С/C++ этот размер установлен по умолчанию сразу ): Options-> Environment->Preferences…->Screen sizes; 5. Прописать в оболочках пути к библиотечным модулям Pascal и С, которые установлены на Вашем компьютере ( в ауд и они лежат в папках BP и BC на диске С:\ ):в Pascal: Options->Directories… (настроить путь к папке BP\UNITS в строках Unit directories и Resource directories; Directories… (настроить путь к папке BС\INCLUDE в строке Include directories и к папке BC\LIB в строке Library directories; 6. Сохранить настройки оболочек: в Pascal: Options->Save as… выбрать путь к папке Z:\BP и файлу BP.TP, в С/C++: Options->Save… выбрать путь к папке Z:\BC и все пункты из списка.

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

10 Простыепрограммы Простые программы Язык программирования PASCAL C Program Simple; const Text = 'Простая программа' ; begin WriteLn(Text ) ; end. #include main( ) { printf(" Простая программа \ n"); } Строки размещаются произвольно Пробел – разделитель конструкций языка Заглавные / строчные буквы игнорируются (кроме текстовых констант) Строки размещаются произвольно Пробелы игнорируются, если они не разделители лексем Заглавные и строчные буквы различаются ТОИ-ИМ 10

11 Простыепрограммы Простые программы stdio.h - standard input/output header - заголовок библиотеки стандартного ввода-вывода С, содержащей функцию printf Program Simple; - объявление имени программы const - блок описания констант Text = 'Простая программа' ; - имя и значение константы begin - начало раздела операторов WriteLn(Text ) ; - оператор вывода на экран end. - завершение программы #include - включение другого файла main( ) - имя функции (главной) { - начало тела функции printf(" Простая программа \ n"); - оператор вывода на печать } - конец программы ТОИ-ИМ 11

12 Структура простой программы Структура простой программы [ Заголовок программы: Program ХХХ; ] [ Декларация - раздел описаний ] [ Тело - раздел операторов: begin Оператор 1; Оператор 2; … end. ] Функция n [ Заголовок функции: Директивы - инструкции для предпроцессора С - #include Имя функции - ( ) ] [ Тело функции - { оператор 1; оператор 2; ……. } ] Функция n+1 В разделе описаний обязательно описываются все нестандартные идентификаторы меток ( label ), констант (const), типов (type), переменных (var), процедур (procedure), функций (function). Программа на С – это одна или более функций, причем главная называется main ( ). Описание функции состоит из заголовка и тела. Тело функции заключено в фигурные скобки и представляет собой набор операторов, каждый из которых оканчивается символом "точка с запятой". PascalC ТОИ- ИМ 12

13 Ссылки на некоторые ресурсы по ЯП в Интернет Общие ссылки Pascal – Начала C – Начала Литература Е.В. Крылов, В.А. Острейковский, Н.Г. Типикин. Техника разработки программ. В 2 кн. Учебник. – М. Высш. Шк., (библиотека). Т. А. Павловская. С/С++. Программирование на языке высокого уровня. – СПб.: Питер, – 461 с.: ил (библиотека, файл). Н. Вирт. Алгоритмы и структуры данных. Пер. с англ. – СПб.: Невский Диалект, – 352 с.:ил. (библиотека). Т. А. Павловская. Pascal. Программирование на языке высокого уровня. – СПб.: Питер, – 393 с.: ил. (файл). Соболь Б.В. Информатика: Учебник. (электронный учебник). ТОИ- ИМ 13

14 АЛГОРИТМЫ. Ориентировка Алгоритм предназначен для структуризации решаемой задачи и описания процедуры пошагового решения задачи Провести системный анализ задачи: выделить цели поставленной задачи определить ее место и рамки в задаче верхнего уровня разбить задачу на слабосвязанные блоки (подзадачи) определить последовательность выполнения действий (шагов решения задачи) определить правила взаимодействия блоков (подзадач) Выполнить следующие действия: определить цель решения задачи как ожидаемый результат определить виды и параметры связи задачи с задачами верхнего и параллельного уровня определить виды и параметры связи подзадач между собой определить содержание каждого шага решения задачи Смысловая ориентировка (зачем делать) – Функционально-целевая ориентировка (что делать) – Исполнительская ориентировка (как делать) – 14 ТОИ- ИМ

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

16 Разработка алгоритма Постановка задачи: Определение совокупности входных данных (составление перечня), Определение совокупности выходных данных (составление перечня), Определение состава и последовательности действий для получения из совокупности входных данных совокупности выходных – АЛГОРИТМА решения задачи, Определение методов проверки разработанного алгоритма (тестирования). Разработка алгоритма решения определение основных действий (групп действий), детализация действий, описание основных действий в действиях более низкого уровня – детализация выполняется до тех пор, пока каждый из шагов алгоритма не описывается как детальная операция: способ выполнения действия с учётом внешних условий (ситуации). Каждый из шагов алгоритма может представлять собой: простое действие (операцию) по обработке данных, например, ввод/вывод или присваивание значения переменной, последовательность из группы операций, выбор из двух или более альтернатив в зависимости от истинности или ложности некоторого условия, циклическое повторение группы операций, изменение порядка выполнения шагов алгоритма. ТОИ-ИМ 16

17 Вербальное описание алгоритма Вербальное описание алгоритма может быть двух видов: свободное словесное описание и псевдокод. ПРИМЕР 2: Даны три разные числа A, B, C. Вывести их на печать в порядке убывания. ввести три числа A, B, C проверить A¬=B, A¬=C, C¬=B если: A>B то: max1=A, max2=B иначе: max1=B, max2=A если: max1>C то: если: max2>C то: max3=C иначе: max3=max2 max2=C иначе: max3=max2 max2=max1 max1=C вывести на печать max1, max2, max3 ПРИМЕР 1: Переход человека через автомобильную дорогу на нерегулируемом переходе стоя на тротуаре посмотреть налево и, когда слева близко едет машина, то ожидать проезда машин стоя на тротуаре, смотреть налево, если слева близко нет машин, то идти до середины дороги, дойдя до середины дороги – остановиться и посмотреть направо, если справа близко едет машина, то стоять, смотреть направо, если близко машины нет, то перейти дорогу до конца. ТОИ-ИМ 17 Свободное словесное описание

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

19 Графическая схема алгоритма Графическое представление алгоритма имеет две разновидности: блок-схема и схема Насси-Шнайдермана. ТОИ-ИМ 19 Блок схемы В блок-схеме условными графическими элементами и надписями внутри и рядом с ними описываются действия и операции алгоритма: графические элементы алгоритмов представляют базовые операции деятельности (последовательности действий, выбор конкретного действия в зависимости от условия, повторение последовательности действий в зависимости от условия – цикл и др.), надписи внутри графических элементов описывают выполняемые действия и условия, надписи вне графических элементов – это комментарии и результаты проверки выполнения условий (ДА или НЕТ и TRUE или FALSE).

20 Графическая схема алгоритма: Блок-схемы ТОИ-ИМ 20 Начало алгоритма Переход человека через автомобильную дорогу на нерегулируемом переходе Стоять на тротуаре в начале перехода Стоять, ждать проезда машины Есть слева близко машина? Смотреть налево ДАНЕТ Идти до середины дороги Дойдя до середины дороги остановиться Смотреть направо Стоять, ждать проезда машины Есть справа близко машина? ДАНЕТ Перейти дорогу до конца Конец алгоритма Алгоритм "Переход человека через автомобильную дорогу на нерегулируемом переходе": Из приведенного примера видно, что на блок-схеме наиболее простым способом можно показывать обратные связи алгоритмов, что в других способах представления алгоритма сделать труднее.

21 Графическая схема алгоритма (некоторые элементы по ГОСТ ) ТОИ-ИМ 21 ЛИНИЯ ПОТОКА – указание последовательности связей между элементами (можно использовать стрелки на концах для указания направления связей). или ПРОЦЕСС – выполнение операций или группы операций, в результате которых изменяется значение, форма представления или расположение данных РЕШЕНИЕ – выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий ПУСК – ОСТАНОВ – начало, конец, прерывание процесса обработки данных или выполнения программы КОММЕНТАРИЙ – связь между элементом схемы и пояснением ПРЕДОПРЕДЕЛЕННЫЙ ПРОЦЕСС (ПОДПРОГРАММА) – использование ранее созданных и отдельно описанных алгоритмов или программ

22 Графическая схема алгоритма (по ГОСТ ) ТОИ-ИМ 22 ВВОД - ВЫВОД – преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод) ДОКУМЕНТ – ввод-вывод данных, носителем которых служит бумага СОЕДИНИТЕЛЬ – указание связи между прерванными линиями потока, связывающими символами МЕЖСТРАНИЧНЫЙ СОЕДИНИТЕЛЬ – указани связи между разъединенными частями схем алгоритмов и программ, расположенных на разных листах ПАРАЛЛЕЛЬНЫЕ ДЕЙСТВИЯ – начало или окончание двух и более одновременно выполняемых операций МОДИФИКАЦИЯ – выполнение операций, меняющих команды или группу команд, изменяющих программу

23 Графическая схема алгоритма ТОИ-ИМ 23 Для рисования блок-схем следует использовать специально предназначенные для этого средства Microsoft Word так и называющиеся – Блок-схема. Расположение средства "Блок-схема" в MS Word 2007

24 Графическая схема алгоритма ТОИ-ИМ 24 Расположение средства "Блок-схема" в MS Word 2003

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

26 Графическая схема алгоритма Если в контекстном меню выбрать поле "Формат автофигуры", то можно выполнить: цветную заливку внутреннего поля элемента, уменьшить поля отступов (снизу, сверху, справа и слева), увеличить толщину линий автофигур, сделать линии автофигур цветными, и многое другое. Для того чтобы готовый алгоритм можно было перемещать по страниц без опасения разрушить взаимное расположение элементов и связей, необходимо выделить все автофигуры в алгоритме (удерживая клавишу SHIFT), затем установить курсор на рамку любой автофигуры, нажать правую клавишу мыши и выбрать в поле "Группировка" команду "Группировать". Алгоритм можно считать завершённым. ТОИ-ИМ 26

27 Графическая схема алгоритма Пример Даны три разные числа A, B, C. Вывести их на печать в порядке убывания. ввести три числа A, B, C проверить A¬=B, A¬=C, C¬=B если: A>B то: max1=A, max2=B иначе: max1=B, max2=A если: max1>C то: если: max2>C то: max3=C иначе: max3=max2 max2=C иначе: max3=max2 max2=max1 max1=C вывести на печать max1, max2, max3 ДА НЕТ A>B Ввод A, B, C НЕТ max1=A max2=B max1=B max2=A max1>C max3=max2 max2=max1 max1=C НЕТ max2>C ДА max3=С Вывод max1, max2, max3 A=B, A=C, B=C НЕТ ДА введите разные числа max3=max2 max2=C ТОИ-ИМ 27

28 Графическая схема алгоритма ТОИ-ИМ 28 Схемы Насси-Шнейдермана Такая схема визуально представляет собой подобный псевдокоду текст, помешённый в прямоугольные блоки, структурирующие алгоритм. Это более наглядный способ представления алгоритмов, чем псевдокод, но менее громоздкий, чем блок-схемы. Алгоритм "Переход человека через автомобильную дорогу на нерегулируемом переходе" Стоять на тротуаре в начале перехода Смотреть налево Слева близко едет машина? ДАНЕТ Стоять, ждать проезда машины Идти до середины дороги Дойдя до середины дороги остановиться Смотреть направо Справа близко едет машина? ДАНЕТ Стоять, ждать проезда машины Перейти дорогу до конца

29 Таблица решений ТОИ-ИМ 29 Табличный способ изображения алгоритма – это таблица решений. В таблице для каждого логического выражения показывается действие (операция). Например: Таблица решений алгоритма "Переход человека через автомобильную дорогу на нерегулируемом переходе": Условие Решение (действие/операция) Стоим в начале перехода Смотреть налево на дорогу Слева близко едет машина Ожидать проезда машин Слева не едет близко машина Идти по переходу до середины дороги Дошли до середины дороги Остановиться, смотреть направо Справа едет близко машина Ожидать проезда машин Справа не едет близко машина Перейти дорогу по переходу до конца

30 Описание алгоритма средствами языка программирования ТОИ-ИМ 30 Алгоритм описывается с помощью синтаксических конструкций какого- нибудь языка программирования. Пример реализации алгоритма "Вычисление факториала 25!" на языке Си #include int main () { int n, k; float p; printf ("Введите факториал k = "); scanf ("%d",&k);/* Ввод факториала */ p = 1; n = 1;/* Начальные значения */ while (n <= k) { p = p * n;/* Вычисление в цикле */ n++; /*Приращение переменной цикла*/ } printf("Значение факториала p = %G\n ",p); return 0; }