Алгоритмы:определение и свойства

В 825 г. учёный из города Хорезма Мухаммед ибн Муса Хорезми написал «Книгу о восполнении и противопоставлении», от названия которой пошло слово "алгебра", а от имени учёного — само слово "алгоритм", одно из базовах понятий информатики.

Алгоритм - описание последовательности действий исполнителя, точное выполнение которой приводит к решению поставленной задачи за конечное число шагов.
Процесс разработки алгоритма называется алгоритмизацией.

В определении в явной или неявной форме заложены следующие свойства, которыми должен обладать правильный алгоритм:

1. Дискретность (от лат. discretus - "раздельный", "прерывистый") — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность (определённость) (от лат. determinate - "определённость", "точность") - в каждый момент времени следующий шаг работы однозначно определяется состоянием системы, то есть любое действие строго и недвусмысленно определено и описано для каждого случая. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
3. Понятность — алгоритм должен включать только те команды, которые доступны исполнителю.
4. Массовость (универсальность) - алгоритм должен быть применим к разным наборам исходных данных, то есть решать не одну конкретную задачу, а целый класс подобных. Свойство массовости подразумевает использование переменных в качестве исходных данных.
5. Результативность — завершение алгоритма определёнными результатами (должна быть предусмотрен вариант действий на случай, если исходные данные будут неверны).
6. Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.

Принято говорить, что алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.

Понятие как форма мышления

Любой объект окружающего мира можно описать с помощью признаков.
Признаки делятся на существенные (важные в конкретном описании) и несущественные.

Понятие отражает существенные признаки одного объекта или класса однородных объектов.
Понятие в языке выражается одним или несколькими словами (например, "блог", "клавиатура", "текстовый редактор", "двоичное кодирование"). Слова используются при разговоре; понятия - при мышлении.

Понятие характеризуется содержанием и объёмом.
Содержание понятия - все существенные признаки объекта или класса объектов, отражённые в понятии.
Объём понятия - множество объектов, каждому из которых присущи признаки, составляющие содержание понятия.

Существуют единичные и общие понятия. За единичным понятием скрывается конкретный объект, тот самый, о котором идёт речь; за общим понятием скрывается множество однородных объектов (класс объектов).

При сравнении понятий сравнивают их содержания и объёмы.

Далёкие друг от друга по содержанию понятия, не имеющие общих признаков, называются несравнимыми.
Между сравнимыми понятиями существуют следующие виды отношений:

• тождество - объёмы понятий совпадают;
• пересечение - объёмы понятий совпадают частично;
• подчинение - объём одного понятия полностью включён в объём другого;
• соподчинение - объёмы понятий не пересекаются, но принадлежат более общему (родовому) понятию;
• противоположность - понятия выражены антонимами, при этом объёмы двух понятий разделены объёмом некоторого третьего;
• противоречие - третьего между двумя понятиями нет.

Блок-схемы и базовые блоки

Схе́ма — графическое представление некоторого объекта в общих, главных чертах с помощью условных обозначений.

Блок-схема — распространенный тип схем, описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, а последовательность действий указывается стрелками, соединяющими эти блоки.

Рис 1. Основные виды блоков

Все блоки имеют один вход и один выход. 

Исключениями являются:

• блок начала алгоритма - только выход
• блок конца алгоритма - только вход
• логический блок - один вход и два выхода

Рассмотрим пример:

С клавиатуры вводятся значения радиусов двух окружностей. Нужно найти значение площади кольца, ограниченного этими окружностями.

Рис 2. Блок-схема алгоритма для нахождения площади кольца

Человек и информация

Информация — это знания, получаемые человеком из различных источников.

Сообщение, полученное человеком, может пополнить его знания, если содержащиеся в нём сведения являются для человека понятными и новыми.

Информация понятна, если выражена на языке, доступном для получателя.
Информативность конкретного сообщения зависит от жизненного опыта получателя.

Знания:

• факты - «я знаю, что... »: знания о явлениях, событиях, свойствах объектов, зависимостях между объектами;
• правила - «я знаю, как... », «для того, чтобы... »: знания о последовательностях действий, направленных на достижение некоторой цели. 

В отличие от явления, событие всегда имеет время наступления; говоря о событии, мы имеем дело с результатом.


Получение знаний, или познание реальной действительности — это её отражение в сознании человека.

Формы познания:

• чувственное — с помощью органов чувств;
• логическое (абстрактное мышление) — с помощью логических рассуждений.

Классификация устройств ввода и вывода

Рис 1. Классификация устройств ввода. 

Рис 2. Классификация устройств вывода.

Графическая модель компьютера

Привожу схему - графическую модель компьютера.

Учащиеся должны свободно ориентироваться в этой схеме, уметь воспроизвести её, объяснить, что представляет собой каждый её элемент, давать определения используемым терминам (детальность объяснений зависит от возраста учащегося).

Рис. 1. Графическая модель компьютера

Используемые сокращения:
ОЗУ - оперативное запоминающее устройство;
ПЗУ - постоянное запоминающее устройство;
АЛУ - арифметико-логическое устройство;
УУ - управляющее устройство.

Аппаратное обеспечение - совокупность всех технических устройств, обеспечивающих работу компьютера.

1. Устройства ввода - аппаратные средства для преобразования (перекодирования) информации из формы, понятной человеку, в форму, понятную компьютеру (двоичный код).
2. Устройства вывода - аппаратные средства для преобразования информации из формы, понятной компьютеру, в форму, понятную человеку.
3. Устройства внешней памяти (накопители) - физические приспособления, позволяющие производить считывание и запись информации на соответствующий носитель.

Программное обеспечение - совокупность всех программ, обеспечивающих работу компьютера и решение пользовательских задач.

1. Системное ПО - комплекс программ, которые обеспечивают эффективное управление компонентами компьютерной системы (процессор, оперативная память, устройства ввода-вывода, сетевое оборудование etc). Системное ПО обеспечивает работу других программ и управляет аппаратными ресурсами вычислительной системы. 

Операционная система - комплекс системных программ, обеспечивающий управление ресурсами компьютера, загрузку и выполнение прикладных программ, взаимодействие с пользователями.

Утилиты (англ. utility или tool) — программы, предназначенные для решения узкого круга вспомогательных задач (например, форматирование жёсткого диска, изменение скорости вращения вентиляторов, мониторинг температуры).

Драйвер - программа, управляющая работой конкретного устройства.

2. Прикладное (пользовательское) ПО включает все программы, предназначенные для выполнения пользовательских задач и рассчитанные на непосредственное взаимодействие с пользователем. К прикладному ПО относятся, к примеру, графические, текстовые, звуковые редакторы, браузеры etc.
3. Инструментальное ПО включает все программы, предназначенное для использования в ходе проектирования, разработки и сопровождения программ (в том числе: ассемблеры, трансляторы, компиляторы, интерпретаторы, среды разработки, редакторы исходных текстов etc).

Базы данных. Системы управления базами данных

База данных позволяет упорядоченно хранить данные о группе объектов, обладающих одинаковыми наборами свойств (записная книжка, библиотечный каталог, энциклопедия etc).  

Системы управления базами данных (СУБД) – программы, управляющие хранением и обработкой данных. Позволяют создавать базы данных (БД), а также обеспечивают обработку (сортировку) и поиск данных.
Необходимо различать собственно базы данных, которые являются упорядоченными наборами данных, и СУБД – программы, управляющие хранением и обработкой данных.
Примеры СУБД: Microsoft Access, OpenOffice Base, LibreOffice Base.

Эти СУБД предоставляют многооконный, но не многодокументный интерфейс: единовременно открыта только одна БД.

Содержит обязательное окно базы данных и окна для работы с объектами БД.

Окно БД:

• Таблицы 
• Запросы 
• Формы 
• Отчёты 

Таблицы: вся информация в БД хранится в виде двумерных таблиц – базовый объект БД.
Запись БД – строка таблицы; содержит набор значений свойств, размещённый в полях базы данных.
Поле БД – столбец таблицы; содержит значения определённого свойства Таким образом, запись содержит всю информацию об одном объекте, а поле – однородные данные обо всех объектах.

Каждая таблица должна содержать по меньшей мере одно ключевое поле, содержимое которого уникально для каждой записи в этой таблице. Ключевое поле позволяет однозначно идентифицировать запись в таблице.
 
Запросы позволяют осуществлять отбор данных на основании заданных условий.
 
Формы позволяют отображать данные, содержащиеся только в одной записи. При помощи форм можно добавлять в таблицы новые данные, а также редактировать и удалять существующие. Форма может содержать рисунки, графики и другие внедрённые объекты.

Отчёты предназначены для печати данных в красиво оформленном виде.