- •1.Предмет и задачи информатики
- •1) Теоретическая информатика:
- •2) Средства информатизации:
- •3) Информационные технологии
- •4) Социальная информатика:
- •2. Истоки и предпосылки информатики.
- •3. Структура современной информатики
- •4. Понятие информации. Носители информации. Сигналы
- •5. Количество информации. Измерение информации. Единицы измерения
- •6. Кодирование информации различных видов
- •7. Свойства информации
- •8. Устройство персонального компьютера
- •9. Основные принципы построения и работы компьютера
- •10. Понятие файла и файловой системы
- •11. Понятие информационной технологии
- •13. Основы интернета. Основные протоколы
- •14. Службы Интернета
- •15. Этапы решения задачи на эвм
- •16. Алгоритм. Свойства алгоритма
- •17. Методы проектирования алгоритмов
- •18. Способы описания алгоритмов. Основы графического способа.
- •19. Структуры алгоритмов. Основные виды вычислительных процессов. Примеры.
- •20. Алгоритмы вычисления суммы функционального ряда. Использование рекуррентных формул. Пример
- •Примеры
- •21. Поиск минимального и максимального элементов массива.
- •22. Сортировка одномерных массивов
- •23. Системы программирования и их состав.
- •24. Понятие о программировании
- •25. Понятие программного обеспечения. Классификация программного обеспечения.
- •26. Назначение операционной системы
- •27. Основные функции операционных систем
- •28. Прикладное по
- •29. Язык программирования Паскаль. Общая характеристика. Основные правила записи программ на языке Паскаль. Структура программы. Пример программы
- •6.Понятие типа данных в Турбо Паскаль
- •Простые типы данных
- •Численные (арифметические) выражения
- •Логические выражения
- •Символьные выражения
- •Составной оператор
- •30. Основные элементы языка Pascal
- •31. Понятие типа данных в Турбо Паскаль
- •Простые типы данных
- •Численные (арифметические) выражения
- •Логические выражения
- •Составной оператор
- •34. Ввод и вывод данных в Паскале.
- •Рассмотрим, для начала, Вывод данных в Паскале.
- •Рассмотрим, теперь, Ввод данных в Паскале.
- •35. Условные операторы Pascal-Паскаль
- •36. Оператор выбора Паскаля
- •37. Оператор безусловного перехода
- •38. Счетный оператор цикла или оператор цикла с параметром
- •39. Цикл с предпроверкой условия
- •40. Цикл с постпроверкой условия
- •42. Процедуры и функции
- •Описание и вызов процедур и функций
- •43. Процедуры.
- •44. Численное решение систем нелинейных уравнений
- •Методы численного решения уравнений и систем нелинейных уравнений
- •3.1. Решение нелинейных уравнений
- •3.1.2. Методы уточнения корней нелинейных уравнений
- •Тогда .
- •С погрешностью
- •Откуда при
- •Пусть тогда и
- •45. Метод половинного деления.
- •Тогда .
- •С погрешностью
- •46. Метод хорд
- •47. 52. Метод Ньютона (метод касательных)
- •48. Комбинированный метод хорд и касательных для уточнения корней нелинейных уравнений
- •49. 51. Метод простых итераций
- •50. Решение систем линейных алгебраических уравнений методом Гаусса
- •53. Метод прямоугольников
- •Составные квадратурные формулы
- •Составные формулы для равномерных сеток
- •Погрешность метода
- •Пример реализации
- •54. Метод трапеций
- •Составная формула
- •59. Интерполяцио́нный многочле́н Лагра́нжа
- •Определение
- •Применения
- •Случай равномерного распределения узлов интерполяции
- •60. Разделё́нная ра́зность
- •Определение
- •Применение
- •История
17. Методы проектирования алгоритмов
Методы проектирования алгоритмов включают: нисходящее проектирование, модульность, структурное программирование.
Нисходящее проектирование предполагает последовательное разбиение исходной задачи на подзадачи до такой конкретизации, когда подзадача сможет быть реализована одним оператором выбранного для программирования языка. По ходу нисходящего проектирования та или иная подзадача может сформировать самостоятельный модуль. Тогда может быть применен принцип модульного программирования. Он обеспечивает легкость составления алгоритмов и отладки программ, легкость сопровождения и модификации, а также возможность одновременной разработки различных модулей разными специалистами с использованием разных языков программирования.
При работе над модулем можно применить принцип структурного программирования. Его цель – повышение читабельности и ясности алгоритма (и программы), более высокой производительности программистов и упрощение отладки. В соответствии с этим принципом для построения любого алгоритма (программы) требуются три типовых блока:
функциональный. Используется для представления линейных алгоритмов. Описывается языком графических символов следующим образом:
циклический. Используется для представления циклических алгоритмов. Описывается языком графических символов одним из двух способов:
конструкция принятия двоичного решения. Применяется для представления разветвляющихся алгоритмов. Описывается языком графических символов следующим образом:
В качестве примера разработаем блок-схему для задачи учета абитуриентов из примера, используя принципы нисходящего проектирования, модульности и структурного программирования.
Выделим в поставленной задаче три основных подзадачи и введем необходимые комментарии:
ввод и размещение в памяти компьютера списка абитуриентов и их оценок по аттестату. При этом количество абитуриентов заранее неизвестно, поскольку документы принимаются у всех желающих;
ввод и анализ оценок по каждому экзамену по каждому абитуриенту. В результате анализа возможно исключение абитуриента из списка. Число абитуриентов известно после решения первой подзадачи. Количество экзаменов известно заранее;
упорядочение списка абитуриентов в зависимости от оценок. Здесь возможно использовать не сами оценки, а средний балл по аттестату и средний балл за вступительные экзамены;
определение нужного подмножества абитуриентов для зачисления. Число студентов набора известно заранее.
В соответствии с выделенными подзадачами определим четыре модуля, взаимосвязь которых представлена на рисунке:
После такой декомпозиции исходной задачи, полученные укрупненные блоки являются модулями, которые могут быть реализованы независимо друг от друга. Единственным ограничением при реализации является необходимость согласования межмодульных связей, когда результат работы одного модуля служит входной информацией другого. Такими данными являются:
от блока Ввод и размещение в блок Ввод и анализ передаются следующие данные: список абитуриентов (фамилии и инициалы), средний балл по аттестату, количество абитуриентов;
от блока Ввод и анализ блоку Упорядочение передаются: список абитуриентов, средний балл по аттестату и средний балл за вступительные экзамены;
от блока Упорядочение блоку Определение передается список абитуриентов и число тех, кто сдал вступительные экзамены.
После этих соглашений введем обозначения для требуемых переменных, придерживаясь принципа мнемоничности имен переменных, а также определим их тип:
фамилия и инициалы студента – FIO, тип - символьный;
начальное число абитуриентов – CHISLO, тип – целый;
число отчисленных абитуриентов – OTCHISL, тип – целый;
оценки по аттестату – ATTECTAT_OCENKI, тип – числовой одномерный массив;
оценки за вступительные экзамены – BCTUPIT_OCENKI, тип – числовой одномерный массив;
средний балл по аттестату – SR_ATTECTAT, тип - вещественная переменная;
средний балл по вступительным экзаменам – SR_BCTUPIT, тип - вещественная переменная;
число вступительных экзаменов – EXAMINE, тип - целая переменная;
объем набора – NABOR, тип - целая переменная.
Разработаем алгоритмы для выделенных четырех модулей, представим их графическими символами, т.е. блок-схемами, и рассмотрим подробнее полученные блок-схемы:
1. Модуль Ввод и размещение;
2. Модуль Ввод и анализ;
3. Модуль Упорядочение;
4. Модуль Определение.
Анализ блок-схем показывает:
при проектировании алгоритма использован принцип нисходящего проектирования, в соответствии с которым исходная задача декомпозирована на подзадачи;
выделенные подзадачи реализованы как отдельные модули, т.е. применен принцип модульности;
в структуре модулей можно выделить типовые конструкции, которые указывались ранее, т.е. алгоритмы выполнены с учетом принципов структурного программирования;
каждый блок из полученных блок-схем может быть закодирован одним оператором такого операторного языка, как, например, Турбо-Паскаль. Это означает, что блок-схемы разработаны с учетом требуемой степени детализации, а сама кодировка блок-схем может быть выполнена читателем самостоятельно.
Таким образом, разработка алгоритма и его кодирование есть не что иное, как представление исходной задачи и способов ее решения средствами, понятными компьютеру.