Почему компьютер можно назвать формальным исполнителем. Контрольные вопросы
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения: 1. Достать ключ из кармана. 2. Вставить ключ в замочную скважину. 3. Повернуть ключ два раза против часовой стрелки. 4. Вынуть ключ.
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Свойства алгоритмов: 1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке); 2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае); 3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения); 4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными); 5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
Виды алгоритмов: 1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке); 2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание); 3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий) 4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
Для более наглядного представления алгоритма широко используется графическая форма — блок-схема , которая составляется из стандартных графических объектов.
Вид стандартного графического объекта
Выполняемое действие записывается внутри прямоугольника
Условие выполнения действий записывается внутри ромба
Стадии создания алгоритма: 1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает. 2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.
Объект, который будет выполнять алгоритм, обычно называют исполнителем.
Исполнитель — объект, который выполняет алгоритм.
Идеальными исполнителями являются машины, роботы, компьютеры.
Исполнитель способен выполнить только ограниченное количество команд. Поэтому алгоритм разрабатывается и детализируется так, чтобы в нем присутствовали только те команды и конструкции, которые может выполнить исполнитель.
Исполнитель, как и любой объект, находится в определенной среде и может выполнять только допустимые в нем действия. Если исполнитель встретит в алгоритме неизвестную ему команду, то выполнение алгоритма прекратится.
Компьютер – автоматический исполнитель алгоритмов.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Программирование — процесс составления программы для компьютера. Для первых ЭВМ программы записывались в виде последовательности элементарных операций. Это была очень трудоемкая и неэффективная работа. Поэтому в последствии были разработанные специальные языки программирования. В настоящее время существует множество искусственных языков для составления программ. Однако, так и не удалось создать идеальный язык, который бы устроил бы всех.
Рассмотрим процесс управления информационным процессом, в котором в качестве управляемого объекта выбран текст. Другими словами, рассмотрим информационный процесс, связанный с редактированием (изменением состояния) текста.
Во-первых , для того, чтобы преобразовать текст, должен существовать кто-то или что-то, который эти преобразования выполняет. Иными словами, необходим исполнитель этих преобразований.
Во-вторых , процесс преобразования текста необходимо разбить на отдельные операции, которые должны быть записаны в виде отдельных команд исполнителю. Каждый исполнитель обладает определенным набором, системой команд , которые он может выполнить. В процессе редактирования текста возможны различные операции: удаление, копирование, перемещение или замена его фрагментов. Исполнитель редактирования текста должен быть в состоянии выполнить эти операции.
В-третьих , должно быть определено начальное состояние объекта, в данном случае текста, и его требуемое конечное состояние (цель преобразования).
Будем говорить, что информационный процесс, обладающий всеми перечисленными выше свойствами, называется алгоритмом . Исполнитель может выполнить алгоритм, если команды алгоритма входят в систему команд исполнителя.
Например: пользователю необходимо отредактировать текст следующим образом:
1. Выделить символы с 1 по 15.
2. Вырезать этот фрагмент и поместить его в буфер.
3. Установить курсор на позицию после 7-го символа.
4. Вставить вырезанный фрагмент текста.
Этот алгоритм пользователь может выполнять формально. Пользователь в процессе выполнения алгоритма на компьютере будет нажимать клавиши клавиатуры, а при работе с графическим интерфейсом с помощью мыши активизировать те или иные кнопки, пункты меню и т.д. Фактически пользователь будет давать команды объектам программной средыWindows&Office, которые и будут исполнителями алгоритма.
Алгоритмические языки программирования. Представление информационного процесса в форме алгоритма позволяет поручить его автоматическое исполнение различным техническим устройствам, среди которых особое место занимает компьютер. При этом говорят, что компьютер исполняет программу (последовательность команд), реализующую алгоритм на каком-либо языке программирования.
14 Основные понятия алгоритмизации: формальные и неформальные исполнители алгоритмов.
Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определенный набор команд.
Команды, которые может выполнить конкретный исполнитель, образуютсистему команд исполнителя (СКИ).
Класс исполнителей необычайно разнообразен. Прежде всего, в нем выделяют два типа исполнителей: формальных и неформальных . Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.
Например, при многократном прослушивании диска с любимыми мелодиями вы можете быть уверены, что они воспроизводятся проигрывателем (формальным исполнителем) одинаково. Но вряд ли кому-нибудь из певцов (неформальному исполнителю) удастся несколько раз совершенно одинаково исполнить песню из своего репертуара.
Как правило, человек выступает в роли неформального исполнителя. Формальными исполнителями являются преимущественно технические устройства. Человек в роли неформального исполнителя сам отвечает за свои действия. За действия формального исполнителя отвечает управляющий им объект.
Управление — это процесс целенаправленного воздействия одних объектов на другие.
Исполнители являются объектами управления. Управлять ими можно, составив для них алгоритм.
Алгоритм — это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи.
Алгоритмы могут быть записаны в виде таблицы, нумерованного списка на естественном языке или изображены с помощью блок-схемы. Программа — это алгоритм, записанный по правилам понятного исполнителю-компьютеру языка.
15 Алгоритмические конструкции: линейная, разветвление, циклы
Понять , что компьютер — это формальный исполнитель программ.
Научиться рассказывать о компьютере как об универсальном исполнителе, используя термины информатики.
О чем идет речь?
Прежде чем выяснять, каковы основы системного программного обеспечения, из чего состоит машина и как программировать с ее применением, сперва нужно разобраться, что за предмет оказался в фокусе внимания. Наименование его пришло к нам из английского языка. Компьютером в наши дни принято называть такую электронную машину, которую можно запрограммировать для накопления данных, обработки сведений и передачи знаний.
Самый главный, основной предмет, на котором построена ЭВМ – тактовый генератор. Именно он производит сигналы с заданными временными промежутками. Импульсы далее участвуют в рабочем процессе различных внутренних, внешних устройств ввода информации, ее обработки и вывода. Фактически процесс управления предполагает распределение сигналов таким образом, чтобы добиться поставленной перед человеком цели. Самостоятельно направлять все сигналы куда требуется нужды нет: это происходит в автоматическом режиме при наличии соответствующего программного управления. Правда, успешным будет результат только в условиях адекватного кода без ошибок.
Клавиатура и мышь.
Звук. К южному мосту может подключаться интегрированная в системную плату микросхема, которая обеспечивает обработку цифрового звука (эту функцию может выполнять также звуковая плата, которая подключается к шине PCI).
С помощью аудиоразъемов к системной плате могут подключаться микрофон, колонки или наушники.
4. Вспомогательные алгоритмы
Нередко в одной программе приходится рисовать одно и то же изображение несколько раз. Получение этого изображения удобно оформить в виде вспомогательного алгоритма, который можно использовать нужное число раз, обращаясь к его названию.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Вспомогательный алгоритм решает некоторую подзадачу основной задачи. Вызов вспомогательного алгоритма в программе заменяет несколько команд одной командой.
Пример 8.6. Напишем программу, выполнив которую исполнитель Чертежник нарисует следующий рисунок:
Данный рисунок состоит из трех одинаковых фигур, поэтому для рисования одной фигуры можно оформить вспомогательный алгоритм figura .
Описание основного алгоритма будет следующим:
- перемещение в начальную точку;
- рисование фигуры;
- перемещение ко второй фигуре;
- рисование фигуры;
- перемещение к третьей фигуре;
- рисование фигуры.
При решении задач над проектом могут работать несколько человек (или десятков человек). Каждый из членов коллектива делает часть своей работы и оформляет ее как отдельный вспомогательный алгоритм.
Алгоритмы построения чертежей человек разрабатывает с глубокой древности. Появление чертежей связано с практической деятельностью человека — возведением укреплений и городских построек. Первые сведения о чертежах, напоминающих современные, связаны с именем Леонардо да Винчи (1452—1519) —итальянского ученого и художника, который в технических рисунках и эскизах раскрывал свои идеи в области техники и строительства.
В настоящее время чертежи широко применяются в различных отраслях строительства, сельского хозяйства, промышленности и т. д. Сегодня для построения чертежей используются специальные программы, позволяющие автоматизировать процесс черчения. Для применения таких программ специалист должен овладеть навыками работы с имеющимися в них инструментами и алгоритмами построения различных чертежей. Вот логотипы подобных программ:
Пример 8.2. Поле исполнителя Чертежник.
Пример 8.3. Запись алгоритма по действиям:
- 1) 1 + 2 = 3 (части);
- 2) 3 ∙ 2 = 6 (частей);
- 3) 120 : 6 = 20 (м);
- 4) 20 ∙ 2 = 40 (м).
Исполнитель Чертежник должен нарисовать прямоугольник длиной 4 клетки и шириной 2 клетки. Программа для исполнителя Чертежник :
Горячие клавиши Windows
Сочетания, комбинации клавиш или как их ещё называют «горячие клавиши» я условно разделяю на те, которые необходимы при работе скажем так в среде Windows и на те, которые используются при работе с текстом в различных текстовых редакторах.
Есть сочетания клавиш с кнопкой Win. Про них я написал отдельную заметку «Кнопка Win на клавиатуре«
Примечание: Знак «+» между названиями двух клавиш обозначает то, что надо нажать первую клавишу и, не отпуская её — нажать вторую, а знак «(!)» обозначает очень полезную комбинацию.
Полезные сочетания клавиш на клавиатуре при работе на компьютере.
F1 — Вывод справки.
F2 — Переименование выбранного элемента.
F3 — Поиск файла или папки.
F5 — Обновление активного окна (актуально для также для браузеров и множества других программ).
F6 — Переключение между элементами экрана в окне или на рабочем столе.
F10 — Активизация строки меню текущей программы (верхняя строка меню в окне).
F11 — Полно экранный режим.
Tab — Переход вперед по параметрам. (!)
Shift + Tab — Переход назад по параметрам.
Shift + Delete — Удаление выделенного элемента без возможности восстановления.
Shift с любой стрелкой или мышью — Выделите нескольких элементов. (!)
Удерживать Ctrl и наводить мышью на отдельные элементы — Выборочное выделение. (!)
При перетаскивании элемента удержать Ctrl — Копирование выбранного элемента. (!)
При перетаскивании элемента удержать Ctrl + Shift — Создание ярлыка для выбранного элемента. (!)
Ctrl + C — Копирование выделенного текста или объекта (в буфер обмена). (!)
Ctrl + X — Вырезание выделенного текста или объекта (в буфер обмена).
Ctrl + V — Вставка текста или объекта из буфера обмена в то место, где стоит курсор. (!)
Ctrl + Z — Отмена последнего действия.
Ctrl + A — Выделение всего в рабочем окне — всех файлов, всех папок, всех элементов и т.д. в активном окне. (!)
Все сочетания кнопок данного блока, выполняют те же функции и при работе с текстом.
Alt + Enter — Просмотр свойств выбранного элемента.
Alt + F4 — Закрытие программы (если запущенных программ нет — появляется меню для выхода из Windows). (!)
Alt + Пробел — Системное меню активного окна.
Alt + Tab — Переход от одного открытого документа к другому. (!)
Ctrl + Esc — Меню Пуск.
Backspace — Просмотр в окне папки на уровень выше, а в браузере переход к просмотру предыдущей страницы.
Esc — прерывание запущенного действия или выход.
End — Переход к нижней позиции активного окна.
Home — Переход к верхней позиции активного окна.
Полезные сочетания клавиш на клавиатуре при работе с текстом.
Ctrl + Стрелка Вправо — Перемещение курсора в начало следующего слова.
Ctrl + Стрелка Влево — Перемещение курсора в начало предыдущего слова.
Ctrl + Стрелка Вниз — Перемещение курсора в начало следующего абзаца.
Ctrl + Стрелка Вверх — Перемещение курсора в начало предыдущего абзаца.
Ctrl + Shift с стрелкой вниз или вверх — Выделение абзаца.
Ctrl + Shift с стрелкой вправо или влево — Выделение одного целого слова.
CTRL + P — печать текущей страницы или активной (выделенной) области
Shift с любой стрелкой — Выделение текста (по одному символу, букве).
Page Up — Переход на предыдущую страницу.
Page Down — Переход на следующую страницу.
End — Переход в конец строки.
Home — Переход в начало строки.
При работе с текстом такие же функции, выполняют все сочетания из блока №3
Алгоритм
«Выполнение алгоритмов компьютером» — Процессор. Формальный исполнитель Алгоритм и программа Особенности выполнения программы. Особенности выполнения программы. Трансляция. Состав команд ЯМК предложил Джон фон Нейман в 1946г. Этапы выполнения программы. Программа. 1. 0011+0101. Данные. Компьютер. 4. 3.
«Data Mining» — Литература по Data Mining. Пример 2. История Data Mining. Системы обработки экспертных знаний. Кибернетические методы. Для карт Кохонена: карты входов, выходов, другие специфические карты. Преимущества метода. Сложность разработки и эксплуатации приложения Data Mining. Процесс конструирования. Критерии: Точность распознавания Ошибка.
«Алгоритмы в информатике» — Полная форма. Структура ветвления. Приведите, пожалуйста, еще примеры циклического алгоритма. Нет. Линейный. Вспомните: что такое алгоритм? Действие. Структура цикла. Алгоритмы можно описать: словесно; таблично; с помощью программы; графически. Как можно представить алгоритм? Действие N. Циклический.
«Логические выражения» — Содержание. ?. Выражается словами ЕСЛИ…, ТО… Логическое следование или Импликация. Цель. Логическое отрицание. Пример: для сдачи экзамена необходимы знания или везение. Логическое следование. Логические выражения. Запомни знак! 1.Логические 2. Предикаты. утверждения. Обозначается значком.
«Команда алгоритма» — Каждая команда алгоритма должна определять однозначное действие исполнителя. 2.Понятность. 1.Точность. Команда 2. Серия. … Команда n. Команда 1. Линейный алгоритм. Свойства алгоритма. Циклический алгоритм. Алгоритм, в котором команды выполняются последовательно одна за другой, называется … Условие.
«Линейный алгоритм» — От куда мы брали информацию. Мы живём по линейному алгоритму. И то в нас заложено. Мы брали информацию из головы. Линейный алгоритм-. Как механизм в часах: после 1,следует 2, после 2-3, после 3-4 должен работать алгоритм: всё на своём месте: после 1,следует 2, после 2-3 и т. д. Линейный алгоритм в жизни.
Насколько глубоко мы погрузимся в тему?
Давайте для начала в общих чертах поговорим об уровнях на которых можно рассматривать компьютер. Каждый уровень основывается на предыдущем. Начнём с самого верха.
Уровень прикладных программ. Здесь находятся все пользовательские приложения, это браузер, Microsoft Office, блокнот, а также веб-сервер IIS, SQL Server, различное middleware вроде Java и .Net и все скриптовые языки, будь то Ruby, PHP или Bat-файлы.
Уровень операционной системы. ОС можно рассматривать как:
- Менеджер ресурсов — память, жёсткие диски, принтеры, экран, клавиатура ограниченные ресурсы которые совместно используются запущенными на компьютере программами.
- Виртуальная машина — файл это наглядный пример виртуального объекта. Он представляет абстракцию данных на диске, API для работы с ним и так же добавляет концепцию прав доступа. Вместо файла могла быть концепция контейнера данных и совершенно другого API. Таких виртуальных объектов в ОС много.
- Платформа — ОС предоставляет программные модели и примитивы для построения программ. К примеру Windows Drivers Framework позволяет быстро разрабатывать драйвера, окна в Windows используются для построения сложных пользовательских интерфейсов. Dll — предоставляет модель расширения функционала программы через плагины, а так же механизм для реализации читалки экрана через ловушки клавиатуры (см. LowLevelKeyboard hook).
Уровень архитектуры компьютера. Он представлен материнской платой, которая имеет определённый форм-фактор, встроенные функции закодированные в микросхемах называемых чип-сетом и порты, через которые можно расширять функционал компьютера подключив графическую карту, сетевую карту, дополнительную оперативную память (RAM), жёсткие диски, клавиатуру и пр. Порты влияют на скорость работы и возможности компьютера, что и будет определять его назначение будь то сервер для обработки тысяч запросов в секунду, планшет для пользования Интернетом или игровой ПК с несколькими видеокартами. ОС абстрагирует особенности материнской платы.
Микросхемы выглядят как на картинке ниже и представляют собой мини-компьютер выполняющий простые программы для низкоуровневых задач, к примеру прочитать данные от клавиатуры и передать их дальше чтобы они достигли в конечном счёте процессора. Как правило реализованы в виде аналоговой непрограммируемой микросхемы или микроконтроллера, программируемого на языке С.
Материнскую плату можно рассматривать как колонию микросхем которые общаются между собой через шины и через них циркулируют данные от подключенных устройств к процессору и обратно. Чип-сет — это своего рода нервная система компьютера. Все чипы на материнской плате были изначально созданы чтобы работать друг с другом. Некоторые из них могут иметь особые функции, к примеру таймер или хранение настроек BIOS. Пожалуй самый важный из них тот что имеет встроенную программу (прошивку, BIOS, UEFI) которая начинает выполняться как только появляется электричество. Она находит жёсткий диск с загрузчиком Windows и передаёт тому управление который в свою очередь запускает исполняемый файл ОС, который можно назвать Windows10.exe, на самом деле NtOsKrnl.exe. BIOS знает что искать благодаря соглашению между производителями железа и операционных систем.
Вокруг материнской платы можно собрать мобильный телефон, игровую приставку, серверную станцию или умное устройство. На картинке ниже распространённые форм-факторы материнских плат.
Уровень микроархитектуры представлен процессором (CPU), это сердце материнки и весь чип-сет нужен для обслуживания CPU. Процессор это компьютер в компьютере, более мощный и продвинутый микроконтроллер которому не нужна прошивка, потому как поток команд подаётся на лету, когда планировщик потоков поменял контекст процессора. Функционал процессора делится на подсистемы, к примеру компонент занимающийся математическими и логическими операциями, математический сопроцессор, кэш. Какие-то из них раньше были отдельным чипом на материнской плате, но сейчас их сделали частью ЦПУ, например контроллер прерывания и микросхема под названием “Северный мост” что увеличило скорость работы.
Микроархитектура это не то же самое что архитектура. Весь функционал CPU разделён на компоненты, которые работают сообща. Эти компоненты и их взаимодействие и есть микроархитектура. На блок-схеме ниже они представлены цветными прямоугольниками и квадратиками.
 |
Архитектура процессора это по сути документ который описывает какой функциональностью он должен обладать для того чтобы соответствовать к примеру архитектуре x86, x64 или ARM применяемой на мобильных устройствах. В этом документе описано какие должны поддерживаться команды, назначения регистров и логика работы. Создатели процессоров Intel, AMD, Эльбрус могут реализовывать эту функциональность как угодно и добавлять к ней новые возможности в виде команд, регистров, флагов, прерываний и если ОС знает о них то может использовать. В терминах ООП архитектура ЦПУ — это интерфейс, а микроархитектура — его реализация.
Логические схемы. Цветные прямоугольники с блок-схемы CPU состоят из логических схем, которые производят свои операции на последовательностях нулей и единиц. Процессор видит все данные и команды в виде битов (0 и 1), по формуле любое десятичное число можно представить в виде последовательности 0 и 1, а вот что значит конкретное число зависит от контекста. Это может быть код, цифра, буква. Арифметическое и логическое устройство (ALU) умеет производить сложение двух чисел через побитовые операции. Побитовые алгоритмы сложения, вычитания, умножения и деления давно известны, разработчикам логической схемы их только надо эффективно реализовать.
Цифровые схемы работают с данными на уровне нулей и единиц, а аналоговые полагаются на эксплуатирование законов физики. Они выполняют простейшие манипуляции над битами, такие как сдвиги, AND, OR, XOR. Через эти примитивы реализуются более сложные операции. На картинке ниже представлен аналоговый оператор AND реализованный через транзисторы. На выходе схемы ненулевое напряжение будет только если оно есть на обоих входных контактах (Вх1 и Вх2), иначе ноль вольт. Точно так же работает оператор && в C#. Цифровые схемы в конечном счёте основаны на аналоговых. Физически логические элементы в логических схемах могут быть реализованы не только электронными но и механическими, гидравлическими, оптическими и другими способами.
Уровень радиоэлементов. Физически аналоговые схемы полагаются на радиоэлементы, которые собственно и эксплуатируют законы физики. Преимущественно это полупроводники, т.е. в определённых условиях они могут проводить электричество, а могут и нет. Диод проводит ток только в одном направлении, если его выпаять, развернуть на 180 и впаять обратно, то ток через него проходить не будет. Транзистор пропускает ток только если есть напряжение на управляющей ножке. Человечество научилось делать транзисторы микроскопическими и потому их можно размещать на маленькой плате миллионами. На картинках ниже полупроводниковые радиоэлементы и обычный транзистор рядом с нано транзистором под электронным микроскопом.
Уровень законов физики. И наконец самый нижний уровень — это уровень законов физики которые заключены в полупроводниковые радиоэлементы.
Мы будем много говорить про уровень ОС и чуть меньше про архитектуру компьютера, микроархитектуру, аналоговые схемы и радиоэлементы. К последней части у вас должно быть понимание как это всё работает вместе.
