Конспект лекций по дисциплине информатика для студентов заочного отделения

Вид материала

Конспект

Содержание 8. Базовые понятия алгоритмизации задач и программирования Порции этой информации Размеры ячеек памяти Запись – это совокупность переменных разного типа Языки машинных команд Языки Ассемблера Языки высокого уровня

Подобный материал:

• Краткий конспект лекций по дисциплине «Основы лесоводства и лесной таксации» Для студентов, 923.35kb.
• Конспект лекций Для специальности -100100 з/о сокращенной формы обучения Киров 2002, 1277.87kb.
• Учебно-методический комплекс по дисциплине «теория и методика преподавания информатики», 378.57kb.
• Методические указания по выполнению контрольной работы №2 по дисциплине Информатика, 278.17kb.
• Опорный конспект лекций и методические указания для выполнения контрольной работы для, 931.78kb.
• Методические указания и вопросы контрольной работы По дисциплине «Средства измерения, 313.48kb.
• Методические указания по выполнению контрольной работы №1 по дисциплине Информатика, 390.61kb.
• Конспект лекций по разделу "Трехфазные цепи", 122.38kb.
• Конспект лекций по курсу "Информатика и использование компьютерных технологий в образовании", 1797.24kb.
• Конспект лекций для студентов по специальности i-25 01 08 «Бухгалтерский учет, анализ, 2183.7kb.

8. Базовые понятия алгоритмизации задач и программирования

Понятие данных

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

Например, с задачей:

«Вычислить площадь S треугольника с длинами сторон A, B, C по формуле Герона , где - полупериметр» связаны следующие данные: A, B, C, P, 2 и S.

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

Ячейки памяти

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

Основная память

0000

0001 байты памяти с их номерами

0002

.

.

.

000N

Байт памяти представляет собой наименьшую адресуемую ячейку памяти. Он состоит из 8 двоичных разрядов, называемых битами, которые нумеруются от 0 до 7


Байт памяти

биты

0 1 2 3 4 5 6 7 номера бит


Каждый бит памяти может хранить 0 или 1. Различные комбинации этих значений в ячейках памяти и используются для кодирования данных, например, код числа 5 в ячейке памяти, длиной в 1 байт имеет вид:

0 0 0 0 0 1 0 1

Размеры ячеек памяти

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




Ячейка памяти длиной в 1 байт




Ячейка памяти длиной в 2 байта







Длина ячейки памяти (количество байт в ячейке) зависит от типа хранящегося в ней данного. Наиболее часто используются ячейки памяти длиной в 1, 2, 4, 6, 8 и 10 байт.

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


Классы данных

Принято выделять следующие два основных класса данных:

1. константы;
   
2. переменные.
   

Переменные (но не константы) в свою очередь подразделяются на три подкласса:

• исходные данные;
  
• промежуточные данные;
  
• результирующие данные (или результаты).
  

Константы – это данные, значения которых при решении задачи не меняются. Константе в оперативной памяти компьютера выделяется ячейка, в которой хранится одно и то же значение.

В нашем примере (смотри выше) – это величина 2.

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

В нашем примере переменные – это A, B, C, P, S.

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

В нашем примере исходными данными являются переменные: A, B, C. Смысл: нельзя вычислить площадь треугольника, не зная длин его сторон.

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

В нашем примере – это переменная P, которая используется для вычисления значения полупериметра. Смысл: сначала следует вычислить полупериметр, а затем – площадь.

Результирующие данные (результаты) – это переменные, которым должны быть присвоены искомые значения. Эти значения затем выводятся пользователю из памяти компьютера посредством одного из устройств вывода, например, на экран монитора или на бумагу.

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


Типы данных

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

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

• данные целого типа (целые числа вида: 5; -135; 0; +15 и т.п.);
  
• данные вещественного типа (десятичные дроби: 3.75; 5.0; -0.25 и т.п.);
  
• данные логического типа (имеют всего два значения: истина и ложь);
  
• данные символьного типа (одиночные символы: буквы, цифры и другие знаки, например, ‘A’; ‘5’; ‘+’);
  
• данные строкового типа (последовательности символов, например, ‘Результат Y=’; ‘Ошибка A < B’).
  

Над данными первых двух типов можно выполнять арифметические операции и операции сравнения. Для данных третьего типа используются специальные логические операции И, ИЛИ, НЕ.

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


Структуры данных

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

Как правило, чаще всего используются следующие структуры:

• массивы;
  
• записи;
  
• файлы.
  

Массивы

Массив – это совокупность переменных одного типа, объединенных одним общим именем, но имеющим разные порядковые номера – индексы.

Массивы бывают одномерными, двухмерными, трехмерными и т.д.

Так, средние температуры воздуха в каждом месяце года составляют одномерный массив из 12-ти переменных вещественного типа с общим именем, например, t.

t (t₁, t₂, t₃, …, t₁₂)


Аналогично, оценки по результатам 5 экзаменов, сданных группой студентов из 27 человек, составляют двухмерный массив целого типа – матрицу из 27 строк и 5 столбцов, например, с именем V (ведомость).





V_1,1 V_1,2 … V_1,5

V V_2,1 V_2,2 … V_2,5

……………

V_27,1 V_27,2 …V_27,5


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

Для работы с элементами массивов используются переменные с индексами, например, t_i или V_i,j. Количество индексов у переменной определяет размерность массива. Изменяя значения индексов i или j (а это простые переменные целого типа), можно получать доступ к тому или иному элементу массива и работать с ним.

Записи

Запись – это совокупность переменных разного типа, объединенных некоторым общим свойством. Например, это могут быть сведения о сотрудниках организации, данные о параметрах некоторого технического устройства и т.п.

Переменные, входящие в состав записи, называются полями записи.

Пример записи:

Студент (stud)

Фамилия (fam)	Группа (gr)	Возраст (vz)	Ср. балл (sb)
Новиков О.Н.	СРБ-Д-1-2	19	4.35

Строковый тип Строковый тип Целый тип Вещественный тип


В оперативной памяти поля записи хранятся в соседних ячейках. Каждое поле может обрабатываться независимо от других полей. Для этой цели используются имена полей (в примере: fam, gr, vz, sb). Запись целиком также имеет имя (в примере: stud).

Файлы

Файл – это совокупность записей одной и той же структуры.

Файлы хранятся на устройствах внешней памяти: магнитных дисках, компакт дисках. Каждой записи файла на диске выделяется необходимая область памяти.

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


Понятие алгоритма

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

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

Свойства алгоритма

Алгоритм должен обладать следующими основными свойствами:

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

Средства представления алгоритмов

Для представления (записи) алгоритмов можно использовать:

• естественный язык;
  
• блок-схемы;
  
• специальные алгоритмические языки.
  

Естественный язык позволяет представлять алгоритм в словесной форме. Этот способ является наиболее простым, но одновременно и наименее строгим. Используется редко.

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

Алгоритмические языки – это специальные языки программирования. Алгоритм, записанный на таком языке, называется программой.

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

Существует много языков программирования. Важным понятием для языка является его уровень.


Уровни языков программирования

Уровень языка программирования – это степень его понятности и удобства использования для человека и степень его понятности для компьютера.

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

Различают следующие основные уровни языков программирования:

• языки машинных команд;
  
• языки Ассемблера;
  
• языки высокого уровня.
  

Языки машинных команд

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

Любой алгоритм можно представить в виде последовательности элементарных операций по обработке данных: сложение, вычитание, умножение, деление, сравнение данных, их пересылка в памяти и т.п. Каждой такой операции соответствует машинная команда, т.е. указание, какую операцию выполнить и над какими данными. Весь набор машинных команд для данного вида компьютера составляет его внутренний (машинный) язык.

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

Так программировали на ранних этапах использования компьютеров. Сейчас составление программ на языке машинных команд возлагают на сами компьютеры (смотри ниже понятие трансляции).

Языки Ассемблера

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

Например, вместо числового кода операции сложения стали использовать английское слово add, а вместо адресов данных стали указывать их имена, такие как X, Y, dan1 и т.п.

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

Языки высокого уровня

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

Примерами языков высокого уровня являются языки Turbo Pascal, Object Pascal, C++, Visual Basic и т.п.

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


Понятие трансляции

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

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

Способы трансляции

Используются два основных способа трансляции:

• компиляция;
  
• интерпретация.
  

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

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

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

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