Шпаргалка по "Информатике"

1. Понятие алгоритма. Основные типы алгоритмов.

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

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

Или (более  коротко):

Алгоритм - это строго определенная последовательность действий, необходимая для решения данной задачи.

Название "алгоритм" произошло от латинской формы  имени среднеазиатского математика аль-Хорезми — Algorithmi. Алгоритм — одно из основных понятий информатики и математики. 

Основные  типы алгоритмов

В зависимости  от особенностей своего построения алгоритмы  делятся на три основные группы:

1. Линейные;
2. Разветвляющиеся;
3. Циклические.

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

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

 

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

 

Примеры команды если  

3. Циклические алгоритмы. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:

Примеры команд пока и для 

Основные  свойства алгоритмов

Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.

Дискpетность (прерывность, раздельность) — т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

Опpеделенность — т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.

Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.

Массовость. Это означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

    Способы записи алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

• словесная (записи на естественном языке);
• графическая (изображения из графических символов);
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• программная (тексты на языках программирования).

 

2. Языки программирования высокого и низкого уровня.

    Язык  программирования - это специальный язык, на котором пишут команды для управления компьютером.

    Программы, написанные на каком-либо языке программирования должны затем транслироваться (транслятором или интерпретатором) в машинный код, который только и может исполняться компьютером.  

    Различают языки:

    - низкого уровня (машинные и машинно-ориентированные),

    - высокого уровня (на зависят от  типа ЭВМ).  

    Язык  низкого уровня - это язык программирования предназначенный для определенного типа компьютера и отражающий его внутренний машинный код.

    Язык  низкого уровня бывают двух видов:

    Машинные  языки — языки программирования, воспринимаемые аппаратной частью компьютера (машинные коды);

    Машинно-ориентированные  языки — языки программирования, которые отражают структуру конкретного типа компьютера (ассемблеры);

    Достоинства машинных языков:

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

    Недостатки  машинных языков:

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

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

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

    Языки высокого уровня бывают:

    - процедурно-ориентированные  (Паскаль, Фортран,  Бейсик ),

    - проблемно-ориентированные  (Лисп, РПГ, Симула ),

    - объектно-ориентированные  (С++). 

    Процедурно-ориентированные языки — языки программирования, где имеется возможность описания программы как совокупности процедур (подпрограмм);

    Проблемно-ориентированные  языки — языки программирования, предназначенные для решения проблем определенного класса;

    Обектно-ориентированные языки – языки, поддерживающие понятие объектов и их свойств и методов обработки

    Основные  преимущества таковы языков высокого уровня:

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

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

Обзор