Скачать 196.02 Kb.
|
Опорные конспекты по курсу Информатика для 8 класса (1 семестр) Введение Программное обеспечение компьютера (повторение) Для работы компьютера одинаково необходимы две составляющие - аппаратное обеспечение (hardware), т.е. все устройства, входящие в состав компьютера, и программное обеспечение (software). Без программ любая аппаратура - просто груда железа (многие так и называют аппаратную часть - «железом»). Программы для компьютера делятся на три больших класса:
Системные программы управляют работой аппаратных средств и обеспечивают услугами нас и наши прикладные программы. В первую очередь - это операционные системы ОС (что делает операционная система?), драйверы периферийных устройств, различные утилиты (форматирование, «лечение» и оптимизация дисков и многое другое). К прикладным программам относятся: текстовые редакторы, калькуляторы и электронные таблицы, графические редакторы, звуковые редакторы, мультимедиа проигрыватели, программы разработки презентаций, системы управления базами данных, коммуникационные программы, обучающие программы, электронные энциклопедии и словари, компьютерные игры и т.д. Все программы для компьютера (системные и прикладные) разрабатываются программистами, которые используют для этого различные системы программирования. Ведь программа - это набор машинных команд, которые следует выполнить компьютеру для достижения требуемого результата. Команды, составляющие программу, должны быть даны компьютеру на понятном ему языке - языке программирования. Таких языков существует, довольно много. Языки программирования и их классификация Первым программистам приходилось писать команды в «машинных кодах», т. е именно так, как воспринимает их компьютер. Например, команда сложения двух чисел могла выглядеть примерно так (но только для компьютера все эти числа еще переводились в двоичную систему счисления): 15 0127 2677 3656 : Число 15 означало операцию сложения, числа 0127 и 2677 - это номера ячеек оперативной памяти, где хранились слагаемые, а результат записывался в ячейку памяти под номером 3656. Такой способ составления программ был очень трудоемким, сопровождался большим количеством ошибок. Довольно быстро специалисты поняли, что можно упростить процесс написания программ, если создать систему условных обозначений (язык программирования) для записи команд и составить программу, которая сама переводила бы такие команды в машинный код. Например, вместо указанной выше последовательности цифр можно было написать: с = а_+ b. Здесь латинские буквы а и b обозначают ячейки памяти со слагаемыми, знак «+» означает сложения, а в ячейке, обозначенной буквой с, будет записана сумма. Различные языки программирования были разработаны разными людьми, фирмами для различных целей и в разные временные периоды. Общепринятой и строгой классификации языков программирования не существует. Но все языки программирования можно разделить на следующие группы:
К языкам программирования низкого уровня относится, например, язык ассемблер. Каждая команда такого языка при переводе на машинный язык представляет собой одну машинную команду (последовательность нулей и единиц). Язык ассемблера позволяет создавать наиболее эффективные программы, однако очень трудоемок и требует высокой квалификации программиста. Каждой команде на языке высокого уровня при переводе ее на машинный язык соответствует несколько машинных команд (т. е. последовательностей нулей и единиц). К языкам высокого уровня относятся алгоритмические языки Fortran, Basic, Cobol, С (а также объектно-ориентированное расширение этого языка C++), Pascal, Prolog и многие другие. В настоящее время большое распространение получила объектно-ориентированная технология программирования, являющаяся развитием алгоритмического программирования. К объектно-ориентированным языкам относятся языки Visual Basic, Delphi, JavaScript и другие. Компиляторы и интерпретаторы Итак, программа написана на языке программирования высокого уровня (некоторый текст) и загружена в оперативную память компьютера. Мы хотим, чтобы процессор- ее выполнил, однако процессор «понимает» команды на машинном языке, а не на языке программирования. Необходимо, чтобы в оперативной памяти компьютера находилась программа-переводчик (транслятор), автоматически переводящая программу с языка программирования на машинный язык. Программы-трансляторы языков программирования бывают двух типов: интерпретаторы и компиляторы. Интерпретатор - это программа, обеспечивающая последовательный «перевод» команд программы на машинный язык с одновременным их выполнением. Поэтому при каждом запуске программы на выполнение процедура перевода повторяется. Достоинством интерпретаторов является удобство отладки программы (поиска ошибок в ней), т.к. возможно «пошаговое» ее выполнение, а недостатком — сравнительно малая скорость выполнения. С таким типом транслятора работает язык Basic. Компилятор действует иначе, он переводит весь текст программы на машинный язык и сохраняет его в исполняемом файле (обычно с расширением ехе). Затем этот уже готовый к выполнению файл, записанный на машинном языке, можно запускать на выполнение. Достоинством компиляторов является большая скорость выполнения программы, а недостатком - трудоемкость поиска ошибок, т.к. невозможно пошаговое выполнение программы. С транслятором-компилятором работает язык Pascal. Основы алгоритмизации Тема 1 Понятие алгоритма. Свойства алгоритмов В своей повседневной деятельности нам постоянно приходится сталкиваться с разнообразными правилами, предписывающими последовательность действий, цель которых состоит в достижении некоторого необходимого результата. Подобные правила очень многочисленны. Например, мы обязаны следовать вполне определенной системе правил, чтобы подняться в лифте или пройти через турникет метро, чтобы найти корни квадратного уравнения или с помощью циркуля и линейки разделить отрезок пополам. Нужно выполнить определенную последовательность действий, чтобы приготовить лекарство или связать свитер. Примеры такого рода можно продолжать неограниченно. Их часто называют алгоритмами. Алгоритм - это последовательность действий со строго определенными правилами выполнения. Составление алгоритмов подразумевает существование определенных исполнителей, которые будут выполнять действия, предписываемые алгоритмами. В роли исполнителей могут выступать роботы, механические устройства, компьютеры или люди. Предполагается, что алгоритм понятен исполнителю, т.е. исполнитель алгоритма знает, как его выполнять. Использование технических устройств, компьютеров в качестве исполнителей алгоритмов предъявляет ряд требований к этим алгоритмам. В отличие от людей технические устройства могут выполнять только точно определенные операции, работать по программе. Можно выделить несколько важных свойств, которыми должны обладать алгоритмы: 1) массовость алгоритма - возможность его применения для решения целого класса конкретных задач, отвечающих общей постановке задачи;
Теперь можно более точно определить алгоритм. Алгоритм - это конечная совокупность предписаний, сформулированных на языке, понятном исполнителю, в результате выполнения которых от исходных данных приходят к искомому результату. Кроме того, алгоритм должен обладать свойствами массовости и однозначности. Тема 2 Способы описания алгоритмов Форма записи алгоритма (слова, формулы, рисунки и т. д.) существенным образом зависит от той цели, которую мы преследуем при записи алгоритма. Рассмотрим некоторые способы записи алгоритмов. 1). Словесный способ описания алгоритма. Примерами такой формы записи алгоритма является любая инструкция по использованию бытовой аппаратуры, рецепты приготовления различных блюд и т.п. Это так называемые бытовые алгоритмы. Но словами можно описать и решение некоторых математических задач. 2). Формульный способ записи алгоритма. Примерами этой формы записи алгоритма может служить любая математическая формула, порядок вычислений в которой определяется наличием скобок и старшинством математических операции. Совокупность формул для решения задачи по физике - это тоже определенный формульный алгоритм. Первый и второй способы записи алгоритмов часто используются вместе при описании решения 'задачи. 3). Блок-схема алгоритма. Она служит для наглядного графического изображения алгоритма. Любая блок-схема представляет собой набор некоторых геометрических фигур или блоков. как правило, прямоугольников, ромбов, овалов. В этих фигурах можно записать любую формулу, любой текст о том, что надлежит сделать исполнителю на данном этапе выполнения алгоритма. Последовательность действий в блок-схеме указывается с помощью стрелок, соединяющих отдельные блоки. Для удобства словесного описания блок-схемы блоки в ней могут быть помечены номерами. Например, изобразим с помощью блок-схемы правило, позволяющее не ошибиться в написании -ться у глаголов в неопределенной форме и -тся у глаголов в 3-ем лице: Начало и конец алгоритма обычно обозначаются овальными блоками. Конкретные действия, предписанные исполнителю, изображаются блоками-прямоугольниками (блоки 2 и 3). Проверка некоторого условия в блок-схемах соответствует логический блок, изображаемый в виде ромба, внутри которого и записано условие (блок 1). От логического блока ведут две стрелки – одна с надписью "да", другая -"нет". Если условие оказывается выполненным, то следующим по порядку будет блок, на который указывает стрелка с надписью "да", в противном случае очередным по порядку будет блок, на который отсылает стрелка с надписью "нет". Блок-схема позволяет отчетливо представить себе связи между частями алгоритма, проследить за последовательностью действий в алгоритме. 4). Программы. Для того, чтобы поручить компьютеру решение какой-либо задачи по выбранному алгоритму, нужно записать его уже на каком-то другом языке, таком, чтобы его мог понять и выполнить компьютер. Получится последовательность указаний для компьютера, каждое из которых реализуется соответствующей командой из фиксированного набора команд специального машинного языка, называемого языком программирования. Программа - это последовательность машинных команд, которые следует выполнить компьютеру для решения той или иной задачи. Иными словами, программа - это форма представления алгоритма для исполнения его машиной. Однако при записи алгоритма на языке программирования редко удается избежать ошибок. Процесс поиска и исправления ошибок называется отладкой программы. Ошибки в программах подразделяются на 2 вида:
Тема 3 Основные виды алгоритмов Очевидно, что в зависимости от условий задач и исходных данных к ним алгоритмы решения этих задач будут различны. Однако можно выделить основные виды алгоритмов, используемых для решения простых задач. Эти простые алгоритмы и используются при составлении алгоритмов решения сложных задач. Основные виды простых алгоритмов будут пояснены ниже на соответствующих блок-схемах. Действие 1 1). Линейные алгоритмы. В этих алгоритмах все предписываемые исполнителю действия выполняются в том порядке, в каком они написаны. Эти алгоритмы носят строго последовательный характер. Часто такие алгоритмы используются для решения задач вычислительного типа. Действие 2 Действие n 2). Ветвящиеся (разветвляющиеся) алгоритмы. Очень часто при решении задачи необходимо выполнение различных действий в разных ситуациях. Запись вариантов выбора действий в алгоритмах проводится двумя основными способами, которые могут комбинироваться. Первый из них - это действия, выполняемые только при соблюдении некоторых условий, иначе говоря, условные действия. Да Условие выполнено? Действия Нет Правила выполнения условных действий: эти действия выполняются, только если выполняется проверяемое условие. В противном случае эти действия не выполняются вовсе. Второй способ - выбор различных вариантов действий при выполнении или невыполнении условия. Нет Да Условие выполнено? Действие 2 Действие 1 Правила выполнения: действия 1 выполняются тогда и только тогда, когда соблюдается условие. Действия 2 выполняются, только если условие не соблюдается. 3). Циклические алгоритмы. Способы решения многих задач часто основаны на повторении одних и тех же действий вплоть до достижения некоторой цели. Организация повторений в алгоритмах называется циклом. Существует два вида циклических алгоритмов: в одном цикле число повторений заранее определено, а в другом - количество повторений заранее неизвестно, выход из этого цикла определяется выполнением некоторого условия. Первый вид циклических алгоритмов называется циклом со счетчиком. В цикле со счетчиком указывается начальное и конечное значения счетчика повторений: Параметр цикла (счетчик цикла) k принимает последовательно значения k = 1 .. n 1, 2, 3 … n Действия Правила выполнения циклов со счетчиком: до начала цикла счетчик получает начальное значение к=1. Далее выполняются действия, а затем проверяется, достиг ли счетчик конечного значения n. Если же счетчик еще не достиг конечного значения, то он увеличивается на единицу и действия выполняются еще раз. Если же счетчик уже достиг конечного значения, то выполнение цикла завершается. Циклический алгоритм, в котором число повторений определяется выполнением некоторого условия, называется циклом по условию: Правила выполнения: если условие выполняется с самого начата, то выполняются и действия; если после этого условие вновь выполняется, то вновь выполняются и действия. Повторение действии продолжается до тех пор, пока выполняется условие. Завершение выполнения цикла происходит тогда и только тогда, когда перестанет выполняться условие повторения. В решении математических задач циклы широко используются для вычисления различных последовательностей. Сложность алгоритмов с циклами нарастает при использовании вложенных циклов. Речь идет об алгоритме с циклом, внутри которого тоже есть цикл. Примером алгоритма с двумя вложенными циклами может служить алгоритм, описывающий ход часов: главный (внешний) цикл отсчитывает часы, первый вложенный во внешний цикл отсчитывает минуты, ну а уже в этот вложенный цикл встроен еще один цикл, который считает секунды. Тема 4 Вспомогательные алгоритмы. Понятие подпрограммы Решение новых задач мы всегда пытаемся свести к решению уже известных, а решение сложных задач - к решению более простых подзадач. Соответственно в алгоритмах решения сложных задач для решения подзадач могут выделяться вспомогательные алгоритмы, которые служат для их решения. Каждый такой вспомогательный алгоритм описывает способ решения некоторой вспомогательной задачи или даже общий способ решения некоторого класса вспомогательных подзадач. Построение сложных алгоритмов с помощью вспомогательных алгоритмов имеет много общего с возведением зданий. Сложные алгоритмы, как и дома, строятся из блоков, роль которых играют вспомогательные алгоритмы. Например, в общем виде алгоритм выполнения домашнего задания на следующий день может выглядеть так: 1) приготовить задание по алгебре; 2) приготовить задание по русскому языку;
Каждый шаг приведенного алгоритма можно детализировать с помощью вспомогательных алгоритмов. Так выполнение задания по алгебре состоит из следующих шагов:
Выполнить задание по русскому языку поможет алгоритм:
Урок по литературе разбивается на следующие шаги:
И такие вспомогательные алгоритмы можно привести для выполнения задании по остальным предметам. Такой способ описания алгоритмов называется описанием сверху вниз. В данном примере последовательно, сверху вниз, уточняются ваши действия по выполнению домашнего задания. При построении алгоритмов последовательно, сверху вниз, уточняется план действий, который доводится до детальных инструкций, непосредственно понятных исполнителям. (По такому принципу могут составляться не только алгоритмы. Таким же образом, сверху вниз, могут подготавливаться доклады, статьи, книги.) Использование вспомогательных алгоритмов существенно упрощает процесс создания алгоритмов решения сложных задач. Если в качестве исполнителя алгоритма предполагается использование компьютера, то для него должна быть написана программа. Представим себе, что при записи алгоритма решения некоторой задачи мы столкнулись с ситуацией, когда одна и та же последовательность действий должна выполняться во многих различных местах алгоритма. Конечно, можно было бы в каждом таком месте вставлять одинаковые последовательности команд, реализующие эти действия. Программа от этого бы разрослась, да и сам процесс многократного написания такой последовательности достаточно трудоемкий. Эту последовательность команд выделяют во вспомогательный алгоритм и обращаются к ней из нужных мест программы. Такую выделенную последовательность команд, к которой можно обращаться из разных мест основной программы, называют подпрограммой. При использовании вспомогательных алгоритмов (подпрограмм) необходимо учитывать способ передачи этим алгоритмам (подпрограммам) исходных данных и получения от них результатов решения. Тема 5 Понятие переменных. Оператор присваивания Обычное понятие переменной отличается от переменной в вычислительных алгоритмах и программах. Если в математике переменная- это некоторая величина, то в алгоритмах и программах переменная - это область памяти, в которой могут храниться определенные значения. При этом в математике если значение переменной определено, то оно остается неизменным. В алгоритмах и программах значения переменных могут многократно изменяться по ходу вычислений. Использовать в программе адреса памяти (номера ячеек памяти компьютера) не только неудобно, но и, по ряду причин невозможно. Поэтому вместо адресов вводятся их условные обозначения - имена (идентификаторы) переменных. Имена переменных могут состоять (по правилам многих языков программирования) из прописных и строчных букв латинского алфавита, цифр и знака подчеркивания. Начинаться идентификатор может с любого символа, кроме цифры. Примеры правильного задания имен переменных: ml, Sum, x 1, Y4. Кроме нового понятия переменных для записи вычислительных операций в алгоритмах и программах вводится еще одно новое понятие -присваивание значения переменной, записываемое знаком := (знак читается "присваивается") Например, запись а: =5 в алгоритме читается: переменной а присваивается значение 5. Запись b:=а+3 читается: переменной b присваивается значение выражения а+3. Смысл последней записи состоит в следующем. Исполнитель должен вычислить значение выражения а+3 по имеющемуся значению переменной а и присвоить это значение переменной b. Повторим, что введение новых понятий и обозначений связано c особенностью выполнения вычислительных операций в компьютере: результаты всех вычислений, все исходные и промежуточные данные записываются и хранятся в памяти компьютера. Знак := в программных алгоритмах называется еще оператором присваивания, т.к. любую команду для компьютера, записанную на языке программирования, принято называть оператором. Запишем с помощью операторов присваивания фрагмент программы, реализующей следующую простую задачу: сумму значений переменных а и b записать в переменную d, а разность – в переменную с, после чего увеличить значения переменных а и b на единицу:
Bo всех случаях вначале вычисляется значение выражения, расположенного справа от комбинации символов :=, а затем вычисленное значение присваивается переменной, расположенной слева. Для того чтобы оператор присваивания мог быть выполнен, необходимо, чтобы все переменные, которые входят в выражение, имели некоторые значения. Из приведенного примера видно, что в ходе выполнения программы переменные могут изменять свои значения. |