А. В. Цветкова Информатика и информационные технологии. Конспект лекций

А. В. Цветкова Информатика и информационные технологии. Конспект лекций Издательство: Эксмо, 2007 г.; 192 стр. Конспект   лекций   соответствует   требованиям   Государственного   образовательного стандарта высшего профессионального образования РФ и предназначен для освоения студентами вузов специальной дисциплины "Информатика и информационные технологии". Лаконичное и четкое   изложение   материала,   продуманный   отбор   необходимых   тем   позволяют   быстро   и качественно подготовиться к семинарам, зачетам и экзаменам по данному предмету. Оглавление ЛЕКЦИЯ № 1. Введение в информатику    1. Информатика. Информация. Представление и обработка информации    2. Системы счисления    3. Представление чисел в ЭВМ    4. Формализованное понятие алгоритма  ЛЕКЦИЯ № 2. Язык Pascal    1. Введение в язык Pascal    2. Стандартные процедуры и функции    3. Операторы языка Pascal  ЛЕКЦИЯ № 3. Процедуры и функции    1. Понятие вспомогательного алгоритма    2. Процедуры в Pascal    3. Функции в Pascal    4. Опережающие описания и подключение подпрограмм. Директива  ЛЕКЦИЯ № 4. Подпрограммы    1. Параметры подпрограмм    2. Типы параметров подпрограмм  ЛЕКЦИЯ № 5. Строковый тип данных    1. Строковый тип в Pascal    2. Процедуры и функции для переменных строкового типа    3. Записи    4. Множества  ЛЕКЦИЯ № 6. Файлы    1. Файлы. Операции с файлами    2. Модули. Виды модулей  ЛЕКЦИЯ № 7. Динамическая память    1. Ссылочный тип данных. Динамическая память. Динамические переменные    2. Работа с динамической памятью. Нетипизированные указатели  ЛЕКЦИЯ № 8. Абстрактные структуры данных    1. Абстрактные структуры данных    2. Стеки    3. Очереди  ЛЕКЦИЯ № 9. Древовидные структуры данных    1. Древовидные структуры данных    2. Операции над деревьями    3. Примеры реализации операций  ЛЕКЦИЯ № 10. Графы 1. Понятие графа. Способы представления графа    2. Представление графа списком инцидентности. Алгоритм обхода графа в глубину    3. Представление графа списком списков. Алгоритм обхода графа в ширину  ЛЕКЦИЯ № 11. Объектный тип данных    1. Объектный тип в Pascal. Понятие объекта, его описание и использование    2. Наследование    3. Создание экземпляров объектов    4. Компоненты и область действия  ЛЕКЦИЯ № 12. Методы    1. Методы    2. Конструкторы и деструкторы    3. Деструкторы    4. Виртуальные методы    5. Поля данных объекта и формальные параметры метода  ЛЕКЦИЯ № 13. Совместимость типов объектов    1. Инкапсуляция    2. Расширяющиеся объекты    3. Совместимость типов объектов  ЛЕКЦИЯ № 14. Ассемблер    1. Об ассемблере    2. Программная модель микропроцессора    3. Пользовательские регистры    4. Регистры общего назначения    5. Сегментные регистры    6. Регистры состояния и управления  ЛЕКЦИЯ № 15. Регистры    1. Системные регистры микропроцессора    2. Регистры управления    3. Регистры системных адресов    4. Регистры отладки  ЛЕКЦИЯ № 16. Программы на Ассемблере    1. Структура программы на ассемблере    2. Синтаксис ассемблера    3. Директивы сегментации  ЛЕКЦИЯ № 17. Структуры команд на Ассемблере    1. Структура машинной команды    2. Способы задания операндов команды    3. Способы адресации  ЛЕКЦИЯ № 18. Команды    1. Команды пересылки данных    2. Арифметические команды ЛЕКЦИЯ № 19. Команды передачи управления    1. Логические команды    2. Команды передачи управления ЛЕКЦИЯ № 1. Введение в информатику 1. Информатика. Информация. Представление и обработка информации  Информатика   занимается   формализованным   представлением   объектов   и   структур   их взаимосвязей в различных областях науки, техники, производства. Для моделирования объектов и   явлений   используются   различные   формальные   средства,   например   логические   формулы, структуры данных, языки программирования и др. В информатике такое фундаментальное понятие, как информация имеет различные значения: 1) формальное представление внешних форм информации; 2) абстрактное значение информации, ее внутреннее содержание, семантика; 3) отношение информации к реальному миру. Но,   как   правило,   под   информацией   понимают   ее   абстрактное   значение   –  семантику. Интерпретируя представления информации, мы получим ее смысл, семантику. Поэтому, если мы хотим   обмениваться   информацией,   нам   необходимы   согласованные   представления,   чтобы  не нарушалась правильность интерпретации. Для этого интерпретацию представления информации отождествляют   с   некоторыми   математическими   структурами.   В   этом   случае   обработка информации может быть выполнена строгими математическими методами. Одно из математических описаний информации – это представление ее в виде функции  у =f(x,   t),  где  t   –  время,  х   –  точка   некоторого   поля,   в   которой   измеряется   значение  у.  В зависимости от параметров функции хи(информацию можно классифицировать. Если   параметры   –   скалярные   величины,   принимающие   непрерывный   ряд   значений,   то полученная   таким   образом   информация   называется   непрерывной   (или  аналоговой).  Если   же параметрам   придать   некоторый   шаг   изменений,   то   информация   называется  дискретной. Дискретная информация считается универсальной, так как для каждых конкретных параметров можно получить значение функции с заданной степенью точности. Дискретную   информацию   обычно   отождествляют   с  цифровой  информацией,   которая является   частным   случаем   символьной   информации   алфавитного   представления.   Алфавит   – конечный   набор символов  любой  природы.   Очень  часто в  информатике  возникает   ситуация, когда символы одного алфавита надо представить символами другого, т. е. провести операцию кодирования.  Если количество символов кодируемого алфавита меньше количества символов кодирующего   алфавита,   то   сама   операция   кодирования   не   является   сложной,   в   противном случае необходимо использовать фиксированный набор символов кодирующего алфавита для однозначного правильного кодирования. Как   показала   практика,   наиболее   простым   алфавитом,   позволяющим   кодировать   другие алфавиты,   является   двоичный,   состоящий   из   двух   символов,   которые   обозначаются,   как правило,   через   О   и   1.   С   помощью   n   символов   двоичного   алфавита   можно   закодировать   2п символов, а этого достаточно, чтобы закодировать любой алфавит. Величина,   которая   может   быть   представлена   символом   двоичного   алфавита,   называется минимальной единицей информации или битом. Последовательность из 8 бит – байт. Алфавит, содержащий 256 различных 8­битных последовательностей, называется байтовым. В   качестве   стандартного   сегодня   в   информатике   принят   код,   в   котором   каждый   символ кодируется 1 байтом. Существуют и другие алфавиты. 2. Системы счисления  Под   системой   счисления   подразумевается   набор   правил   наименования   и   записи   чисел. Различают позиционные и непозиционные системы счисления. Система   счисления   называется  позиционной,  если   значение   цифры   числа   зависит   от местоположения цифры в числе. В противном случае она называется  непозиционной.  Значение числа определяется по положению этих цифр в числе. 3. Представление чисел в ЭВМ  32­разрядные процессоры могут работать с оперативной памятью емкостью до 232­1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220­1, а адреса попадают в диапазон 00000 – FFFFF. Байты памяти могут объединяться в поля как фиксированной, так и переменной длины. Словом называется поле фиксированной длины, состоящее из 2 байтов, двойным словом – поле из 4 байтов. Адреса полей бывают четные и нечетные, при этом для четных адресов операции выполняются быстрее. Числа   с   фиксированной   точкой   в   ЭВМ   представляются   как   целые   двоичные   числа,   и занимаемый ими объем может составлять 1, 2 или 4 байта. Целые   двоичные   числа   представляются   в   дополнительном   коде,   соответственно   числа   с фиксированной точкой представляются в дополнительном коде. При этом если число занимает 2 байта, то структура числа записывается по следующему правилу: старший разряд отводится под знак числа, а остальные – под двоичные цифры числа. Дополнительный код положительного числа равен самому числу, а дополнительный код отрицательного числа может быть получен по такой формуле: х = 10и – \х\, где n – разрядность числа. В двоичной системе счисления дополнительный код получается путем инверсии разрядов, т. е., заменой единиц нулями и наоборот, и прибавлением единицы к младшему разряду. Количество   битов   мантиссы   определяет   точность   представления   чисел,   количество   битов машинного порядка определяет диапазон представления чисел с плавающей точкой. 4. Формализованное понятие алгоритма  Алгоритм   может   существовать   только   тогда,   когда   в   то   же   самое   время   существует некоторый математический объект. Формализованное понятие алгоритма связано с понятием рекурсивных функций, нормальных алгоритмов Маркова, машин Тьюринга. В   математике   функция   называется   однозначной,   если   для   любого   набора   аргументов существует закон, по которому определяется единственное значение функции. В качестве такого закона может выступать алгоритм; в этом случае функция называется вычислимой. Рекурсивные  функции  – это подкласс  вычислимых  функций,  а алгоритмы,  определяющие вычисления,   называются  сопутствующими   алгоритмами  рекурсивных   функций.   Сначала фиксируются базовые рекурсивные функции, для которых сопутствующий алгоритм тривиален, однозначен; затем вводятся три правила – операторы  подстановки, рекурсии  и  минимизации, при   помощи   которых   на   основе   базовых   функций   получаются   более   сложные   рекурсивные функции. Базовыми функциями и их сопутствующими алгоритмами могут выступать: 1) функция n   независимых   переменных,   тождественно   равная   нулю.   Тогда,   если   знаком функции   является   n,   то   независимо   от   количества   аргументов   значение   функции   следует положить равным нулю; φ ψ λ ψ 2) тождественная функция n независимых переменных вида  ni. Тогда, если знаком функции является   ni,   то   значением   функции   следует   взять   значение   i­го   аргумента,   считая   слева направо; Λ , то значением функции следует взять значение, следующее за значением аргумента. Разные ученые предлагали свои подходы к формализованному  – функция одного независимого аргумента. Тогда, если знаком функции является  3) представлению  алгоритма. Например, американский  ученый Черч предположил,  что класс вычислимых функций исчерпывается рекурсивными функциями и, как следствие, каким бы ни был алгоритм, перерабатывающий один набор целых неотрицательных чисел в другой, найдется алгоритм, сопутствующий рекурсивной функции, эквивалентный данному. Следовательно, если для решения некоторой поставленной задачи нельзя построить рекурсивную функцию, то и не существует алгоритма для ее решения. Другой ученый, Тьюринг, разработал виртуальную ЭВМ, которая перерабатывала входную последовательность символов в выходную. В связи с этим им был выдвинут тезис, что любая вычислимая функция вычислима по Тьюрингу. ЛЕКЦИЯ № 2. Язык Pascal 1. Введение в язык Pascal  Основные символы языка – буквы, цифры и специальные символы – составляют его алфавит. Язык Pascal включает следующий набор основных символов: 1) 26 латинских строчных и 26 латинских прописных букв: ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz; 2) _ (знак подчеркивания); 3) 10 цифр: 0123456789; 4) знаки операций: + – х / = <> < > <= >= := @; 5) ограничители: . , ' ( ) [ ] (. .) { } (* *) .. : ; 6) спецификаторы: ^ # $; 7) служебные (зарезервированные) слова: ABSOLUTE, ASSEMBLER, AND, ARRAY, ASM, BEGIN, CASE, CONST, CONSTRUCTOR, DESTRUCTOR, DIV, DO, DOWNTO, ELSE, END, EXPORT, EXTERNAL, FAR, FILE, FOR, FORWARD, FUNCTION, GOTO, IF, IMPLEMENTATION, IN, INDEX, INHERITED, INLINE, INTERFACE, INTERRUPT, LABEL, LIBRARY, MOD, NAME, NIL, NEAR, NOT, OBJECT, OF, OR, PACKED, PRIVATE, PROCEDURE, PROGRAM, PUBLIC, RECORD, REPEAT, RESIDENT, SET, SHL, SHR, STRING, THEN, TO, TYPE, UNIT, UNTIL, USES, VAR, VIRTUAL, WHILE, WITH, XOR. Кроме   перечисленных,   в   набор   основных   символов   входит   пробел.   Пробелы   нельзя использовать внутри сдвоенных символов и зарезервированных слов. Концепция типа для данных В математике принято классифицировать переменные в соответствии с некоторыми важными характеристиками. Производится строгое разграничение между вещественными, комплексными и   логическими   переменными,   между   переменными,   представляющими   отдельные   значения   и множество значений, и т. д. При обработке данных на ЭВМ такая классификация еще более важна. В любом алгоритмическом языке каждая константа, переменная, выражение или функция бывают определенного типа. В языке Pascal существует правило: тип явно задается в описании переменной или функции, которое   предшествует   их   использованию.   Концепция   типа   языка   Pascal   имеет   следующие основные свойства: 1) любой тип данных определяет множество значений, к которому принадлежит константа, которые   может   принимать   переменная   или   выражение   либо   вырабатывать   операция   или функция; 2) тип значения, задаваемого константой, переменной или выражением, можно определить по их виду или описанию; 3) каждая   операция   или   функция   требуют   аргументов   фиксированного   типа   и   выдают результат фиксированного типа. Отсюда   следует,   что  транслятор   может   использовать   информацию   о   типах  для   проверки вычислимости и правильности различных конструкций. Тип определяет: 1) возможные   значения   переменных,   констант,   функций,   выражений,   принадлежащих   к данному типу; 2) внутреннюю форму представления данных в ЭВМ; 3) операции   и   функции,   которые   могут   выполняться   над   величинами,   принадлежащими   к данному типу. Следует   заметить,   что   обязательное   описание   типа   приводит   к   избыточности   в   тексте программ,   но   такая   избыточность   является   важным   вспомогательным   средством   разработки программ и рассматривается как необходимое свойство современных алгоритмических языков высокого уровня. В языке Pascal существуют скалярные и структурированные типы данных. К скалярным типам относятся стандартные типы и типы, определяемые пользователем. Стандартные типы включают целые, действительные, символьный, логические и адресный типы. Целые типы определяют константы, переменные и функции, значения которых реализуются множеством целых чисел, допустимых в данной ЭВМ. Действительные   типы   определяет   те   данные,   которые   реализуются   подмножеством действительных чисел, допустимых в данной ЭВМ. Типы, определяемые пользователем, – перечисляемый и интервальный. Структурированные типы имеют четыре разновидности: массивы, множества, записи и файлы. Кроме перечисленных, Pascal включает еще два типа – процедурный и объектный. Выражение языка состоит из констант, переменных, указателей функций, знаков операций и скобок.   Выражение   задает   правило   вычисления   некоторого   значения.   Порядок   вычисления определяется   старшинством   (приоритетом)   содержащихся   в   нем   операций.   В   языке   Pascal принят следующий приоритет операций: 1) вычисления в круглых скобках; 2) вычисления значений функций; 3) унарные операции; 4) операции *, /, div, mod, and; 5) операции +, —, or, xor; 6) операции отношения =, <>, <, >, <=, >=. Выражения входят в состав многих операторов языка Pascal, – также могут быть аргументами встроенных функций. 2. Стандартные процедуры и функции  Арифметические функции 1. Function Abs(X); Возвращает абсолютное значение параметра. X – выражение вещественного или целочисленного типа. 2. Function ArcTan(X: Extended): Extended; Возвращает арктангенс аргумента. X – выражение вещественного или целочисленного типа. 3. Function Ехр(Х: Real): Real; Возвращает экспоненту. X – выражение вещественного или целочисленного типа. 4. Function Frac(X: Real): Real; Возвращает дробную часть аргумента. X – выражение вещественного типа. Результат – дробная часть X, т. е. Frac (X) = X–Int (X). 5. Function Int(X: Real): Real; Возвращает целочисленную часть аргумента. X – выражение вещественного типа. Результат – целочисленная часть X, т. е. X, округленный к нулю. 6. Function Ln(X: Real): Real; Возвращает натуральный логарифм (Ln е = 1) выражения X вещественного типа. 7. Function Pi: Extended; Возвращает значение Pi, которое определено как 3.1415926535. 8. Function Sin(X: Extended): Extended; Возвращает синус аргумента. X – выражение вещественного типа. Sin возвращает синус угла X в радианах. 9. Function Sqr(X: Extended): Extended; Возвращает квадрат аргумента. X – выражение с плавающей запятой. Результат того же самого типа, что и X. 10. Function Sqrt(X: Extended): Extended; Возвращает квадратный корень аргумента. X – выражение с плавающей запятой. Результат – квадратный корень X. Процедуры и функции преобразования величин 1. Procedure Str(X [: Width [: Decimals]]; var S); Преобразовывает число X в строковое представление согласно Width и параметрам форматирования Decimals. X – выражение вещественного или целого типа. Width и Decimals – выражения целого типа. S – переменная типа String или символьный массив с нулевым окончанием, если допускается расширенный синтаксис. 2. Function Chr(X: Byte): Char; Возвращает символ с порядковым номером X в ASCII­таблице. 3. Function High(X); Возвращает наибольшее значение в диапазоне параметра. 4. Function Low(X); Возвращает наименьшее значение в диапазоне параметра. 5. Function Ord(X): Longint; Возвращает   порядковое   значение   выражения   перечислимого   типа.  X   –  выражение перечислимого типа. 6. Function Round(X: Extended): Longint; Округляет   значение   вещественного   типа   до   целого.   X   –   выражение   вещественного   типа. Round возвращает значение Longint, которое является значением X, округленным до ближайшего целого числа. Если X находится точно посередине между двумя целыми числами, возвращается число с наибольшей абсолютной величиной. Если округленное значение X выходит за диапазон Longint, генерируется ошибка времени выполнения программы, которую вы можете обработать с использованием исключительной ситуации EInvalidOp. 7. Function Trunc(X: Extended): Longint; Усекает значение вещественного типа до целого. Если округленное значение X выходит за диапазон Longint, генерируется ошибка времени выполнения программы, которую вы можете обработать с использованием исключительной ситуации EInvalidOp. 8. Procedure Val(S; var V; var Code: Integer); Преобразовывает число из строкового значения S в числовое представление V. S – выражение строкового типа – последовательность символов, которая формирует целое или вещественное число. Если выражение S недопустимо, индекс неверного символа сохраняется в переменной Code. В противном случае Code устанавливается в нуль. Процедуры и функции работы с порядковыми величинами 1. Procedure Dec(varX [; N: Longlnt]); Вычитает единицу или N из переменной X. Dec(X) соответствует X:= X – 1, и Dec(X, N) соответствует X:= X – N. X – переменная перечислимого типа или типа PChar, если допускается расширенный   синтаксис,   и   N   –   выражение   целочисленного   типа.   Процедура   Dec   генерирует оптимальный код и особенно полезна в длительных циклах. 2. Procedure Inc(varX [; N: Longlnt]); Прибавляет единицу или N к переменной X. X – переменная перечислимого типа или типа PChar, если допускается расширенный синтаксис, и N – выражение целочисленного типа. Inc (X) соответствует   инструкции   X:=   X   +   1,   и   Inc   (X,   N)   соответствует   инструкции   X:=   X   +   N. Процедура Inc генерирует оптимальный код и особенно полезна в длительных циклах. 3. Function Odd(X: Longlnt): Boolean; Возвращает True, если X – нечетное число, и False – в противном случае.