Автор работы: Пользователь скрыл имя, 24 Марта 2015 в 06:26, курс лекций
Основные понятия и определения информатики.
Начало развития информатики как науки положило появление ЭВМ в 50-е годы прошлого столетия.
Выделению информатики в отдельную науку способствовало наличие единой формы представления информации в компьютерах: числовая, символьная и аудиовизуальная (звук, изображение) представляется в двоичной форме.
Любая компьютерная программа представляет собой последовательность отдельных команд.
Команда — это описание операции, которую должен выполнить компьютер. Как правило, у команды есть свой код (условное обозначение), исходные данные (операнды) и результат.
Совокупность команд, выполняемых данным компьютером, называется системой команд этого компьютера.
Для автоматизации работы с данными, относящимися к различным типам, очень важно унифицировать их форму представления — для этого обычно используется прием кодирования, то есть выражение данных одного типа через данные другого типа. Естественные человеческие языки — это не что иное, как системы кодирования понятий для выражения мыслей посредством речи. К языкам близко примыкают азбуки (системы кодирования компонентов языка с помощью графических символов).
Своя система кодирования существует в вычислительной технике — она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1 – битов.
Одним битом могут быть выражены два понятия: 0 или 1 (да или истина, черное или белое, истина или ложь и т. п.). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия:
00 01 10 11
Тремя битами можно закодировать восемь различных значений:
000 001 010 011 100 101 110 111
Увеличивая на единицу количество разрядов в системе двоичного кодирования, мы увеличиваем в два раза количество значений, которое может быть выражено в данной системе-, то есть общая формула имеет вид:
N=2m,
где N— количество независимых кодируемых значений;
m — разрядность двоичного кодирования, принятая в данной системе
(возведение в степень
– замена многократной
одна позиция 0 или 1 - 2 комбинации, 2 позиции – 2*2=4 комбинации, 3 позиции - 8 комбинаций и т.д.)
Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). Шестнадцать бит позволяют закодировать целые числа от 0 до 65 535, а 24 бита — уже более 16,5 миллионов разных значений (2 в 24 степени).
Если каждому символу алфавита сопоставить определенное целое число (например, порядковый номер), то с помощью двоичного кода можно кодировать и текстовую информацию. Для кодирования 256 различных символов достаточно восьми двоичных разрядов или 1 байт информации. Этого хватит, чтобы выразить различными комбинациями восьми битов все символы английского и русского языков, как строчные, так и прописные, а также знаки препинания, символы основных арифметических действий и некоторые общепринятые специальные символы, например символ "§".
Для того чтобы весь мир одинаково кодировал текстовые данные, нужны единые таблицы кодирования, а это пока невозможно из-за противоречий между символами национальных алфавитов. Кодовая страница – это таблица, ставящая в соответствие каждому символу определенный числовой код. Например, заглавная латинская буква A имеет числовой код 65 (причем, во многих кодовых страницах).
Для английского языка, противоречия уже сняты. Институт стандартизации США (ANSI — American National Standard Institute) ввел в действие систему кодирования ASCII (American Standard Code for Information Interchange — стандартный код информационного обмена США). В системе ASCII закреплены две таблицы кодирования — базовая (во всех кодовых страницах одинаковая) и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255 (для национальных алфавитов).
Аналогичные системы кодирования текстовых данных были разработаны и в других странах. Отсутствие единого стандарта в этой области привело к множественности одновременно действующих кодировок. Только в России можно указать три действующих стандарта кодировки: Windaws-1251 для платформы Windows, CP866 - «альтернативная» кодировки, другая распространенная кодировка КОИ8-R, есть и другие, но они используются редко.
В связи с изобилием систем кодирования текстовых данных была принята Универсальная система кодирования текстовых данных UNICODE. Этот стандарт был предложен в качестве решения проблемы наличия многих языков и множества различных кодовых страниц (кодировок). В традиционных кодовых страницах для кодирования одного символа служит один байт. Таким образом, с помощью одной такой таблицы можно закодировать только 256 различных символов. Поэтому возникают трудности с использованием в документах одновременно нескольких естественных языков (например, русского и датского). Если же для кодирования одного символа допустить использование более чем одного байта, то тогда эта проблема была бы решена. В стандарте UNICODE предложены различные формы (схемы) кодирования символов. Форма кодирования UTF-8 предполагает использование от одного до четырех байтов для кодирования одного символа. При этом для представления самых распространенных символов используются однобайтовые коды. Форма кодирования UTF-16 предписывает использование одного или двух двухбайтовых блоков для кодирования каждого символа, а в UTF-32 используются только четырехбайтовые блоки. (http://ru.wikipedia.org Unicode Transformation Format)
Лекция 4. Алгоритм. Свойства алгоритмов
Понятие алгоритма такое же основополагающее для информатики, как и понятие информации.
Название "алгоритм" произошло от латинской формы имени среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi) – жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику.
Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов.
Алгоритм – точное предписание, определяющее вычислительный процесс, ведущий от начальных данных к искомому результату.
Исполнитель алгоритма — это некоторая абстрактная или реальная система, способная выполнить действия, предписываемые алгоритмом. В информатике универсальным исполнителем алгоритмов является компьютер.
Основные свойства алгоритмов
1. Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов). Разбиение на отдельные этапы, выполнение которых не вызывает сомнений.
2. Детерминированность (опpеделенность) — каждое пpавило алгоpитма должно быть четким, однозначным. При заданных исходных данных обеспечивается однозначность искомого результата. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.
4. Pезультативность (или конечность) - за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
5. Массовость - алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.
Существуют множество различных форм записи алгоритмов. Это связано с тем, что каждый исполнитель алгоритмов "понимает" лишь такой алгоритм, который записан на его "языке" и по его правилам. Выделяют следующие формы записи алгоритмов:
Алгоритм записывается в виде пронумерованных этапов его выполнения. Пример: Алгоритм сложения двух чисел (a и b).
Словесный способ не имеет широкого распространения, так как такие описания:
Это запись алгоритма на специальном языке (в том числе и на языке программирования). Она осуществляется, строго следуя правилам того или иного алгоритмического языка.
Заголовок включает в себя название алгоритма, имена исходных данных (это величины, без которых выполнить алгоритм невозможно) и имена результатов (это величины, значения которых вычисляются в алгоритме).
Алгоритм записывается в виде схемы, состоящей из блоков (геометрических фигур) с размещенными в них действиями. Блоки соединяются стрелочками и показывают структуру всего алгоритма. Алгоритм в виде блок-схемы начинается блоком "начало" и заканчивается блоком "конец".
Основные блоки приведены на рисунке.
Рис.4. Изображение основных блоков
При составлении блок-схемы алгоритма сначала выделяют исходные данные (все переменные величины после знака равенства и в условии) и результат (величины которые необходимо найти). Если в задании подразумеваются, но не указываются имена величин, то они обозначаются самостоятельно. При отсутствии исходных данных блок ввода не пишется. В один блок можно поместить одно действие. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. По умолчанию не требуется рисование стрелок при проведении линий слева направо и сверху вниз. Во всех остальных случаях стрелки необходимы.
Пример: Алгоритм вычисления значения выражения K=3b+6а приведен на рис. 5.
Рис. 5. Текстовая и блок схема форма записи алгоритма вычисления выражения K=3b+6а
1
2
3
Рис 6. Вычисление длины окружности по известной площади круга.
Алгоритм, определяющий пройдет ли график функции y=3x+4 через точку с координатами x1,y1
1
2
Да
3
Рис. 7. Алгоритм, определяющий пройдет ли график функции y=3x+4 через точку с координатами x1,y1
(т.е. перемножаем все числа от 1 до n, при этом 0!=1)
5!=1*2*3*4*5=120
1
2
3
4
5
Да
6
Нет
7
По своей структуре различают следующие типы алгоритмов: линейные, разветвляющиеся и циклические.
В линейных - все предписания выполнятся одно за другим. Например, алгоритм вычисления длины окружности по известной площади круга.
В разветвляющихся схемах алгоритмов для конкретных исходных данных выполняются не все заданные предписания. Какие именно предписания будут выполняться, определяется в процессе выполнения алгоритма в результате проверки некоторых условий. Пример – алгоритм, определяющий пройдет ли график функции y=3x+4 через точку с координатами x1, y1.
Циклическим алгоритмом называется такой алгоритм, в котором можно выделить многократно повторяющуюся последовательность предписаний, называемую циклом. Пример – алгоритм, определяющий факториал натурального числа. В этом алгоритме введена дополнительная переменная I, которая является параметром цикла и изменяется от начального значения 1 до конечного значения n с шагом 1. На каждом шаге итерации искомая величина f умножается на переменную цикла.
Цикл – конструкция (или процесс), содержащая операторы, выполнение которых предполагается выполнять многократно, если условие цикла выполняется n раз, если условие не выполняется, то цикл выполняется 0 раз. (Цикл -это неоднократное повторение каких-либо действий.)
Итерация – один виток цикла, один оборот цикла.
Оператор – одна строка на языке программирования, то над чем производится операция, например «а+в», где а и в – операторы, а «+» - операция.
В реальных задачах, как правило, сочетаются все три типа алгоритмов.
Базовые алгоритмические структуры Таблица 1
Вид алгоритма |
Ключевые слова |
Структура |
1 |
2 |
3 |
Алгоритм, в котором есть структура следование называется линейным. Следование - это расположение действий друг за другом. |
Ключевых слов нет. |
|
Алгоритм, в котором есть структура ветвление называется разветвляющимся. Ветвление - это выбор действия в зависимости от выполнения какого-нибудь условия. |
если...то...иначе..; при ...(в значении если...). |
|
Алгоритм, в котором есть структура цикл называется циклическим. Цикл -это неоднократное повторение каких-либо действий. |
от...до...; ... раз; пока ...; если... (в значении пока...). |