МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

681.3 (07) П121

С. Т. Касюк

КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ «ИНФОРМАТИКА»

Учебное пособие для студентов кафедры автоматики и управления

Челябинск

2005

Министерство образования и науки Российской Федерации Южно-Уральский государственный университет Кафедра «Автоматика и управление»

681.3 (07) П121

С. Т. Касюк

КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ «ИНФОРМАТИКА»

Учебное пособие для студентов кафедры автоматики и управления

Одобрено учебно-методическим советом приборостроительного факультета

Челябинск

2005

УДК 004.4 ББК 32.965

АННОТАЦИЯ

Касюк С. Т. Конспект лекций по дисциплине «Информатика»: Учебное пособие для студентов кафедры автоматики и управления. — Челябинск: Из-во ЮУрГУ, 2005. — 212 с, ил.

Учебное пособие написано в соответствии с разработанной автором рабочей программой курса «Информатика» для обучения бакалавров и инженеров на кафедре автоматики и управления Южно-Уральского Государственного Университета по направлению подготовки 550200 — «Автоматизация управления».

Цель пособия состоит в поэтапном формировании у студентов знаний о методах составления программ и выработке навыков программирования на языке Си.

Весь материал разбит по главам, в которых приведены: 1) основные понятия информатики, 2) базовые конструкции и элементы стандарта ANSI языка программирования Си, 3) описание динамических информационных структур и 4) вопросы сортировки и поиска данных. Имеется много примеров программ на языке Си учебного и практического характеров.

Для удобства преподавателей и студентов приведена рабочая программа дисциплины и списки вопросов к зачету и экзамену.

Ил. 69, табл. 19, список лит. — 13 назв.

© Издательство ЮУрГУ, 2005.

ПРЕДИСЛОВИЕ

Вучебном пособии представлен конспект лекция по курсу «Информатика», который используется для подготовки бакалавров и инженеров по направлению 651900 — «Автоматизация и управление» на кафедре автоматики и управления Южно-Уральского государственного университета.

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

При изложении материала автор стремился учитывать, что пособие ориентировано на студентов младших курсов, начинающих изучать программирование «с нуля». По своему объему данных пособие приближается к учебникам по языку программирования Си для студентов, изучающих информатику и вычислительную технику. Однако оно отличается от них в основном менее подробным изложением материала, поскольку, по мнению автора, изучение разнообразных языковых конструкций и возможностей при начальном освоении программирования затеняет базовые понятия языка Си и «сбивает студентов с толку». Поскольку для учащихся практика программирования имеет огромное значение, в пособии приведено много примеров программ учебного и прикладного характеров, снабженных комментариями.

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

Впособии даны программные реализации стеков, списков, очередей и деревьев. Кроме того, приведены программы с использованием динамических информационных структур из книги Кернигана Б. и Ритчи Д. «Язык программирования Си». Раздел сортировки и поиска разработан несколько подробнее других разделов, так приведены прикладные алгоритмы обработки данных, примеры сортировки и поиска данных, расчетные характеристики алгоритмов.

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

Для удобства преподавателей и студентов в пособие включены рабочая программа дисциплины «Информатика» и списки вопросов к зачету (осенний семестр) и экзамену (весенний семестр).

Автор надеется, что полученные с помощью этого учебного пособия знания помогут студентам в дальнейшем при изучении языков Си++ и ассемблера и

3

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

* * *

Автор считает своим долгом выразить глубокую благодарность доценту Г. А. Поллак за предоставленные материалы по структурам данных, сортировке и поиску данных, а так же ассистенту Е. А. Канашеву за большую помощь, выразившуюся в просмотре и коррекции текстов программ. Ряд ценных указаний и материалов были предоставлены преподавателями Ю. И. Казьминой, А. Д. Чесноковым и С. А. Павловым, которым автор выражает свою большую признательность.

С. Т. Касюк Челябинск, 2005 г.

4

ГЛАВА 1. ОСНОВЫ ИНФОРМАТИКИ

§1.1. Предмет информатики. История информатики

Информатика — отрасль науки, изучающая структуру и общие свойства информации, а также вопросы, связанные с ее сбором, хранением, поиском, переработкой, преобразованием, распространением и использованием в различных сферах человеческой деятельности. Термин «информатика» используется в указанном смысле во многих языках. В английском языке имеется соответствующий термин «computer scince» (вычислительная наука).

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

Готфрид Вильгейм Лейбниц родился в 1646 году в Лейпциге в семье профессора философии и морали Лейпцигского университета. В пятнадцати лет Лейбниц начал изучать право в Лейпциге и в 1667 году получил ученую степень. Он занимается различными науками: философией, теологией, математикой, алхимией. В 1672 году Лейбница посылают в Париж — место встреч европейских ученых. Здесь созревают его первые грандиозные идеи: проект вычислительной машины и дифференциальное исчисление. К этому же периоду относятся его первые размышления о двоичной системе счисления и логическом исчислении. С 1678 года Лейбниц занимается универсальным символическим языком, как средством построения некой универсальной науки, которая в рамках одного исчисления позволяла бы давать ответы на все вопросы простейшим образом и со свойственной математике достоверностью. В своей работе «Об универсальной науке или философском исчислении» он пишет: «Тогда при возникновении спорных вопросов между двумя философами не будет больше надобности в научных дискуссиях, как нет её для двух специалистов-вычислителей. Достаточно будет взять в руки что-нибудь пишущее, сесть за вычислительное устройство и сказать друг другу (дружеским тоном, если угодно): давайте посчитаем».

Одновременно с теоретическими разработками Лейбниц выполняет несколько технических проектов. Он продолжает работать над созданием вычислительной машины, работающей в двоичной системе счисления. В 1694 году по проекту Лейбница изготавливается машина, выполняющая четыре арифметических действия, возведение в степень и извлечение корня. В 1712 году Лейбниц встретился с Петром I, для которого пытался построить третий экземпляр своей вычислительной машины. В 1716 году Лейбниц умирает.

Становление информатики как науки идет двумя взаимосвязанными путями: разработкой теоретической базы и совершенствованием технических средств.

5

Наиболее существенными достижениями теории, способствовавшими появлению и развитию информатики, обычно считают:

1.Формулировка принципа двоичного кодирования, создание теории кодирования и теории информации. Так, английский философ Френсис Бекон (1561 — 1626) первым понял, что для кодирования информации достаточно двух цифр и применил принцип двоичного кодирования для тайнописи. Его код был пятиразрядным, состоящим из букв А и В, и кодировал 24 буквы английского алфавита: а — «ААААА»; b — «AAAAB»; c — «AAABA»; d — «AAABB». Затем

вразвитии теории двоичного кодирования наблюдается некоторый «застой», который продолжается до второй половины 19 века, когда начинается интенсивное развитие средств связи (изобретение телеграфа, а затем радио).

В середине 20 века французский ученый Грей строит двоичный код, уменьшающий величину ошибки от воздействия помех, а американский ученый Ричард Хэмминг создает код, позволяющий исправлять ошибки. Существенно новое направление придал делу американский ученый Клод Шеннон. Исходя из своих исследований по криптографической надежности, выполненных во время второй мировой войны, он создал теорию информации, базирующуюся исключительно на статических предположениях об источнике сообщений. Шеннон установил также, какое количество информации можно передавать при наличии помех. Аналогичные результаты независимо от него в то же время получили Норберт Винер и советский математик Андрей Николаевич Колмогоров.

2.Создание логического исчисления (алгебры логики). Решающим шагом в создании логического исчисления стала разработка алгебры логики англичанином Джорджем Булем в 1847 г. Введение понятий логической переменной и логической функции, формулировка законов алгебры логики и разработка методов минимизации логических функций (работы Шеффера, Пирса, Карно) позволили впоследствии создать теорию цифровых автоматов, которые являются основной частью арифметико-логических устройств (АЛУ) современных микропроцессоров.

3.Разработка теории алгоритмов, алгоритмических языков и программирования. На протяжении веков термином «алгоритм» обозначали инструкцию, предписание, рецепт, правило, в соответствии с которым нужно чтото сделать. Поворотным пунктом в развитии теории алгоритмов стала формализация, то есть отказ от естественного языка с присущей ему неточностью и обращение к символьным языкам для описания алгоритмов и их объектов. Термин «алгоритмические языки» впервые ввел в обиход Боттенбурк в 1958 году. В это же время начинают создаваться алгоритмические языки с целью их применения для программирования ЭВМ. Первым существенным достижением в этой области стали Фортран и Алгол.

4.Формулировка принципов программного управления. В 1945 году американский математик Джон фон Нейман сформулировал принципы программного управления, которые используются в настоящее время при построении ЭВМ:

6

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

•Слова информация (данные и команды) размещаются в ячейках памяти и идентифицируются номерами ячеек, называемыми адресами слов.

Первые ЭВМ с программным управлением и хранимой в памяти программой появились практически одновременно в Англии, США и СССР. Однако их появлению предшествовал долгий исторический процесс

совершенствования технических средств вычислений.

Вот основные вехи этого пути:

•В 1642 году французский физик и математик Паскаль сконструировал машину, выполнявшую операции сложения и вычитания.

•В 1694 году Лейбниц создал машину, выполнявшую 4 арифметических действия, возведение в степень и извлечение корня.

•В 1820 году был разработан арифмометр.

•В конце 19 века появились первые электромеханические счетные машины. Однако, все эти устройства позволяли выполнять одну операцию над одним или двумя числами и не позволяли проводить сложные вычисления. Но еще в 1833 году профессор Кембриджского университета Ч. Бэббидж пришел к выводу о возможности построения машины, способной выполнить любые вычисления, заданные оператором. «Аналитическая машина» Бэббиджа состояла из «мельницы» и «склада». «Мельница» предназначалась для выполнения арифметических операций над числами, а «склад» для хранения чисел. Современными аналогами «мельницы» и «склада» машины Бэббиджа являются АЛУ и память ЭВМ. Для ввода чисел и управления процессором вычислений Бэббидж предполагал использовать перфокарты. При жизни Ч. Бэббиджа его машина не была построена. Прошло более 100 лет, прежде чем идея Бэббиджа была реализована.

•В 1942 году в Германии и позднее в США построили вычислительные машины на электромагнитных реле с управлением от программы.

•В конце сороковых годов в Англии, США и СССР практически одновременно были построены электронные вычислительные машины на лампах. Первая ЭВМ, построенная в нашей стране, называлась Малая Электронная Счетная Машина (МЭСМ). В 1952 — 54 г.г. была построена Быстродействующая Электронная Счетная Машина (БЭСМ), которая выполняла 8000 операций в секунду и являлась одной из самых быстродействующих машин в мире.

За прошедшее время сменилось несколько поколений ЭВМ. Поколения ЭВМ отличаются элементной базой и логической организацией:

•I поколение. Ламповые ЭВМ («Стрела», «Минск-1», «Урал-1,2»). Основной недостаток ЭВМ этого поколения — низкая надежность.

•II поколение. Полупроводниковые ЭВМ на дискретных элементах (конец 50-х годов — конец 60-х годов): «Минск-2, 22, 32», БЭСМ-4, «Мир». Производительность ЭВМ этого поколения достигала 1 млн. операций в секунду; надежность, хотя и оставляла желать лучшего, позволяла строить

7

автоматизированные системы управления производством и технологическими процессами.

•III поколение. ЭВМ на интегральных схемах (конец 60-х годов). Родоначальниками этого поколения стали: разработанная фирмой IBM система машин IBM-360 и миникомпьютер PDP-11 фирмы DEC. В нашей стране эти машины производились под именами Единая система ЭВМ (ЕС ЭВМ) и Система малых ЭВМ (СМ ЭВМ).

•IV поколение. ЭВМ на основе больших интегральных схем (БИС). Характеризуется наличием нескольких процессов. Быстродействие достигает сотен миллионов операций в секунду.

§1.2. Информация и сообщения. Дискретные сообщения. Обработка сообщений

Основными понятиями информатики являются информация и сообщение. В жизни они обычно отождествляются, однако информация и сообщение — не одно и то же. Эти понятия разграничены. Абстрактная информация передается посредством конкретного сообщения, а передача сообщения, в свою очередь, осуществляется с использованием какого-либо носителя.

Носители могут быть долговременные, недолговременные. Примерами долговременных носителей сообщения являются: письмо, газета, перфокарта, диск, кинопленка и т.д.; недолговременных носителей — электрические напряжения, токи, свободные электромагнитные волны (включая световые волны), волны давления в жидкостях и газах (включая звуковые волны). Недолговременными носителями, как правило, являются сигналы.

Сигнал — это изменение некоторой физической величины во времени, обеспечивающее передачу сообщения. Та характеристика сигнала, которая несет информацию в сообщении, называется параметром сигнала. Сигнал может быть непрерывным и дискретным. Если параметр сигнала изменяется непрерывно и может принимать множество значений, то сигнал называется непрерывным. Если же параметр сигнала принимает конечное число значений и существенен в конечном числе моментов времени, то сигнал называется дискретным. Сообщение называется дискретным, если оно передается с помощью дискретных сигналов. Дискретное сообщение представляется в виде некоторой последовательности знаков (для вычислительной техники — 0 и 1). Знак — это элемент некоторого конечного множества элементов, называемого набором знаков. Алфавит — это набор знаков, в котором определен их порядок.

Для информатики большое значение имеют наборы, состоящие из двух знаков — 0 и 1. Такие наборы называются двоичными наборами знаков, а сами знаки называются двоичными знаками.

Дискретные сообщения, как правило, разбивают на последовательности знаков. Это связано с физиологией чувств человека, а также с техническими соображениями. Конечной последовательностью двоичных знаков называется двоичное слово. Правило, которое описывает отображение одного набора знаков в

8

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

§1.3. Алгоритмы. Свойства алгоритмов. Схемы алгоритмов

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

Практически решение любой задачи можно представить в виде обработки сообщения типа «исходные данные» с целью получения сообщения типа «результат». Можно сказать, что алгоритм описывает процесс преобразования исходных данных в результат. Разработка алгоритма является важнейшим этапом решения любой задачи. Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги (этапы). При этом должно быть четко указано содержание каждого этапа и определена последовательность выполнения этих этапов. После разработки алгоритма его можно реализовать практически на любом языке программирования.

Основные свойства алгоритмов:

1.Дискретность. Алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых и заранее определенных этапов; каждый из этих этапов выполняется некоторый конечный отрезок времени. Иными словами, алгоритм должен отображать дискретность процесса преобразования исходных данных в результат.

2.Определенность (детерминированность). Каждое действие, указанное

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

3.Результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

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

Как представляется алгоритм? Сначала фиксируется в виде схемы, а затем переводится на алгоритмические языки, то есть представляется в виде программы.

Полный перечень правил и условных обозначений для изображения схем алгоритмов приведен в ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем» (см. табл. 1.3.1).

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

Схема программы отображает последовательность операций в программе. Схема состоит:

9

•из символов процесса, указывающих фактические операции обработки данных;

•из линейных символов со стрелками-указателями, указывающих поток данных;

•из специальных символов, используемых для облегчения написания и чтения схем.

Таблица 1.3.1

Типовые действия, наиболее часто встречающиеся в схемах программ

1. Вычисление, функция обработки данных любого вида (символ «процесс»).

2. Вызов функции (символ «предопределенный процесс»).

3.Начало или конец программы (символ «терминатор»).

4.Ввод данных вручную во время обработки с устройств любого типа (символ «ручной ввод»).

5.Вывод информации на видеомонитор в человекочитаемой форме (символ «дисплей»).

6.Проверка условия — функция переключательного типа,

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

10

Продолжение табл. 1.3.1

7. Вычисление в цикле (символ «граница цикла»). Символ состоит из двух частей, между которыми находится тело цикла).Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие.

8. Комментарии к алгоритму (символ «комментарий»). Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. Пунктирные линии связаны с соответствующим символом или могут обводить группу символов.

9. Обрыв линий, выход в часть схемы и вход из другой части этой схемы (символ «соединитель»).

10. Поток данных (символ «линия»). Символ отображает поток данных. При

необходимости или повышения —— удобочитаемости могут быть добавлены стрелки-указатели.

Пример. Разработать схему программы вычисления произведения двух натуральных чисел n и m с использованием операции сложения. Произведение — k. (Схема приведена на рис. 1.3.1.)

11

Таблица 1.3.2

Основные структуры алгоритмов

1.Следование — последовательное размещение символов (блоков) или группы символов.

2. Цикл с постусловием — цикл «до». Цикл всегда выполняется хотя бы один раз. Проверка условия выхода из цикла происходит после того, как тело цикла выполнено. (Тело цикла — та последовательность действий, которая выполняется многократно.)

13

Продолжение табл. 1.3.2

3.Цикл с предусловием — цикл «пока». Проверка условия производится перед выполнением тела цикла. Если при первой проверке условие выхода выполняется, то само тело цикла не будет выполнено ни разу. Тело цикла выполняется до тех пор, пока не будет выполнено условие выхода из цикла.

4.Разветвление. Применяется, когда в зависимости от условия выполняется либо одно, либо другое действие. Действия могут содержать несколько этапов (символов).

14

Продолжение табл. 1.3.2

5. Обход — частный случай разветвления, когда одна ветвь не содержит никаких действий.

6. Множественный выбор — результат обобщения разветвления, когда в зависимости от значения некоторой переменной выполняется одно из нескольких действий.

15

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

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

Разработка алгоритма методом пошаговой детализации. Первоначально продумывается и фиксируется общая структура алгоритма без детальной разработки отдельных его частей. Блоки, которые требуют дальнейшей детализации, как-то выделяются (например, пунктирной линией). Далее прорабатываются отдельные блоки, которые не были детализированы на предыдущем шаге. После детализации всех блоков будет сформирован окончательный алгоритм. Метод пошаговой детализации называется также программированием «сверху-вниз».

16