- •Информатика Учебное пособие
- •Содержание
- •Предисловие
- •Тема 1. Введение
- •1.1. Цель и задачи курса «Информатика»
- •1.2. Объекты и составные части информатики
- •1.3. Информатика как единство науки и технологии
- •Контрольные вопросы
- •Тема 2. Основные понятия информатики
- •2.1. Место информатики в системе наук
- •2.2. Основные понятия курса «Информатика»
- •Предмет информатики составляют следующие понятия:
- •Информация классифицируется по видам. (рис. 2.4.)
- •Тема 3. Основы дискретной математики.
- •3.2. Основы логики
- •Элементарные булевые функции
- •Из них выделим функцию "отрицание X" (обозначается -X). Эта функция представлена в таблице
- •3.3. Графы и деревья
- •А) граф g; б) остов графа g; в) другой остов графа g
- •Тема 4. Основные понятия архитектуры эвм
- •Для представления числовых данных в эвм используются естественная и нормальная формы записи чисел.
- •4.2. Системы счисления. Правила перевода чисел из одной системы счисления в другую
- •3. Арифметические операции
- •4.3. Логические элементы компьютера
- •В качестве важных последовательностных схем, выполняемых на одной ис, можно отметить счетчики, сдвиговые регистры, элементы памяти и др.
- •Структурная схема базовой модели мп фирмы Intel представлена на рисунке 4.15.
- •4.5. Организация памяти компьютера
- •Используется два основных типа оперативной памяти:
- •Контрольные вопросы
- •Тема 5. Алгоритмическое решение задач, анализ алгоритмической сложности.
- •5.1. Стратегия решения задач.
- •5.2. Алгоритмы (свойства, реализация алгоритмов)
- •5.3. Структуры данных
- •5.4. Основные вычислительные алгоритмы.
- •5.5. Анализ алгоритмов
- •1. Сравнительные оценки алгоритмов
- •2. Система обозначений в анализе алгоритмов
- •3. Классификация алгоритмов по виду функции трудоёмкости
- •4. Асимптотический анализ алгоритмов
- •Контрольные вопросы
- •Тема 6. Знакомство с языками программирования.
- •6.1. Обзор языков программирования
- •6.2. Основные конструкции программирования
- •Внутри программы значение свойств можно изменять как угодно часто.
- •Константы.
- •На практике наибольшее распространение получили язык функционального программирования lisp и два его диалекта: язык Common lisp и язык Scheme.
- •Наиболее распространенным языком логического программирования является язык Prolog (Пролог).
- •Контрольные вопросы
- •Тема 7. Основы операционных систем
- •7.1. Основные концепции операционных систем
- •7.4. Файловые системы
- •7.6. Обзор современного прикладного программного обеспечения
- •Контрольные вопросы
- •Тема 8. Сети и телекоммуникации
- •Компоненты сети
- •По программной совместимости эвм: однородные (гомогенные) и неоднородные (гетерогенные);
- •8.3. Системы телекоммуникаций
- •Типы телекоммуникационных систем
- •Системы телевещания
- •Системы подвижной связи
- •Сети сотовой подвижной связи
- •Сети транкинговой связи
- •Сети персонального радиовызова
- •Сети мобильной спутниковой связи
- •Волоконно-оптические сети
- •Контрольные вопросы:
- •Тема 9. Сеть Internet
- •9.1. Теоретические основы Internet
- •9.2. Основные понятия (сайт, сокет, сервер, клиент). Web как пример архитектуры «клиент-сервер»
- •9.3. Службы Internet
- •Контрольные вопросы:
- •Тема 10. Графическое программное обеспечение
- •10.1. Иерархия графического программного обеспечения. Графические коммуникации. Графические системы.
- •10.2. Системы растровой и векторной графики
- •Описание объекта является простым и занимает мало памяти;
- •10.3. Графические редакторы
- •Контрольные вопросы
- •Тема 11. Основы защиты информации
- •11.1. Информационная безопасность и ее составляющие
- •11.2. Угрозы безопасности информации и их классификация
- •11.3. Сетевая безопасность
- •11.4. Антивирусные программы
- •Контрольные вопросы
5.2. Алгоритмы (свойства, реализация алгоритмов)
Алгоритм решения задачи – это система точных и понятных предписаний о содержании и последовательности выполнении конечного числа действий, необходимых для решения любой задачи данного типа.
Алгоритм – это конечный набор правил, последовательное применение которых к обрабатываемой информации за конечное число шагов позволяет получить результаты обработки (правила выполнения арифметических действий, правила решения определенных видов уравнений и т.д.).
Слово алгоритм появилось в результате искажения (после перевода на европейские языки) имени выдающего математика IX века Аль –Хорезми, которым были описаны правила выполнения основных арифметических действий в десятичной системе счисления. Понятие алгоритма возникло и используется ранее, чем появление ЭВМ.
Основные свойства алгоритма:
1. Дискретность, т.е. пошаговый характер определяемого им процесса. Описываемый процесс должен быть разбит на последовательность отдельных шагов. При каждом шаге работы алгоритма известно, что считать результатом шага.
2. Детерминированность (однозначность или определенность). Процесс применения правил к исходным данным определен вполне однозначно, результат работы алгоритма также будет однозначен. Запись алгоритма должна быть настолько четкой, полной, продуманной в деталях, чтобы у исполнителя не могло возникать потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма.
3. Массовость. Необходимы алгоритмы, обеспечивающие решение широкого класса задач данного типа. Они предполагают возможность использовать различные допустимые значения исходящих данных.
Например: решение уравнения ах2+вх+с=0 в области действительных чисел может быть найдено по формуле:
, которые применяемы не для одного, а для многих квадратных уравнений с коэффициентами а, в, с, удовлетворяющих условию
D=в2 -4ас0
4. Результативность. При точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен быть получен какой-либо определенный ответ на вопрос задачи.
Под алгоритмизацией понимают процесс разработки алгоритма решения какой-либо задачи.
Формы (способы) записи алгоритмов:
1) Словесный способ алгоритма – содержание последовательных шагов вычислений задается в произвольной форме на естественном языке. Например:
1. Прочитать заданное значение х.
2. Умножить х на 8.
3. Из результата второго действия (шага) извлечь квадратный корень.
4. К результату третьего действия прибавить 1.
5. Умножить х на 3.
6. Результат пятого действия разделить на результат четвертого действия.
7. Записать значение результата у.
Недостатки: низкая наглядность и слабая формализация. Этим способом можно описывать алгоритмы с произвольной степенью детализации.
2) Формульно-словесный способ основывается на задании последовательных шагов алгоритма с помощью математических формул и выражений в сочетании со словесными выражениями. Например:
1. Если Х>0, то перейти к шагу 2, в противном случае перейти к шагу 3.
2. Положить S=+D. Перейти к шагу 4.
3. Положить S=X-A. Перейти к шагу 4.
4. Принять S за искомый результат и остановиться.
Он более компактен и нагляден, но не является строго формальным.
3) Операторные схемы записи алгоритмов – это аналитическая форма представления алгоритма с помощью операторов, описывающих содержание отдельных участков вычислительного процесса. Участки алгоритма могут разделяться по своему назначению. Одни участки предусматривают вычисления с помощью арифметических операций, другие предназначены для проверки некоторых условий, выполнение которых определяет порядок работы алгоритма. Первые называются арифметическими операторами, вторые – логическими операторами. Имеется также группа специальных операторов управления (ввод-вывод данных, оператор останова и т.д.). Весь процесс решения задач состоит из последовательности выполнения таких операторов. Обозначения операторов:
B- ввод исходных данных
A- арифметический оператор
П - оператор печати (вывода)
Р - логический оператор
Я - оператор останова
Операторы имеют номера-индексы в соответствии с порядком их исследования. Логический оператор записывается как функция, аргументом которой служит проверяемое условие P (i=N) или P(υ ≤o)и т.д.
Операторы выполняются последовательно, которые могут нарушить логические операторы и безусловные операторы передачи управления. Если окажется, что проверяемое условие истинно, то очередным становится оператор, стоящий справа от логического оператора, в противном случае, когда логическое условие не соблюдается, оператор – приемник указывается стрелкой. Отсутствие передачи управления от оператора слева к соседнему оператору справа обозначается точкой с запятой (;). Алгоритм завершается оператором останова.
Операторная схема алгоритма сопровождается схемой счета.
Например:
Схема счета представлена в виде таблицы
№ |
Символ-оператор |
Содержание оператора | |
1 2 3 4 5 6 |
В1 Р2 А3 А4 П5 Я6 |
Ввод исходных данных Проверка выполнения логического условия (X>0) Вычисление значения Вычисление значения S= X-A Печать вычисленного значения S Останов | |
Операторная схема выглядит следующим образом:
B1 P2 (х>0) А3; А4 П5 Я6 |
|
Ввел этот метод А.А. Ляпунов в 1954 году. Операторные схемы имеют формальный уровень, близкий к алгоритмическим языкам, и поэтому могут рассматриваться как средство автоматизации программирования.
4) Метод блок-схемы – это графическое изображение логической структуры алгоритма. На блок-схеме каждый этап процесса обработки представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера вычисляемых операций.
Блок может иметь имя (метку). Линия соединения блоков показывает направление процесса обработки данных. Каждое направление называется ветвью.
Перечень блоков, их наименование, функции, формы, размеры определяются ГОСТ 19.003—80. Указанный ГОСТ регламентирует изображение и размеры отдельных блоков в блок-схеме, а также их взаимное расположение. Основные виды блоков приведены в табл. 5.2.
Таблица 5.2
Блок-схемы алгоритмов
Наименование блока |
Графическое представление блока |
Функция блока |
Линейный процесс |
|
Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположение данных |
Проверка условия, логическое решение |
|
Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий |
Ввод-вывод |
|
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод) |
Начало-конец алгоритма (пуск-остановка) |
|
Начало, конец процесса обработки данных |
Предопределенный (заранее описанный) процесс, модуль |
|
Использование ранее созданных или отдельно описанных алгоритмов (модулей) |
Соединитель |
|
Указание связи между прерванными линиями потока обработки данных |
Например:
5) Псевдокод или структурно-стилизованный способ записи алгоритма основан на формализованном представлении предписаний. Разновидность: алгоритмический язык в русской нотации. Это например:
алг. запись
арг. истина
если ложь
нач. массив
кон.
Важнейшая особенность – близость к алгоязыкам программирования.
6) Язык программирования используется для записи алгоритмов в виде, непосредственно доступном ЭВМ.
Программа, написанная на языке программирования, представляет собой последовательность операторов, реализующих заданный алгоритм.
Языки программирования высокого уровня: ФОРТРАН, БЕЙСИК, КОБОЛ, АЛГОЛ, ПАСКАЛЬ, СИ, ПЛ/1 и др.
Например:
На языке Бейсик это выглядит следующим образом:
10 INPUT «Исх. данные», Х, D, А
20 IF X0 THEN 5 Ø
30 S=Х- А
40 Goto 6 Ø
50 S=SQR (X) +D
60 PRINT «Результат=», S
70 END