- •1. ИНФОРМАЦИЯ, ЕЁ СВОЙСТВА, ИЗМЕРЕНИЕ, ПРЕДСТАВЛЕНИЕ И КОДИРОВАНИЕ
- •1.1. Информатика – предмет и задачи
- •1.2. Информация, ее виды и свойства
- •1.3. Представление об информационном обществе
- •1.4. Кодирование информации
- •1.5. Практическое занятие № 1. Системы счисления. Перевод чисел из одной системы счисления в другую. Арифметические операции в позиционных системах счисления
- •1.6. Кодирование текстовых и символьных данных
- •1.7. Кодирование графических данных
- •1.8. Кодирование звуковой информации
- •1.9. Структуры данных
- •1.10. Файлы и файловая структура
- •1.11. Измерение и представление информации
- •1.12. Теоремы Шеннона
- •1.13. Математические основы информатики
- •1.13.1. Алгебра высказываний (алгебра логики)
- •1.13.2. Элементы теории множеств
- •2. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
- •2.1. История развития вычислительной техники
- •2.2. Классификация компьютеров по сферам применения
- •2.3. Базовая система элементов компьютерных систем
- •2.4. Функциональные узлы компьютерных систем
- •2.5. Архитектура ЭВМ
- •2.6. Совершенствование и развитие архитектуры ЭВМ
- •2.6.1. Архитектуры с фиксированным набором устройств
- •2.6.2. Открытая архитектура
- •2.6.3. Архитектура многопроцессорных вычислительных систем
- •2.7. Внутренняя структура ЭВМ
- •2.7.4. Внешние запоминающие устройства
- •2.8. Внешние устройства компьютера
- •2.8.1. Видеотерминалы
- •2.8.2. Устройства ручного ввода информации
- •2.8.3. Устройства печати
- •2.8.4. Устройства поддержки безбумажных технологий
- •2.8.5. Устройства обработки звуковой информации
- •2.8.6. Устройства для соединения компьютеров в сеть
- •3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЭВМ
- •3.1. Состав системного программного обеспечения
- •3.2. Операционные системы
- •3.3. Виды операционных систем и их базовые понятия
- •3.4. Процессы и потоки
- •3.5. Управление памятью
- •3.6 Организация ввода-вывода
- •3.7 Драйверы устройств
- •3.8 Файловые системы
- •3.9 Файловые системы Microsoft Windows
- •3.9.1. Файловая система FAT16
- •3.9.3. Файловая система NTFS
- •3.9.4. Сравнение файловых систем FAT16, FAT32 и NTFS
- •3.10 Операционная система Windows
- •3.11 Служебные программы
- •3.13 Прикладное программное обеспечение
- •3.13.1. ППО общего назначения
- •3.13.2. ППО специального назначения
- •3.17. Практическое занятие № 6. Табличный процессор Excel. Основные понятия и общие принципы работы с электронной таблицей. Создание и заполнение таблиц постоянными данными и формулами. Построение диаграмм и графиков
- •3.18. Практическое занятие № 7. Табличный процессор Excel. Сортировка и фильтрация (выборка) данных. Сводные таблицы, структурирование таблиц. Расчёты в Excel
- •4. БАЗЫ ДАННЫХ (БД) И СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ (СУБД)
- •4.1. Базы данных в структуре информационных систем
- •4.2. Классификация баз данных и виды моделей данных
- •4.3. Нормализация отношений в реляционных базах данных
- •4.4. Проектирование баз данных
- •4.5. Этапы развития СУБД. Реляционная СУБД Microsoft Access – пример системы управления базами данных
- •4.6. Практическое занятие № 8. СУБД Access 97. Создание однотабличной базы данных. Отбор данных с помощью фильтра. Формирование запросов и отчётов для однотабличной базы данных
- •5. КОМПЬЮТЕРНЫЕ СЕТИ И ОСНОВЫ ЗАЩИТЫ ИНФОРМАЦИИ
- •5.1. Назначение и классификация компьютерных сетей
- •5.2. Режимы передачи данных в компьютерных сетях
- •5.3. Типы синхронизации данных при передаче и способы передачи информации
- •5.4. Аппаратные средства, применяемые при передаче данных
- •5.5. Архитектура и протоколы компьютерных сетей
- •5.6. Локальные вычислительные сети (ЛВС) и их топологии
- •5.7. Физическая передающая среда ЛВС и методы доступа к ней
- •5.8. Примеры сетей. Глобальная сеть Интернет
- •5.9. Службы сети Интернет
- •5.10. Поиск информации в Интернет
- •5.10.1. Поисковые машины
- •5.12. Основы и методы защиты информации
- •5.13. Политика безопасности в компьютерных сетях
- •5.14. Способы и средства нарушения конфиденциальности информации
- •5.15. Основы противодействия нарушению конфиденциальности информации
- •5.16. Криптографические методы защиты данных
- •5.17. Компьютерные вирусы и меры защиты информации от них
- •6. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ. МОДЕЛИ И ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ
- •6.1. Алгоритм и его свойства
- •6.1.2. Графическое представление алгоритмов
- •6.2. Принципы разработки алгоритмов и программ для решения прикладных задач
- •6.2.1. Процедурное программирование
- •6.2.3. Функциональное программирование
- •6.2.4. Логическое программирование
- •6.2.5. Объектно-ориентированное программирование (ООП)
- •6.3. Методы и искусство программирования
- •6.4. Обзор языков программирования
- •6.5. Понятие о метаязыках описания языков программирования
- •6.6. Моделирование как метод решения прикладных задач
- •6.7. Основные понятия математического моделирования
- •6.8. Информационное моделирование
- •6.9. Практическое занятие № 11. Вычисления в среде Mathcad
- •6.10. Практическое занятие № 12. Вычисления в среде Matlab
- •СПИСОК ЛИТЕРАТУРЫ
- •ОГЛАВЛЕНИЕ
6. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ. МОДЕЛИ И ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ
6.1.Алгоритм и его свойства
6.1.1.Различные подходы к понятию “алгоритм”. Алгоритм – одно из фундамен-
тальных понятий информатики. Алгоритмизация наряду с моделированием выступает в ка- честве общего метода информатики. Особенность положения состоит в том, что при реше- нии практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, почти всегда можно не опираться на высокую формализацию данного понятия. В таких слу- чаях достаточно содержательного толкования понятия алгоритма и рассмотрения его основ- ных свойств. При таком подходе алгоритмизация выступает как набор определенных прак- тических приемов, особых навыков рационального мышления в рамках заданных языковых средств.
Понятие алгоритма в математике прошло большой путь развития. Общее определение алгоритма, имеющее интуитивный характер следующее.
Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи из данной массовой проблемы. Таким образом, алгоритм всегда связан с решением массовой проблемы. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Примеры алгоритмов: извлечение квадратного корня, предельный переход, нахождение производной и тому подобное. Приведенное понятие алгоритма нестрогое. В нем встречаются слова, точный смысл которых не установлен, например, “способ”. Тем не менее, даже при таком определении можно выделить некоторые характерные черты алго- ритма:
§дискретность. Каждая последующая величина получается из значений преды- дущих по определенному закону. Все величины получаются последовательно друг за другом;
§детерминированность. Между всеми величинами, получаемыми алгоритмом, существует жесткая причинная связь. Последующие значения зависят от пре- дыдущих;
§элементарность шагов алгоритма. Закон получения последующей системы ве- личин из предшествующей должен быть простым;
§массовость. Начальная система величин выбирается из некоторого множества. Начальные условия могут варьироваться в бесконечных пределах;
§результативность. Конечный результат всегда должен быть получен. Описанные свойства алгоритма следует считать эмпирическими. Они выявлены на
основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Слово “алгоритм” происходит от имени математика аль Хорезми (ал Горезми – алгоритм). Интуитивное понятие алгоритма работает, когда речь идет о найденном алгоритме решения конкретной задачи. Положение существенно меняется, если возникает алгоритмическая про- блема, решение которой не найдено, и требуется установить, имеет ли она решение. В этом случае надо доказать либо существование алгоритма, либо его отсутствие. Первое можно сделать путем фактического описания процесса, решающего задачу. В этом случае достаточ- но и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Доказать не существование алгоритма таким путем невозможно. Для этого необходимо точное формальное определение.
Вуточнении понятия алгоритма выделяются три направления:
Абу Джафар Мухаммад ибн Муса ал-Хорезми (ок. 783- ок. 850) – арабский математик.
237
q уточнение понятия эффективно вычислимой функции. Этим занимались А. Чёрч и К. Гёдель . В результате был выделен класс частично рекурсивных функций, имеющих строгое математическое определение;
qмашинную арифметику. Здесь сущность понятия алгоритма раскрывается пу- тем рассмотрения процессов, осуществляемых в вычислительной машине;
q направление, связанное с понятием нормальных алгоритмов из работ А. Маркова .
Существование различных определений понятия алгоритма имеет и свои преимуще- ства, так как для решения различных задач удобно использовать различные наиболее подхо- дящие для этого случая определения.
Первое направление уточнение – понятия алгоритма – связано с точным описанием специального класса функций, называемых рекурсивными. Числовые функции, значения ко- торых можно вычислить посредством алгоритма, называются вычислимыми функциями. По- нятие алгоритма здесь не определено формально точно, поэтому понятие вычислимой функ- ции оказывается интуитивным. Однако совокупность вычислимых функций, соответствую- щих условиям 1-5, т.е. удовлетворяющих характерным чертам алгоритма для многих процес- сов, оказалась одной и той же, легко описываемой в математических терминах. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычисли- мых функций при самом широком понимании алгоритма, называется совокупностью рекур- сивных функций.
Рекурсивные функции впервые описаны Гёделем, затем в 1936 году Чёрч пришел к такому же классу функций. Анализ идей, лежащих в основе определения рекурсивных функ- ций, позволил Чёрчу высказать гипотезу о том, что класс рекурсивных функций тождестве- нен с классом всюду определенных вычислимых функций. Эта гипотеза известна под именем тезиса Чёрча; доказать ее нельзя, так как понятие вычислимой функции точно не определе- но. В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о её рекурсив- ности. Понятие рекурсивной функции строгое. Поскольку в алгоритмических проблемах речь обычно идет не об алгоритмах, а о вычислимости некоторых, специальным образом по- добранных решающих проблему функциях, то можно строго доказать, что решающая кон- кретную задачу функция не может быть рекурсивной, а, следовательно, не существует и ал- горитма решения этой задачи. Именно этим путем Чёрч доказал неразрешимость алгоритми- ческой проблемы логики предикатов.
Если первое направление уточняет понятие алгоритма через класс рекурсивных функ- ций, то второе, связанное с машинной арифметикой, сначала уточняет понятие алгоритма, а затем определяет класс вычислимых функций. Это направление развито Э. Постом и А. Тьюрингом . Основная идея этого направления заключается в том, что алгоритмиче- ские процессы – это процессы, которые могут имитироваться на подходяще построенных машинах, которые описываются в точных математических терминах. В результате оказыва- ется, что сложные процессы можно моделировать на простых устройствах. Всякий алгоритм может быть задан некоторой функциональной схемой и реализован в соответствующей ма- шине Тьюринга. Эта гипотеза называется тезисом Тьюринга. Его также нельзя доказать, по той же причине, что и тезис Чёрча. Все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.
Третье направление – теория нормальных алгоритмов Маркова.
Алонзо Чёрч (1903 – 1995) – американский математик и логик.
Курт Фридрих Гёдель (1906 – 1978) – немецкий математик и логик.
Андрей Андреевич Марков (1903 – 1979) – советский математик.
Эмиль Леон Пост (1897 – 1954) – американский математик и логик.
Алан Матисон Тьюринг (1912 – 1954) – английский математик.
238
Будем называть алфавитом A всякое непустое конечное множество символов, сами символы называются буквами. Словом в алфавите A называется всякая конечная последова- тельность букв этого алфавита. Простейшими действиями в нормальных алгоритмах Марко- ва являются последовательные замены вхождений подслов специального вида на другие сло- ва. Нормальный алгоритм может переводить слово α в слово β , причем на множестве слов используемого алфавита слово β однозначно определяется этим алфавитом и словом α . Нормальный алгоритм может быть и не применим к слову α , если он не преобразует α ни в какое слово.
Основное положение об “универсальности” нормальных алгоритмов – принцип нор- мализации: любой алгоритм над конечным алфавитом A эквивалентен относительно A не- которому нормальному алгоритму над A . Этот принцип подобен тезисам Чёрча и Тьюринга и недоказуем из-за неопределенности формального понятия алгоритма. На практике доста- точно ограничиться алгоритмами, действующими на последовательностях натуральных чи- сел и выдающих в качестве значений также последовательности натуральных чисел. Дейст- вия нормальных алгоритмов Маркова похожи на действия машин Тьюринга.
Все эти возникшие исторически независимо друг от друга подходы оказались впо- следствии эквивалентными. Вместе с тем, формально определенный любым из известных
способов алгоритм не может в практическом программировании заменить данное в начале текущего раздела нестрогое определение. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.
6.1.2. Графическое представление алгоритмов. Алгоритм, составленный для неко-
торого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на ал- горитмическом языке. Рассмотрим следующие способы описания алгоритма: словесное опи-
сание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Ника- ких правил составления словесного описания не существует. Этот способ строго не форма- лизуем, допускает неоднозначность толкования при описании некоторых действий, страдает многословностью, поэтому не имеет широкого распространения.
Псевдокод – описание структуры алгоритма на естественном, но частично формали- зованном языке. В псевдокоде используются некоторые формальные конструкции и обще- принятая математическая символика, и он позволяет выявить основные этапы решения зада- чи перед точной ее записью на языке программирования. Единого формального определения псевдокода не существует, поэтому возможны различные псевдокоды.
Блок- схема – это описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций, т. е. это ориентированный граф, указывающий порядок исполнения команд алгоритма. Этот способ весьма нагляден, обеспечивает “читаемость” алгоритма.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускает некоторый произвол при изображении команд. Вместе с тем эти способы позволяют человеку понять суть дела и исполнить алгоритм. Однако для компьютера алгоритм должен быть записан на “понятном” ему языке, такой формализованный язык называют языком программирования. Программа – описание структуры алгоритма на языке программирования.
239
|
|
Рассмотрим подробнее некоторые конструкции, использующиеся для построения |
||||||||
|
|
|
|
|
|
|
|
|
блок-схем (см. рис. 6.1 а-д). Блоки, характеризую- |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
щие начало и конец алгоритма, изображаются |
|
а |
|
Начало |
|
Конец |
|
|
||||
|
|
|
|
прямоугольником со скругленными вершинами; |
||||||
|
|
|
|
|
|
|
|
|
обычным прямоугольником – блоки, предназна- |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
ченные для описания отдельных действий. Анало- |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
гичным образом изображаются блоки для вво- |
|
|
|
|
|
|
|
|
|
|
||
б |
|
Действие |
|
Ввод/Вывод |
в |
да/вывода с неопределенного носителя и вывода |
||||
|
|
|
|
|
|
на печатающее устройство. Наконец, условный |
||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
блок изображается в виде ромба. Вершины графа, |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
представляющего блок-схему, могут быть одного |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
из трех типов: функциональная вершина |
(F ), |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||
г |
|
Вывод на |
Нет |
Проверка |
Да |
|
д имеющая один вход и один выход, предикатная |
|||
|
|
печать |
|
условия |
|
|
вершина (P), имеющая один вход и два выхода, в |
|||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
этом случае функция P передает управление по |
|
|
|
|
|
|
|
|
|
|
||
|
Рис. 6.1. Основные конструкции блок-схем |
одной из ветвей в зависимости от значения |
P , |
|||||||
|
объединяющая вершина (U ), обеспечивающая пе- |
|||||||||
|
|
|
|
|
|
|
|
|
редачу управления от одного из двух входов к выходу. Особое значение для практики алго- ритмизации имеют четыре блок-схемы: композиция или следование (рис. 6.2 а); альтернати- ва или ветвление (рис. 6.2 б); итерация или цикл с предусловием (рис. 6.2 в) или постуслови-
ем (рис. 6.2 г).
|
|
|
|
|
|
|
|
|
|
U |
|
U |
|
|
|
|
нет |
|
да |
|
|
да |
|
|
|||
|
|
|
|
|
|
|
|
||||||
F1 |
|
|
|
|
P |
|
|
|
|
P |
F |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1 |
|
|
F2 |
|
нет |
|
|
да |
|||
F2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
U |
|
|
|
|
F |
|
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
нет |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
а |
|
|
|
|
б |
|
|
|
в |
|
г |
Рис. 6.2. Основные алгоритмические структуры
Доказано, что логическая структура любой программы может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла (теорема Боэма – Якопини ).
Следование – самая важная из структур. Она означает, что действия могут быть вы- полнены друг за другом. Прямоугольники, показанные на рисунке 6.2 а, могут представлять как одну единственную команду, так и множество операторов, необходимых для выполнения сложной обработки данных.
Ветвление – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей (см. рис. 6.2 б). Эта структура на- зывается также ЕСЛИ – ТО – ИНАЧЕ. Каждый из двух путей ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.
Цикл предусматривает повторное выполнение некоторого набора команд программы и позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд. Каждый цикл либо начинается, либо заканчива-
Коррадо Боэм (р. 1923) - итальянский математик.
240