- •Понятие алгоритма, его основные свойства. Способы представления алгоритмов.
- •Архитектура эвм. Внешние устройства, их назначение, основные характеристики, принципы работы.
- •Организация ввода – вывода в языках программирования.
- •Подпрограммы и процедуры в языках программирования. Процедуры с передачей параметров. Функции, определяемые пользователем.
- •Сетевые технологии. Локальные и глобальные компьютерные сети.
- •Архитектура эвм. Внутренние устройства, их назначение, основные характеристики, принципы работы.
- •Программное обеспечение эвм. Файловая структура компьютера.
- •Текстовые редакторы и процессоры. Объекты, параметры, типовые действия над объектами тр и тп.
- •Организация работы с массивами в языках программирования. Сортировка данных.
- •2. Вывод массива.
- •4. Поиск элементов по заданному условию.
- •6. Сортировка массивов.
- •3) Сортировка "подсчетом"
- •Обработка графической информации. Прикладные программы, характеристики.
- •Программное управление эвм. Операционная система. Программы-оболочки. Операционная среда.
- •Утилиты сервисного обслуживания (усо)
- •Утилиты расширения функциональности
- •Информационные утилиты
- •Работа с дисковыми файлами в языках программирования.
- •Языки программирования. Интерпретаторы и компиляторы.
- •История развития эвм. Поколения компьютеров.
- •Организация циклов в языках программирования.
- •Понятие информации и информатики. Информационные процессы.
- •Электронные таблицы. Объекты, параметры. Данные, типы. Типовые действия над объектами эт.
- •Условный, безусловный переход, выбор в языках программирования.
- •Модели данных. Базы данных. Системы управления базами данных.
- •Представление информации в памяти компьютера, Кодирование и измерение информации.
- •Типы данных в языках программирования. Числовые и строковые переменные и операции с ними.
- •Методика обучения темы «Компьютерная графика».
- •Методика обучения темы «Обработка текстовой информации».
- •Егэ по информатике. Подготовка и содержание.
- •Методика обучения темы «Электронные таблицы».
- •Профильное обучение информатике.
- •История формирования информатики как школьного предмета.
- •Стандарт школьного образования по информатике. Назначение и функции общеобразовательного стандарта в школе.
- •Методика обучения темы «Программное обеспечение эвм».
- •Методика обучения темы «Сетевые информационные технологии».
- •Методика обучения темы «Архитектура эвм».
- •Методика обучения темы «Базы данных и информационные системы»
- •Методика обучения темы «Языки программирования».
- •Программное обеспечение по курсу информатики. Анализ учебных и методических пособий.
- •Методика обучения темы «Алгоритмы и исполнители».
- •Методика обучения темы « Информация, информационные процессы».
- •Цели и задачи школьного курса информатики.
- •Элективные курсы.
- •Методика обучения темы «Компьютерное моделирование».
Понятие алгоритма, его основные свойства. Способы представления алгоритмов.
Алгоритм – это заранее заданное понятное и точное предписание возможному исполнителю совершить опр. последовательность действий за конечное число шагов. Исполнитель алгоритма - это некоторое абстрактная или реал система способная выполнить действия предписанные алгоритмом.
Понятие исполнителя невозможно определить с помощью какой-либо формализации. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ).
Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т. е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создан, мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат.
Свойства:
1.однозначность – четкое предписание что и как делать в каждой конкретной ситуации. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно 2.универсальность – применяемость данного алгоритма к решению любой задачи данного типа 3.результативность – отсутствие зацикливаний. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует - тоже результат. 4. массовость. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа. 5.дискретность – алгоритм должен быть разбит на отдельные достаточно простые действия. 7.понятность. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может.
Способы записи:
1.словесная – ориентирована на исполнителя человека. Команды записываются на обычном языке. «+» – понятность. « - » - неоднозначность, избыточность, отсутствие наглядности связей.
2.схемы программ – графическое отображение алгоритма согласно утвержденным стандартам (блок схемы). Каждое действие записывается внутри блоков. Блоки соединяются линиями, кот-е указывают последовательность действий.
Блок-схема - это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов
На рис. изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу.
Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 2), имеющих особое значение для практики алгоритмизации.
На рис. изображены следующие блок-схемы: а - композиция, или следование; б - альтернатива, или развилка, в и г - блок-схемы, каждую из которых называют итерацией, или циклом (с предусловием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя, В - это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями.
На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки
3.псевдокоды – занимают промежуточное место между естественным и формальным языком.
Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной. Используют некоторые служебные слова, которые подчеркиваются. АЛГ – название алгоритма; НАЧ; …; КОН; ДЛЯ i ОТ 1 ДО 100 ВЫП; ЕСЛИ ТО ИНАЧЕ; Нц Кц 4.языки программирования.На практике основной исполнитель алгоритма – ЭВМ, поэтому запись алгоритма должна быть абсолютно точна, т.е. язык должен быть формализован. Его наз языком программирования, а запись алгоритма на таком языке – программой.
По синтаксису можно разделить на классы:
машинные – воспринимаемые аппаратной частью компьютера (машинные коды – двоичная запись). машинно – ориентированные – отражают стр-ру кон кретного типа компа – ассемблеры. алгоритмические – не зависящие от архитектуры компа (Pascal, Basic, Фортран). Проги транслируются с языка высокого уровня на машинный.
процедурно – ориентированные – имеется возможность описания прог как совокупности процедур подпрограмм.
проблемно – ориентированные – решают определенный класс задач (Prolog).
Классификация алгоритмов:
1.линейные – команды выполняются в естественном порядке, как они записаны – сверху вниз. Следование - самая важная из структур. Она означает, что действия могут быть выполнены друг за другом,
2.разветвленные – в этих алгоритмах в зависимости от некоторых условий выполняются те или иные действия. Ветвление - это структура, обеспечивающая выбор между
двумя альтернативами.Выполняется проверка, а затем выбирается один из путей. Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.
3.циклические – для многократно повторяемых действий используют специальную конструкцию – цикл. Команды цикла содержат условия для определения количества повторов. Существует три типа циклов:
счетчик (с параметром) – когда заранее определено количество повторов.
с предусловием – сначала проверяется условие. Если оно выполняется, то затем выполняется действие в теле цикла. Если условие не выполняется, то цикл завершается (будет выполняться следующий оператор после цикла).
с постусловием – условие проверяется после действий в теле цикла, и если это условие выполняется, то происходит выход из цикла.
Формализация алгоритма, т.е. строгое его описание. Подходы к формализации понятия «алгоритм»:1) теория конечных и бесконечных автоматов; 2) теория вычислимых (рекурсивных) ф-й; 3) -исчисление Черча. Все эти подходы оказались эквивалентными. Главная цель формализации-подойти к решению проблемы алорит-ой разрешимости различ.мат.задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи.Рассмотрим формализацию в теории автоматов на примере машин Поста и Тьюринга.
Машина Поста. Абстрактные машины Поста и Тьюринга были предложены не зависимо друг от друга в 1936г.америк.мат-ом Эмилем Постом и англ.мат-ом Алланом Тьюрингом. Эти машины универсал.исполнители,полностью детерминированные, позвол.вводить нач.данные и после вып-я программ читать рез-т.
Машина Поста предст-ет собой беск.ленту, раздел.на одинак.клетки, каждая из кот.м.б.либо пустой либо заполненной меткой «V», и головки, кот. Может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если ее там ранее не было, стирать если была, проверять наличие в клетки метки. Команда машины Поста n K m, n порядковый номер команды, K действие, вып-е головкой, m номер след команды. 6 команд машины Поста: 1)Движение головки на 1 клетку вправо n m, 2) влево n m,3) нанесение метки, над кот.нах-ся головка n М m, 4) стирание n С m, 5) проверка наличия метки в клетке, над кот.нах-ся головка, если метка отсутствует, управление передается команде м1, иначе м2,6) остановка машины n Стоп n . Программой для машины Поста будем называть непустой список команд, такой что:1)на n месте команда с номером n,2) номер m каждой команды совпадает с номером к-либо команды из списка.
Рассмотрим представление чисел на ленте машины Поста. Число к представляется на ленте идущими подряд к+1 метками (одна метка означает число 0). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Н-р: запись чисел 2 и 3 на ленте:
|
v |
v |
|
v |
v |
v |
|
|
|
|
Cоставим программу для прибавления к произвольному числу единицы. Пусть на ленте записано одно число и головка нах-ся над одной из клеток, в кот нах метка, принадлежащая этому числу. Для решения задачи можно переместить головку влево( или вправо) до первой пустой клетки, а затем нанести метку. Программа:
Машину Поста можно рассматривать как упрощенную модель ЭВМ. Они имеют: 1) неделимые носители информации(клетки-биты), кот.м.б.заполненными или не заполненными,2) ограниченный набор элемент.д-й – команд, каждая из кот.вып-ся за один такт – шаг. Обе машины работают на основе программы. Однако в машине поста инф-я расп-ся линейно и читается подряд, а в ЭВМ можно читать инф-ю по адресу и т.д.
Машина Тьюринга.
МТ есть мат.машина, а не физич..Это такой же мат.обьект как ф-я, производная,группа. И так же как др.мат.понятия МТ моделирует некие реал.процессы. МТ удобно представлять в виде автомат.раб.устройства. Она состоит из ленты, разбитой на ячейки, потенциально беск.в обе стороны. В каждую ячейку м.б.вписан только 1 символ из конечного мн-во символов – алфовит МТ А={a0,a1,…,aT}. Имеется упр.головка МТ способная передвигаться по ленте вправо и влево, в результате работы 1 такта на 1 ячейку.В каждый дискрет.момент времени устройство, находясь в нек.состоянии обозревает содержимое одной ячейки ленты, протягиваемой через устройство и делает 1 шаг, заключ.в том,что устр-во переходит в новое состояние, изменяет содержимое обозреваемой ячейки и переходит к обозреванию след.ячейки. Шаг МТ осущ-ся на основе предписанной команды. Совокупность всех команд предст-ет программу МТ. МТ располагает конеч.числом знаков, символов, букв, образ.внеш.алфавит - А={a0,a1,…,aT}. В каждую ячейку обозреваемой ленты в каждый дискрет.момент времени может быть записан 1 символ из А. Удобно считать, что среди букв внеш.алфавита имеется «пустая буква», и она записана в пуст.ячейку ленты. В каждый момент времени МТ способна находится в одном состоянии из конечного числа внут.состояний, совокупность кот.наз-ся алфавитом внут.состояний-q0,q1,…,qs. Среди состояний выд-ся 2 – начальное q1, заключительное – состояние остановки q0. Работа МТ опред-ся программой. Программа состоит из команд, каждая команда представляет выражение одного из след видов: 1)qiajqsat, 2) qiajqsatП , 3) qiajqsat Л.
Команда 1:находясь в состоянии qi и обозревая ячейку с символом aj и напечатать в данной ячейке символ at . Команда 2(3): находясь в состоянии qi и обозревая ячейку с символом aj и напечатать в данной ячейке символ at и сдвинуться на 1 ячейку вправо(влево). Под к-конфигурацией понимается изображение ленты с информацией сложившейся на ней к началу к-такта с указанием того, какая ячейка обозревается в этот такт и в каком состоянии нах-ся машина. Будем говорить, что непустое слово L в алфавите А воспринимается машиной в стандарт.положении, если это слово записано в послед.ячейках ленты, все другие ячейки пусты и машина обозревает крайнюю справа ячейку из тех, в которых записано слово L. Стандартное положение назовенм начальным , если МТ воспринимает слово в стандартном положении нах-ся в нач.состоянии q1 .
Пример: Дана МТ с внеш.алфавитом А={a0,1}, внут.алфавитом – Q={q0,q1} и программой в виде системы команд: 1)q1a0q01, 2) q11q11 П. Определить в какое слово МТ переработает слово 1a0111, если обозревается ячейка 4 слева.
|
1 |
a0 |
1 |
1 |
a0 |
a0 |
1 |
|
|
|
1 |
a0 |
1 |
1 |
a0 |
a0 |
1 |
|
|
|
1 |
a0 |
1 |
1 |
1 |
a0 |
1 |
|
|