«Алгоритмическое решение задач, анализ алгоритмической сложности. Основы программирования»

Тема 3 «Алгоритмическое решение задач, анализ алгоритмической сложности. Основы программирования»

Слово «алгоритм» происходит от algorithmi – латинской формы написания имени великого среднеазиатского математика IX века Мухаммеда Аль-Хорезми, который сформулировал правила выполнения четырех арифметических действий. Многие годы математики использовали этот термин для описания правил решения математических задач.

Но не следует считать алгоритм чисто математическим понятием. По определению:

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

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

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

Разработка алгоритма – сущность процесса решения задачи с помощью ЭВМ. Процесс составления алгоритмических предписаний называется алгоритмизацией. Чтобы решить любую задачу на ПК, надо выполнить действия в определенной последовательности.

Этапы решения задач на ЭВМ

1. Постановка задачи (создание математической модели)

2. Разработка алгоритма решения задачи

3. Перевод алгоритма на выбранный язык программирования

4. Ввод и отладка программы на ЭВМ

5. Проверка правильности решения методом тестирования.

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

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

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

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

4. Результативность (Не каждый перечень последовательных действий приводит к результату. Алгоритмом считается только тот перечень действий, который приводит к решению за разумный период времени.)

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

6. Понятность (Алгоритм должен быть понятен пользователю или исполнителю. Иначе его невозможно будет выполнить)

Существует несколько способов задания алгоритмов:

1. На естественном языке (рус., каз., и т.д.)

2. В виде схем (блок-схемы)

3. На алгоритмическом языке

4. На языке программирования.

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

Название процесса	Вид блок- схемы	Основные действия
Вычисление, присваивание		Вычисление математических выражений, присваивание значений
Выбор, условие		Выбор способа решения задачи, выполнение условия
Цикл		Начало цикла (повторения)
Документ		Вывод результата на принтер
Ввод, вывод		Ввод данных с клавиатуры, вывод результатов на экран
Начало, конец		Начало, конец алгоритма
Подпрограмма		Вход и выход в подпрограмму
Пояснение		Пояснение к схемам, формулам

Кроме этого, в алгоритмизации и программировании используют три основные структуры:

1. Линейный алгоритм,

2. Разветвляющийся алгоритм,

3. Циклический алгоритм.

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

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

3. Циклический алгоритм предусматривает многократное повторение одних и тех же действий над новыми данными.

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

Пример №1.

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

Пример №2. Составить алгоритм нахождения максимального числа из двух заданных

Пример №3. Составить алгоритм нахождения площади 5-ти прямоугольных треугольников по заданным размерам катетов.

Тема 4 «Компьютерные сети, сетевые и телекоммуникационные технологии. Интернет»

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

Информационные ресурсы - это файлы программ и документов, технические – это принтер, модем, диски. Чтобы сеть функционировала необходимо специальное аппаратное и техническое обеспечение.

До недавнего времени различали 2 вида сетей: локальные и глобальные. Сейчас сюда добавляют 3-й вид – региональные или корпоративные.

Локальные сети

Локальные сети представляют собой небольшую группу ПК, расположенных в одном здании или соседних зданиях и соединенных между собой линиями связи (проводами) относительно небольшой длины. При соединении 2-х ПК (локальное кабельное соединение) не требуется никакого дополнительного оборудования или настройки сети. Но если ПК больше 2-х, то возникает необходимость специальной настройки управления компьютером и, даже, возможно появление дополнительного оборудования – сетевого адаптера. Сетевой адаптер или HUB – это устройство, обеспечивающее работу нескольких ПК в сети, которое определяет очередность передачи данных линиям связи. При этом ПК должен так же иметь сетевую плату или сетевую карту. Способ соединения ПК в локальную сеть (конфигурация сети) называют топологией сети.

Существует несколько видов топологии:

1. Шина

2. Кольцо (замкнутая шина)

3. Звезда

4. Комбинированная

Комбинированный способ является сочетанием любых трех в любой последовательности.

Из рисунков хорошо видно, что только в соединении звездой имеется сетевой адаптер. Достоинством 1-го и 2-го соединений является более высокая скорость передачи сигналов по сети, но в случае выхода из строя одного из ПК, нарушается работа всей сети. В «звезде» поломка ПК не влияет на работу сети, но зато скорость работы в сети несколько ниже.

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

Кроме этого различают 2 вида сети: сервер-клиент и одноранговые.

В первом случае один ПК является управляющим или сервером. Обычно он имеет больше памяти, к нему подключены различные устройства оргтехники: принтеры, модем; на нем хранится общая для всех информация и он выполняет большую часть работы. Остальные ПК называют станциями. Если же сервера нет, и все ПК имеют равные возможности, то такая сеть называется одноранговой. Для работы в такой сети достаточно настроить «Сетевое окружение», присвоить всем ПК уникальные номера и одно имя группе. При создании рабочих групп учитывают принадлежность ПК тому или иному подразделению: бухгалтерии, администрации, отделу кадров и т.п. В дальнейшем пользователю достаточно войти в «Сетевое окружение», выбрать ПК по имени, сделать на нужном значке двойной щелчок, ввести пароль, если он предусмотрен и он оказывается на чужом ПК. При этом на всех ПК должен быть настроен «Доступ» в свойствах диска С: или другой папки. Доступ бывает 2-х видов:

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

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

Глобальные сети.

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

Региональные или корпоративные сети.

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

Обозначение сетей:

• глобальные сети (WAN — Wide Area Network);

• региональные сети (MAN — Metropolitan Area Network);

• локальные сети (LAN — Local Area Network).

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

Запомните! Единица измерения скорости передачи данных — бит в секунду.

Примечание. Часто используется единица измерения скорости — бод. Бод — число изменений состояния среды передачи в секунду. Так как каждое измене­ние состояния может соответствовать нескольким битам данных, то реальная скорость в битах в секунду может превышать скорость в бодах.

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

Задачи.

1. Теоретически модем, передающий информацию со скорость 57600 бит/с, может передать 2 страницы текста (3600 байт) в течении:

A) 0.5 ч;

B) 0.5 мин;

C) 0.5 с;

D) 3 мин 26 с;

E) 2 мин 16 с.

2. Определите время передачи двух страницы текста (3 600 байт) модемом, передающий информацию со скоростью 28 800 бит/с.

A) 1 минута;

B) 1 час;

C) 1 секунда;

D) 1 день;

E) 2 минуты.

Интернет

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

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

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

1. Межсетевой протокол (Iпternet Protocol- IP) разделяет передаваемые данные на отдельные пакеты и снабжает заголовком с указанием адреса получателя.

2. Протокол управления передачей (Transmission Control Protocol - ТСР) отвечает за правильную доставку такого пакета, т.е. разбиение файлов на IP-пакеты в процессе передачи и сборку файлов в процессе получения;

Поскольку оба эти протокола пред­ставляют собой единое целое, то говорят о прото­коле ТСР/IР. Этот протокол является своеобразным языком, без которого невозможно взаимопонимание отдель­ных участников - различных прог­рамм, компьютеров и сетей, входящих в глобальную сеть.

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

Идентификация отдельных компьютеров и их пользователей осуществляется при помощи двух адресов:

• доменный адрес, который понятен человеку;

• IР-адрес, который понятен компьютеру.

Пример:
адрес www.геlcоm.ru:

• www - имя ресурса - World Wide Web;

• relcom - название фирмы:

• ru – Россия.

IP - адрес представляет собой 32-битовое число (например _49._19._81._ _2), разделенное точками на 4 части, из которых ни одна не может превышать 255. Этот адрес мало о чем говорит пользователю, но именно он считывается компьютером.

Чтобы посмотреть IP – адрес своего ПК, нужно через правую кнопку мыши открыть свойства службы «Сетевое окружение», затем также через правую кнопку открыть свойства своего сетевого подключения и посмотреть свойства «Протокол Интернета ТСР/IР». Существует два вида IP – адреса: статический и динамический. Статический адрес постоянно закреплен за ПК и прописан в окне свойств, а динамический не указывается явно, так как при каждом подключении к Интернету, ПК получает от сервера свободный (не занятый) IP – адрес. World Wide Web. Появление и развитие глобальной информационной сети Интернет, обусло­вили разработку специальных программ - браузеров. Эти программы организуют просмотр ресурсов Интернета и ориентированы на работу в сетях, реализованных по стандартам Интернета, и Всемирной паутины - WWW.

World Wide Web (WWW) - одна из технологий Интернета. Суть WWW заключается в представлении информации в виде расположенных на раз­личных компьютерах отдельных текстовых, графических и других файлов. Эти файлы объединены между собой гиперсвязями. Совокупность таких файлов называют Web-документом или Web-сайтом (Web-site). Web-сайт состоит из отдельных Web-страниц. Несколько Web-документов располагаются на Web-сервере. Поиск Web-документа и обращение к нему выполняется по специальному адресу - URL (Uniform Resource Locator). Стандартный URL состоит их трех частей, определяющих протокол передачи информации, имя компьютера, на котором находится информация, и путь к ней. Например, структура URL компании Vermont Teddy Bears, осуществляющей продажу игрушек, выглядит так:

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

Для того, чтобы информация быстро и качественно предавалась по сетям, используются специальные форматы файлов, разработанные специально для работы в Интернет и в WWW:

Тип информации	Расширение (тип файла)
Текст	.htm .html
Звук	.аи .snd .mid .тр3
Изображение	gif .jpg .tif
Видео	.mpg .mov .avi

Для просмотра Web-документов необходимо специальное программное обеспечение. Такие программы - приложение называются Web-браузерами.

Наиболее популярными являются:

1. Internet Ехрlогег (разра­ботка фирмы Мicrosоft)

2. Netscape Navigator (фирмы Netscape Communications Согр.).

3. Opera и многие др.

Помимо ресурса WWW, Web-браузеры до­пускают обращение к другим ресурсам Интернета:

• поисковые системы,

• электронная почта,

• чаты,

• форумы,

• файловые архивы FТP,

• телекон­ференции.

Электронная почта (e-mail) (торговая марка Electronic Маи) была зарегистрирована в 1974 году. До тех пор использовалось название "Система передачи сообщений с помощью компьютеров" (Computer Based Messaging System).

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

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

Адрес электронной почты выглядит так:

логин @ имя почтового сервера

Например: [email protected]

Если какое-то письмо не может быть сразу доставлено, например не работает сервер, где находится ящик, письмо ставится на очередь и будет отправляться каждые 10-15 минут. Если через несколько часов письмо все еще не будет отправлено, то отправитель получает уведомление, что адрес не существует. Почтовая служба устроена таким образом, что письмо просто так исчезнуть не может. При отправке почты взаимодействие происходит по протоколу исходящей почты SMTP (Simple Mail Transfer Protocol – простейший протокол исходящей почты). При приеме работает протокол входящей почты РОР3.

Существует множество различных почтовых программ:

• Microsoft Outlook Express,

• Microsoft Internet Mail,

• Netscape Messenger

• Eudora (не рекомендуется для переписки по-русски, платная),

• The Bat!.

Эти программы позволяют хранить всю отправленную и полученную корреспонденцию на своем ПК, а не на почтовом сервере. Это позволяет работать с почтой, не подключаясь к Интернету, так как подключение в этом случае необходимо только в момент отправки и приемки почты. Каждый почтовый имеет как минимум 4 папки (каталога): полученные, отправленные, черновики и корзину. Но обычно можно создавать дополнительные папки для упорядочивание писем. Но если ящик находится на сервере, то есть ограничение на размеры ящика (в Кбайтах), а если пользоваться почтовой программой, то письма как бы перекачиваются с сервера, и хранятся на ПК пользователя, поэтому объем для их хранения не ограничивается.

Служба ICQ.

Предназначена для коммуникационных целей. Это своеобразный Интернет - пейджер, который немедленно сообщает, кто из друзей находится в данный момент в Интернете и при этом желает общаться. Каждому абоненту присваивается уникальный номер UIN –универсальный Интернет, который снабжается паролем. Основная форма общения в ICQ – обмен короткими (до 450 символов) сообщениями почти в реальном времени. Необходимо только установит на ПК специальную программу, которые как правило бесплатные.

Chat.

В переводе с английского означает «дружеский разговор, беседа, болтовня». В современном Интернете за этим термином закрепилось значение «общения в реальном режиме времени». Специальная программа IRC – Internet Relay Chat – организует многопользовательскую систему общения. В настоящее время Chat организуют на многих сайтах, чтобы привлекать дополнительных пользователей.

Форумы.

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

Конференции.

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

Контрольные вопросы

1. Что такое информация?

2. Какие разделы входят в информатику?

3. Как можно классифицировать информацию?

4. Как информация измеряется?

Литература

1. Аветисян Р. Д., Аветисян Д. Д., Теоретические основы информатики – М.: Наука, 1997. , с. 3 - 75

2. Аладьев В.З. и др. Основы информатики. – М.: Филин, 1999., с 3- 41

3. Макарова Н. В., Матвеев Л. А., Бройдо В. Л. и др. Информатика / Под ред. Макаровой Н. В. М, 2003.

4. Информатика / Под ред. С. В. Симоновича. - СПб., 2004.

5. Моисеев А.В. Информатика. - М.: Академия, 1998.