- •Содержание
- •Информатика. Предмет и задачи
- •Структура информатики
- •Задачи информатики:
- •Измерение и представление информации
- •Сигналы Данные Методы Информация
- •Методы воспроизведения и обработки данных
- •Информационный процесс
- •Меры информации
- •Единицы измерения информации
- •Качественные свойства информации
- •Классификация информации
- •Хранение информации
- •Кодирование данных двоичным кодом
- •Системы счисления
- •Двоичная система счисления
- •Перевод из десятичной системы в двоичную
- •Арифметические операции с двоичными числами
- •Восьмеричная и шестнадцатеричная системы счисления
- •Кодирование числовых данных
- •Кодирование текстовых данных
- •Кодирование графических данных
- •Кодирование звуковых данных
- •Послесловие к лекции о кодировании данных в компьютере
- •Хранение данных в компьютере
- •Представление и обработка числовой информации в компьютере
- •История развития вычислительной техники
- •Классификация эвм по принципу действия
- •Поколения цифровых эвм
- •Архитектура эвм
- •Архитектура эвм, построенная на принципах фон Неймана
- •Структура современных эвм
- •Тенденции в развитии структуры современных эвм
- •Упрощенная структурная схема ibm pc совместимого компьютера
- •Структура и виды команд
- •Состав машинных команд
- •Основной цикл работы компьютера
- •Обработка прерываний
- •Состав вычислительной системы
- •Аппаратное обеспечение
- •Программное обеспечение
- •Классификация программных продуктов по сфере использования
- •Системное программное обеспечение
- •Операционная система
- •Ос как расширенная машина
- •Ос как система управления ресурсами
- •Функции ос
- •Понятие многозадачности
- •Установка приложений
- •Удаление приложений
- •Обеспечение взаимодействия с аппаратным обеспечением
- •Обслуживание компьютера
- •Прочие функции операционных систем
- •Особенности файловых систем
- •Файловые системы fat и fat32
- •Файловая система ntfs
- •Физическая структура ntfs
- •Mft и его структура.
- •Основные понятия ос Windows
- •Моделирование как метод решения прикладных задач
- •Моделирование как метод познания
- •Материальные и информационные модели
- •Формализация модели
- •Математическое моделирование
- •Классификация математических моделей по цели моделирования
- •Компьютерное моделирование
- •Этапы и цели компьютерного математического моделирования
- •Понятие алгоритма и его свойства
- •Определение алгоритма на основе рекурсивных функций
- •Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)
- •Способы записи алгоритмов
- •Линейный алгоритм
- •Разветвляющийся алгоритм
- •Циклический алгоритм
- •Объекты алгоритма
- •Языки и системы программирования
- •Классификация языков программирования, их эволюция
- •Алгоритмические (процедурные) языки программирования
- •Декларативные (описательные) языки программирования
- •Объектно-ориентированные языки программирования
- •Языки создания сценариев (программирование для Интернета)
- •Языки программирования баз данных
- •Языки моделирования
- •Поколения языков программирования
- •Системы программирования и их компоненты
- •Архитектура программных систем
- •Технологии программирования
- •Основные этапы развития технологии программирования
- •Модули и их свойства
- •Нисходящая и восходящая разработка программного обеспечения
- •Структурное и «неструктурное» программирование
Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)
Алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».
Под «машиной» в данном случае подразумевается некоторый абстрактный, существующий лишь в воображении автомат.
В общем случае такая машина состоит из следующих частей:
из неограниченной в обе стороны информационной ленты, разделенной на ячейки, представляющей неограниченную память машины. В каждой ячейке можно хранить только один символ, в том числе и ноль;
из головки чтения/записи, вдоль которой может перемещаться лента;
управляющего устройства, которое в каждый рассматриваемый момент находится в некотором «состоянии». Устройство управления может находиться в некотором конечном числе состояний, если это состояние заключительное, машина заканчивает работу.
Такая машина может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным, или может изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной. Машина Тьюринга работает в произвольном конечном алфавите и выполняет некоторое конечное число приказов.
Машины Тьюринга представляют собой универсальных исполнителей, с использованием которых можно имитировать все алгоритмические процессы, описываемые математиками. Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций. Т.о. вопрос о существовании или не существовании алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или не существовании машины Тьюринга, обладающей нужным свойством.
Интуитивное понимание машины Тьюринга таково: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.
Способы записи алгоритмов
Существует несколько способов записи алгоритмов, отличающихся друг от друга наглядностью, компактностью, степенью формализации. Наибольшее распространение получили: словесный, графический, программный.
Графический способ записи предполагает использование определенных графических символов – блоков, каждый из которых обозначает определенный тип действия.
Каждый блок предписывает выполнение определенных действий. Совокупность блоков образует схему алгоритма или блок-схему.
Обозначение некоторых блоков в соответствии с ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ ДАННЫХ И СИСТЕМ
Наименование символа |
Обозначение символа |
Пояснение |
Процесс |
|
Арифметический блок, определяющий действия, которые необходимо выполнить |
Предопределенный процесс |
|
Обращение к подпрограмме |
Принятие решения |
|
Логический блок, проверяющий истинность или ложность некоторого условия |
Передача данных |
|
Ввод или вывод информации |
Прерывание |
|
Начало, конец, пуск, останов, вход в подпрограмму |
Модификация |
|
Организация циклического процесса при известном количестве повторений |
Граница цикла |
|
Начало и конец цикла. Условие помещают внутри символа в начале или конце в зависимости от расположения операции проверки условия |
Блоки соединяются линиями потока информации. Внутри блоков записываются выполняемые действия. Линии со стрелками определяют направление вычислений.
Практически любой сложный алгоритм можно представить собой комбинацией трех типов базовых структур: линейного, разветвляющегося и циклического.