Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Тульский государственный университет
Кафедра прикладной математики и информатики
ИНФОРМАТИКА
Конспект лекций для студентов
Направления: 010500 - Прикладная математика и информатика
специальности: 010501 - Прикладная математика
очной формы обучения
Тула 2005
Разработал М.Б.Кривоногов, канд. техн. наук, доцент.
Лекция 1
Введение
Широкое внедрение вычислительных машин, информатики, компьютерных технологий в жизнь и профессиональную деятельность современного человека требует от него определенных знаний по информатике.
Понятие информации определяется как “знания получаемые в процессе чтения, наблюдения, изучения…”. В кибернетике понятие информация определяется как “новые знания об объекте управления, позволяющие вырабатывать управленческие решения, как мера устранения неопределенности в управленческой системе, как упорядоченное отражение действительности”. Применительно к вычислительным наукам понятие информация определяется как “сведения, представленные в символьной форме”.
Таким образом, текст книги, научные данные и формулы, сальдо, поступления и выплаты по банковскому счету, тарифы и сроки платежей, расписание занятий, сообщения радиолокационных станций являются видами информации.
Следует отличать понятие “информация” от понятия “данные”. Всякое информационное сообщение несет в себе сведения об управляемом объекте, то есть данные о нем, но не всякое сообщение требует управленческих воздействий, то есть оно не обязательно содержит новые знания - информацию.
Процесс наблюдения и отражения реальной действительности представляет собой непрерывное или дискретное получение многочисленных данных о наблюдаемом объекте. Чтобы из этого множества данных получить необходимую для управления информацию, поток данных необходимо обработать по специальному алгоритму.
В настоящее время рост потоков информации во всех областях человеческой деятельности так велик, что его часто называют информационным взрывом. В огромном объеме разнообразных сведений очень трудно, а порой невозможно разобраться, отличить нужное от ненужного, найти то, что требуется. Все это приводит к большим потерям времени, финансов и прочих ресурсов.
Необходимость в регистрации, обработке, передаче и хранении больших объемов информации, представленной числовыми, символьными, зрительными, речевыми и другими данными, с высокими скоростями потребовала создания помощников человеку в этих вопросах.
Такими помощниками и являются современные ЭВМ. Наука, исследующая законы и методы обработки, накопления и передачи информации с помощью ЭВМ называется информатикой.
До недавнего времени вычислительные машины обрабатывали только цифровые данные и свое название – ЭВМ (компьютер) – унаследовали от профессии “большого арифмометра”. В связи с этим языки для описания алгоритмов обработки данных (языки программирования) были ориентированы на создание математических моделей в физике, механике, экономике, управлении и т. д.
Способность современных компьютеров обрабатывать символьные данные составляет основу всех видов коммуникационных отношений между людьми. Символы или знаки в зрительной, звуковой или других формах общения образуют естественные языки и языки точных наук. Именно способность ЭВМ обрабатывать данные в символьной форме явилась одной из предпосылок того, чтобы говорить об искусственном интеллекте как о свойстве вычислительных машин и их программ решать задачи, традиционно считавшиеся интеллектуальными.
Таким образом, была открыта новая область применения компьютеров – возможность их включения в коммуникационные отношения между людьми в качестве инструментов повышения интеллектуальной деятельности, способных анализировать и синтезировать тексты и речь, распознавать зрительные образы и сцены и соответствующим образом реагировать на них.
Способность ЭВМ анализировать и синтезировать тексты и речь определяет новый стиль применения вычислительной техники, когда она используется лицами принимающими решения с помощью ЭВМ, без посредничества программистов.
Эффективная эксплуатация современных ЭВМ немыслима без оснащения их комплексами специальных программ, облегчающих процесс подготовки задач к решению и организующих прохождение этих задач через машину. Комплекс таких программ принято называть программным обеспечением вычислительной системы. Возможности ЭВМ определяются уровнем развития теории и техники программирования, а также быстродействием процессора и емкостью памяти машины.
Лекция 2
Понятие алгоритма является основным при составлении любого вида программ для ЭВМ. Алгоритм – точно определенное правило действий (программа), для которого задано указание, как и в какой последовательности, это правило необходимо применить к исходным данным задачи, чтобы получить ее решение.
Примером алгоритма может служить правило нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Даны два целых положительных числа m и n. Требуется найти их наибольший общий делитель, то есть наибольшее положительное целое число, которое нацело делит как m, так и n.
1 шаг (нахождение остатка). Разделим m на n. Пусть остаток равен r. Имеем 0 £ r < n.
2 шаг (это нуль?). Если r = 0, то алгоритм заканчивается; n – искомое число.
3 шаг (замена). Положите m ¬ n, n ¬ r и возвращайтесь к шагу 1.
Формула для нахождения корней квадратного уравнения также является своеобразной формой записи алгоритма. Она указывает, какие арифметические действия и в какой последовательности нужно производить над коэффициентами квадратного уравнения, чтобы получить корни этого уравнения.
Теория алгоритмов - раздел математики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения. Теория алгоритмов является в настоящее время важным и быстроразвивающимся разделом математической логики. Интерес к ней объясняется, с одной стороны, внутренними интересами самой математики (алгоритмические проблемы алгебры, вопросы оснований математики и т.п.), а, с другой - бурным развитием электронной вычислительной техники и теоретической кибернетики. Практические и теоретические вопросы реализации алгоритмов на современных вычислительных машинах являются содержанием такого важного раздела теоретической кибернетики, как программирование.
Точные математические понятия, которые в том или ином смысле формализовали интуитивное понятие алгоритма, предложены только в середине 30-х годов нашего столетия. Исторически первые из предложенных понятий можно разделить на два вида.
1. Описывается некоторый класс арифметических функций (вообще говоря, частных), то есть функций от конечного числа натуральных аргументов с натуральными значениями. Эти функции обладают некоторыми эффективными процедурами нахождения значения функции (если оно существует) по заданным значениям аргументов. Функции из этого класса называются частично рекурсивными (ч.р.ф.), а в случае, если ч.р.ф. всюду определены, их называют общерекурсивными.
2. Описываются точные математические понятия машины и вычислимости на машине. Такие понятия машины и вычислимости на машине предложили независимо один от другого Э.Пост и А.Тьюринг. Эти "теоретические вычислительные машины" обычно называют машинами Тьюринга. Оказалось, что класс арифметических функций, для которых существует машина Тьюринга, вычисляющая по значениям аргументов значение функции (если оно существует), совпадает с классом всех ч.р.ф. и наоборот, каждая ч.р.ф. вычислима на подходящей машине Тьюринга.
В общих чертах различие между двумя рассмотренными выше видами определений можно сформулировать так: в первом дается точное описание класса вычислимых арифметических функций, во втором - точное описание некоторого класса алгоритмических преобразований (вычислений на машине Тьюринга).
Процесс выполнения алгоритма называется алгоритмическим процессом. Для некоторых исходных данных он заканчивается получением искомого результата после конечного числа шагов. Однако допускаются случаи, в которых процесс выполнения алгоритма для некоторых исходных данных безрезультативно обрывается или продолжается неограниченно. Принято считать, что к этим исходным данным алгоритм не применим. Понятие алгоритма тесно связано с понятием "алгоритмический язык" (на котором задан алгоритм) и понятием "правило выполнения алгоритма" при заданных для него исходных данных. Алгоритмический язык и правило выполнения алгоритма (которое по существу само является алгоритмом и его можно назвать "алгоритмом выполнения алгоритма") естественным образом выделяют определенное семейство алгоритмов.
Каждая детерминированная вычислительная машина является автоматом, действия которого можно описать в виде некоторого алгоритма. Такой алгоритм является алгоритмом выполнения программ указанной вычислительной машины. Сами программы можно рассматривать как некоторый класс алгоритмов. При этом алгоритмическим языком является система команд вычислительной машины.
Алгоритмический язык - формальный язык, предназначенный для записи алгоритмов. Использование алгоритмического языка основано на возможности формального задания правил конструирования алгоритмов. При формальном описании алгоритмов существенная роль принадлежит выбору способа записи (кодирования) перерабатываемой информации и задания алгоритмических предписаний - элементарных шагов алгоритма, из которых он конструируется. Алгоритмический язык определяется заданием алфавита (или словаря исходных символов), точным описанием его синтаксиса (грамматики) и семантики.