Урок Тема: Понятие алгоритма. Свойства алгоритма - gozda.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Урок Тема: Понятие алгоритма. Свойства алгоритма - страница №1/1

Еловикова Светлана Серафимовна, учитель информатики Бийского лицея г. Бийск Алтайского края

E-mail: ess@liceum.secna.ru



6 класс

ЛогоМиры


Урок 1.

Тема: Понятие алгоритма. Свойства алгоритма.



Исполнитель. Формальный, неформальный исполнитель. Система команд исполнителя.
Алгоритм – план решения задачи
Алгоритм – базовое понятие информатики и, как всякое базовое понятие, не имеет строгого определения.
Алгоритм – упорядоченная последовательность действий, выполнение которых приведет к решению задачи.
Понятие алгоритма нельзя рассматривать изолированно, оно связано с понятием исполнителя, среды.
Решение любой задачи всегда состоит из выполнения какой-либо последовательности действий. Разработка плана решения задачи – процесс творческий. Реализацию уже имеющегося плана действий можно поручить объекту или субъекту, называемому формальным исполнителем или просто исполнителем.
ЗАДАНИЕ ПО ИНФОРМАТИКЕ. >>
ЯЗЫКИ ПРОГРАММИРОВАНИЯ, БЛОК-СХЕМА АЛГОРИТМА. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ. Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгоритмическом языке (языке программирования). Остановимся на графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное отображение управления в нем. Прежде всего определим понятие блок-схемы. Блок-схема - это ориентированный граф, указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного из трех типов (рис. 1.1.). Рис. 1.1. Три типа вершин графа На рис. 1.1. изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -). Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 1.2.), имеющих особое значение для практики алгоритмизации. Рис. 1.2.. Основные алгоритмические структуры На рис. 1.2. изображены следующие блок-схемы: а - композиция, или следование; б - альтернатива, или развилка, в и г - блок-схемы, каждую из которых называют итерацией, или циклом (с предусловием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя, В - это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями. Блок-схема «альтернатива» может иметь и сокращенную форму, в которой отсутствует ветвь S2 (рис. 1.3., а). Развитием блок-схемы типа альтернатива является блок-схема «выбор» (рис. 1.3., б). Рис. 1.3.. Развитие структуры типа «альтернатива»; о) - неполная развилка; б) - структура «выбор»

Теоретический материал >>
Теоретический материал Алгоритм двоичного (бинарного) поиска Алгоритм двоичного поиска можно использовать для поиска элемента с заданным свойством только в массивах, упорядоченных по этому свойству. Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по возрастанию или по убыванию. Идея алгоритма состоит в том, что массив каждый раз делится пополам и выбирается та часть, где может находиться нужный элемент. Деление продолжается пока часть массива для поиска больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска. Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой. В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка логарифма N по основанию 2, где N-количество элементов массива. ПРИМЕР: Поиск в упорядоченном по возрастанию массиве первого вхождения числа X. program Poisk4; var A:array[1..100] of integer; N,X,left,right:integer; begin read(N); {N

Понятие множества >>
Понятие множества. Равенство и включение множеств. Пустое и универсальное множества. Булевы операции, их свойства. Булеан множества. Упорядоченные пары и кортежи. Декартово произведение, свойства. Бинарные отношения на множестве. Основные свойства бинарных отношений. Примеры. Основные типы бинарных отношений: эквивалентность, частичный порядок, линейный порядок. Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Связь отношения эквивалентности и разбиения. Матрица бинарного отношения. Связь свойств бинарного отношения и свойств его матрицы. Связь с операциями над булевыми матрицами. Отображения (функции) как отношения. Обратное отображение как отношение. Инъективность, сюръективность, биективность. Ядро отображения. Отношение частичного порядка. Отношение покрытия. Диаграммы ч.у.м. Минимальные и максимальные, наименьшие и наибольшие элементы ЧУМ, их свойства. Изоморфное вложение ч.у.м. Теорема о представлении ч.у.м. Условия фундированности, индуктивности и артиновости. Как эти условия связаны между собой? Вполне упорядоченные множества. Принцип полной индукции. Ординалы. Ординальная сумма и ординальное произведение. Аксиома выбора. Теорема Цермелло. Мощность множества. Отношение равномощности. Кардинальное число. Сравнение кардинальных чисел. Теорема Кантора-Бернштейна. Бесконечные множества. Критерий Дедекинда бесконечности множества. Счетные множества. Теорема о счетных множествах. Континуальные множества. Теорема о континуальных множествах. Теорема Кантора о булеане. Иерархия кардиналов. Континуум-гипотеза. Парадоксы теории множеств. Способы их избежать. Сочетания. Бином Ньютона. Треугольник Паскаля. Свойство симметрии биномиальных коэффициентов. Размещения без повторений, с повторениями. Перестановки без повторений, с повторениями. Полиномиальные коэффициенты. Перестановки как функции. Орбиты элементов. Циклы. Теорема о разложении на циклы. Симметрические группы. Группа симметрий квадрата. Изоморфизм групп. Теорема Кэли. Числа Каталана. Число наддиагональных путей в квадратной решетке. Правильные расстановки скобок, триангуляции выпуклых многоугольников. Принцип включения-исключения. Число сюръекций. Разбиения: числа Стирлинга второго рода, числа Белла. Рекуррентные соотношения. Решение линейных рекуррентных соотношений с постоянными коэффициентами. Числа Фибоначчи. Конкатенация и ее свойства. Коммутирующие слова. Полугрупповой код. Свободная полугруппа. Гомоморфизм. Теорема о гомоморфных образах свободной полугруппы.

Программа вступительнОГО испытаниЯ >>
ПО ИНФОРМАТИКЕ И ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫМ ТЕХНОЛОГИЯМ в ФГОУ ВПО «Госуниверситет – УНПК» в 2011 году ОСНОВЫ ИНФОРМАТИКИ Понятие информации. Носители информации. Измерение информации.Энтропия. Меры информации: структурная, статистическая, семантическая. Обработка аналоговой и цифровой информации. Кодирование информации. Основные свойства информации. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ Основные понятия алгебры логики. Символьная логика. Элементарные логические функции. Законы алгебры логики. Преобразование и упрощения логических выражений. Основные понятия алгебры логики. Свойства элементарных функций алгебры логики Совершенные нормальные формы. Совершенные нормальные формы функций алгебры логики. Аналитическое представление функций алгебры логики. Упрощение логических функций. Системы функций алгебры логики. Формы представления числовой информации. Представление чисел с фиксированной и плавающей запятой, отрицательных чисел. Правила двоичной арифметики. Выполнение арифметических операций над числами с фиксированной запятой: сложение и вычитание с использованием двоичных сумматоров прямого, дополни­тельного и обратного кода. Системы счисления: двоичная, восьмеричная и шестнадцатеричная. Методы перевода чисел из одной системы счисления в другую ОСНОВЫ АЛГОРИТМИЗАЦИИ Понятия алгоритма. Свойства алгоритмов. Способы представления алгоритмов. Этапы подготовки и решения задач на ЭВМ. Описание линейных, циклических и разветвляющихся алгоритмов. Описание ветвлений с помощью схем алгоритмов и программ. ОСНОВЫ ПРОГРАММИРОВАНИЯ

Вопросы к итоговой контрольной по общей психологии (1 курс, 2 семестр) >>
Автор Название произведения >>
Автор Название произведения Класс Форма (обзорный урок, отдельный урок, внеклассное мероприятие и др.) и тема1 изучения М. Успенский «Там, где нас нет» 10 отдельный урок Д. Рубина «Астральный полет души на уроке физики» 9 отдельный урок М. Веллер «Памятник Дантесу» 9 внеклассное чтение В Токарева «Я есть, ты есть, он есть…» 11 отдельный урок А.Жвалевский, Е. Пастернак «Время всегда хорошее» 6 отдельный урок А.Жвалевский, Е. Пастернак «Шекспиру и не снилось» 7 отдельный урок С. Лукьяненко «Мальчик и Тьма» 7 отдельный урок Л. Петрушевская Отдельные рассказы из сборника рассказов «Пограничные сказки про котят» 7-11 внеклассное чтение Э. Веркин «Книга советов по выживанию в школе» 5-7 для самостоятельного прочтения В. Пелевин «Generation П» 11 интегрированный урок с историей Сведения о составителе: ФИО – Ноженкина Ольга Сергеевна; Место работы, должность – информационно-методический отдел издательства «Просвещение», ведущий методист; Профессиональные отличия – кандидат психол. наук; E-mail – farmer77@mail..ru

Опорный конспект лекции >>
ФСО ПГУ 7.18.2/07 Министерство образования и науки Республики Казахстан Павлодарский государственный университет им. С. Торайгырова Факультет физики, математики и информационных технологий Опорный конспект лекции по дисциплине «Интеллектуальные информационные системы» Для специальности 050703 «Информационные системы» Павлодар Лист утверждения опорного конспекта лекции Ф ФСО ПГУ 7.18.2/11 УТВЕРЖДАЮ Декан факультета ФМ иИТ _____________ Тлеукенов С.К. «__»_________20__г. Составитель: старший преподаватель Аканова А.С. Кафедра информатики и информационных систем Опорный конспект лекции по дисциплине Интеллектуальные информационные системы для специальности 050703 «Информационные системы» форма обучения: дневная на базе ОСО, СПО, ВПО Опорный конспект лекции разработан на основании рабочей программы дисциплины Рекомендована на заседании кафедры от «__» ____________200 протокол №__ Зав. кафедрой __________________________Ж.К. Нурбекова (подпись, Ф.И.О.) Одобрено методическим советом факультета ФМиИТ «______»____________200__г., протокол № ___________________ Председатель МС___________________ А.Т.Кишубаева (подпись) Лекция 1. Понятие интеллектуальной информационной системы (ИИС), основные свойства. Классификация ИИС. Цель: Познакомить с понятиями интеллектуальной системы, со свойствами ИИС, с классификацией.

Прин­цип ак­тив­но­сти в пси­хо­ло­гии и фи­зио­ло­гии. Свойства активных форм поведения. Ор­га­ни­за­ция, ре­гу­ля­ция и уров­ни по­строе­ния дви­же­ний (Бер­н­штейн). Понятие сенсорных коррекций. Принцип рефлекторного кольца. Основные закономерности и этапы формирования двигательных навыков (по Бер­н­штейну). Психофизическая и психофизиологическая проблемы: формулировки и основные варианты решения. Проблема локализации психических функций. Высшая психическая функция как функциональная система. Явление мотивации. Проблема локализации причин действия. Фундаментальная ошибка атрибуции: различия в объяснении своего и чужого поведения. Понятия потребности, мотива, мотивации. Личностные и ситуационные детерминанты поведения. Основные теоретические подходы к объяснению поведения. Виды и возможные основания классификации мотивов. Пирамида потребностей А. Маслоу. Классификации мотивов в концепциях У. МакДауголла и Г. Мюррея. Внешняя и внутренняя мотивация. Связь мотивации с деятельностью. Общая характеристика эмоциональной сферы психики. Три стороны эмоционального процесса. Связь эмоций с потребностями и деятельностью. Функции эмоциональных явлений. Виды эмоциональных явлений, возможные критерии их классификации. Эмоциональные состояния (стресс, фрустрация, эмпатия). Понятие воли. Признаки волевых явлений. Различение произвольной и волевой регуляции деятельности. Структура волевых актов. Общая характеристика познавательной сферы человека. Специфические и неспецифические («сквозные») познавательные процессы: краткая характеристика. Понятия рецептора и рецепции. Функции рецепции. Возможные критерии классификации рецепторов. Общее представление об ощущении. Свойства и возможные критерии классификации ощущений. Свойства перцептивного образа. Двойственная природа перцептивного образа. Соотношение чувственной основы и предметного содержания образа. Виды и функции образных явлений. Понятие внимания. Основные феномены внимания. Критерии внимания и невнимания. Метафоры внимания. Свойства внимания. Способы их измерения. Ошибки и нарушения внимания. Виды внимания и возможности их классификации. Онтогенетическое развитие внимания и памяти в теории Выготского. Понятие памяти. Основные метафоры памяти. Круг явлений памяти. Свойства памяти. Виды памяти и возможности их классификации. Мнемотехника и случаи феноменальной памяти. Амнезии и их виды. Забывание в повседневной жизни.

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

Инструкцию, записанную на формальном языке, называют программой.


Общая схема знакомства с исполнителем


Исполнитель





Среда «обитания»



СКИ



КОМАНДЫ

КАК ОТДАЮТСЯ?

КАК ВЫПОЛНЯЮТСЯ?

КОГДА Не могу?





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

В разных учебниках выделяют разные наборы свойств.


Дискретность (алгоритм исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

Детерминированность (определенность, однозначность, точность).

Результативность, конечность.

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

Массовость (возможность с помощью одного и того же алгоритма решать однотипные задачи)

Урок 2.


Опрос.


  1. Что такое алгоритм?
    (Алгоритм – упорядоченная последовательность действий, выполнение которых приведет к решению задачи.

  2. Что такое система команд исполнителя?
    СКИ - это набор команд, которые исполнитель может понять и выполнить.

  3. Какие способы записи алгоритма существуют?
    (блок-схема, построчная запись)

  4. Что такое программа?
    (Инструкция для исполнителя, записанная на формальном языке)

  5. Перечислите свойства алгоритма.
    (Дискретность, детерминированность, результативность, конечность, понятность, эффективность, элементарность шагов, массовость).

Тема: Знакомство со средой ЛогоМиры Интерфейс среды. Исполнитель Черепашка.



Непосредственный режим работы. Команды управления. Команды с параметром и без параметра


Команда

Действие исполнителя

ВПЕРЕД <число шагов>

Черепашка движется на указанное число шагов в том направлении, куда она смотрит

НАЗАД <число шагов>

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

НАПРАВО <число градусов>

Черепашка поворачивается по часовой стрелке (через правую лапку) на указанное число градусов

НАЛЕВО <число градусов>

Черепашка поворачивается против часовой стрелки (через левую лапку) на указанное число градусов

ПП

Черепашка поднимает перо, чтобы не оставлять след

ПО

Черепашка опускает перо для рисования

СГ

Сотри графику (рисунок на рабочем поле стирается)

ДОМОЙ

Черепашка возвращается в исходное положение (в центр экрана, головой вверх)



Правила написания команд

  • Правило «одного слова»: между буквами в команде не должно быть пробелов;

  • Правило «пробела»: если в команде есть входной параметр, то он отделяется от названия команды пробелом; если на одной строке пишется несколько команд, то они отделяются друг от друга пробелами.


Практические задания: рисование букв, цифр.
Урок 3.

Тема: Работа с листом программ

Лабораторная работа



  1. Включить компьютер.

  2. Загрузить среду ЛогоМиры.

  3. В непосредственном режиме составить алгоритм рисования собачки.




  1. Установить курсор в начало первой строки алгоритма.

  2. При помощи клавиш Shift и выделить все команды алгоритма.

  3. Скопировать выделенный фрагмент в буфер обмена.

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



  1. Перейти в программный режим работы.

Для этого нужно выбрать пункт горизонтального меню Листы, затем пункт ниспадающего меню Программы



  1. Вставить фрагмент из буфера обмена.

Для этого нужно выбрать пункт горизонтального меню Редактор, затем пункт ниспадающего меню Верни





  1. Оформить алгоритм рисования собачки в виде программы с именем Собачка

ЭТО Собачка




– заголовок программы







– тело программы

КОНЕЦ




– признак завершения программы

10. Сохранить файл в свою личную папку с именем Собачка

Для этого нужно выбрать пункт горизонтального меню Файл, затем пункт ниспадающего меню Сохрани проект под именем

Опрос.

Вариант 1




Вариант 2


1. По какой команде Черепашка пятится назад на 60 шагов, не поворачивая головы?




1. По какой команде Черепашка передвинется на 100 шагов в том направлении, куда она смотрит?

2. По какой команде Черепашка поворачивается через левую лапку (против часовой стрелки) на 60 градусов?




2. По какой команде Черепашка поворачивается через правую лапку (по часовой стрелке) на 45 градусов?

3. По какой команде Черепашка поднимает перо, чтобы не оставлять след?




3. По какой команде Черепашка выпускает перо для рисования?

4. По какой команде рисунок на рабочем поле стирается?




4. По какой команде Черепашка возвращается в центр экрана, головой кверху?

5. После выполнения какой из перечисленных ниже команд появится сообщение об ошибке: «Не хватает входных данных?»

    1. домой

    2. вперед

    3. НАЗАД 200

    4. направо 90




5. После выполнения какой из перечисленных ниже команд появится сообщение об ошибке: «Не хватает входных данных?»

  1. назад

  2. вперед 100

  3. НАЗАД 200

  4. налево 45


Вариант 1


(ответы)



Вариант 2


(ответы)

1. НАЗАД 60




1. ВПЕРЕД 100

2. НАЛЕВО 60




2. НАПРАВО 45

3. ППП




3. ПО

4. СГ




4. ДОМОЙ

5. b. вперед





5. a. назад