Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Алгоритмическое решение задач, анализ алгоритмической сложности
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Информатика

Алгоритмическое решение задач, анализ алгоритмической сложности

библиотека
материалов
Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презен...
Тема: Алгоритмическое решение задач, анализ алгоритмической сложности
Цель: Познакомить с понятием алгоритм и его свойствами, изучить основные спос...
План Лекции: 1. Этапы решения задач на компьютере 2. Основные вычислительные...
Задачи Лекции: 1. Рассмотреть этапы решения задач на компьютере 3. Выявить ос...
Этапы решения задач на компьютере
Алгоритм - это метод (способ) решения задачи, записанный по определенным прав...
Этапы решения задач на компьютере Постановка задачи Пpогpаммиpование Разработ...
Этапы решения задач на компьютере 1. Постановка задачи - сбор информации о за...
Этапы решения задач на компьютере 2. Анализ и исследование задачи, модели - а...
Этапы решения задач на компьютере 3. Разработка алгоритма - выбор метода прое...
Этапы решения задач на компьютере 4. Пpогpаммиpование - выбор языка программи...
Этапы решения задач на компьютере 5. Тестирование и отладка - синтаксическая...
Этапы решения задач на компьютере 6. Анализ результатов решения задачи - Анал...
Этапы решения задач на компьютере 7. Сопровождение программы - доработка прог...
Процесс разработки программы Разработка программы = Изготовление + Проверка и...
Отладка программы - это процесс поиска и устранения ошибок в программе, произ...
Отладка и тестирование: при отладке происходит локализация и устранение синта...
Тест = Некоторая совокупность исходных данных + Точное описание соответствующ...
2 Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга
Задача точного определения понятия алгоритма была решена в 30-х годах в работ...
Типы алгоритмов Алгоритмические машины Функции вычислимые алгоритмом Исчисления
Алгоритмические машины Алгоритм представляется набором правил команд процессо...
Функции вычислимые алгоритмом В этом случае сам алгоритм не определяется форм...
Исчисления Представляют собой формальные системы, в которых определены поняти...
Структура алгоритма
Процессорная структура Во всех теоретических конструкциях алгоритмов и больши...
Структуры данных Структура данных это способ организация записи, хранения и и...
Информационная структура алгоритма Структура функций есть описание конструиро...
Логическая структура алгоритма Логическая структура алгоритма суть описание о...
Машина Тьюринга
– алфавит рабочих символов – алфавит состояний – алфавит действий - набор пра...
Интерпретация Машины Тьюринга Процессор – в МТ называется управляющей головко...
Интерпретация Машины Тьюринга Процесс вычислений происходит по тактам в каждо...
Интерпретация Машины Тьюринга МТ – останавливается в двух случаях: •	удачное...
Интерпретация Машины Тьюринга Процесс «вечной» работы МТ означает для порожда...
Интерпретация Машины Тьюринга Список правил для МТ не упорядочен. Поиск прави...
Машина Тьюринга Логическую структуру алгоритма (ЛСА), содержащую все возможны...
Машина Тьюринга Граф переходов МТ есть направленный бинарный граф S – вершины...
Н.Вирт. Алгоритмы и структуры данных: Пер. с англ. Д.Б.Подшивалова. – М.: Мир...
??? Что такое алгоритм? Какие этапы решегия задач на компьютере существуют? П...
Спасибо за Внимание! Спасибо за Внимание! Спасибо за Внимание!
42 1

Описание презентации по отдельным слайдам:

№ слайда 1 Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презен
Описание слайда:

Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презентации: ст. преподаватель кафедры ИиМ Ермагамбетова Гульмира Нурлановна

№ слайда 2 Тема: Алгоритмическое решение задач, анализ алгоритмической сложности
Описание слайда:

Тема: Алгоритмическое решение задач, анализ алгоритмической сложности

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

Цель: Познакомить с понятием алгоритм и его свойствами, изучить основные способы записи алгоритмов

№ слайда 4 План Лекции: 1. Этапы решения задач на компьютере 2. Основные вычислительные
Описание слайда:

План Лекции: 1. Этапы решения задач на компьютере 2. Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга

№ слайда 5 Задачи Лекции: 1. Рассмотреть этапы решения задач на компьютере 3. Выявить ос
Описание слайда:

Задачи Лекции: 1. Рассмотреть этапы решения задач на компьютере 3. Выявить основные типы алгоритма 2. Показать структуру алгоритма 4. Рассмотреть машину Тьюринга

№ слайда 6 Этапы решения задач на компьютере
Описание слайда:

Этапы решения задач на компьютере

№ слайда 7 Алгоритм - это метод (способ) решения задачи, записанный по определенным прав
Описание слайда:

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

№ слайда 8 Этапы решения задач на компьютере Постановка задачи Пpогpаммиpование Разработ
Описание слайда:

Этапы решения задач на компьютере Постановка задачи Пpогpаммиpование Разработка алгоритма Сопровождение программы

№ слайда 9 Этапы решения задач на компьютере 1. Постановка задачи - сбор информации о за
Описание слайда:

Этапы решения задач на компьютере 1. Постановка задачи - сбор информации о задаче; - фоpмулиpовка условия задачи; - определение конечных целей решения задачи; - определение формы выдачи результатов; - описание данных (их типов, диапазонов величин, структуры и т.п. ).

№ слайда 10 Этапы решения задач на компьютере 2. Анализ и исследование задачи, модели - а
Описание слайда:

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

№ слайда 11 Этапы решения задач на компьютере 3. Разработка алгоритма - выбор метода прое
Описание слайда:

Этапы решения задач на компьютере 3. Разработка алгоритма - выбор метода проектирования алгоритма; - выбор формы записи алгоритма (блок-схемы, псевдокод и др.); - выбор тестов и метода тестирования; - проектирование алгоритма.

№ слайда 12 Этапы решения задач на компьютере 4. Пpогpаммиpование - выбор языка программи
Описание слайда:

Этапы решения задач на компьютере 4. Пpогpаммиpование - выбор языка программирования; - уточнение способов организации данных; - запись алгоритма на выбранном языке пpогpаммиpования.

№ слайда 13 Этапы решения задач на компьютере 5. Тестирование и отладка - синтаксическая
Описание слайда:

Этапы решения задач на компьютере 5. Тестирование и отладка - синтаксическая отладка; - отладка семантики и логической стpуктуpы; - тестовые расчеты и анализ результатов тестирования; - совершенствование пpогpаммы.

№ слайда 14 Этапы решения задач на компьютере 6. Анализ результатов решения задачи - Анал
Описание слайда:

Этапы решения задач на компьютере 6. Анализ результатов решения задачи - Анализ и исследование задачи, модели - Разработка алгоритма; - Пpогpаммиpование - Тестирование и отладка.

№ слайда 15 Этапы решения задач на компьютере 7. Сопровождение программы - доработка прог
Описание слайда:

Этапы решения задач на компьютере 7. Сопровождение программы - доработка программы для решения конкретных задач; - составление документации к решенной задаче, к математической модели, к алгоритму, к пpогpамме, к набору тестов, к использованию.

№ слайда 16 Процесс разработки программы Разработка программы = Изготовление + Проверка и
Описание слайда:

Процесс разработки программы Разработка программы = Изготовление + Проверка и исправление

№ слайда 17 Отладка программы - это процесс поиска и устранения ошибок в программе, произ
Описание слайда:

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

№ слайда 18 Отладка и тестирование: при отладке происходит локализация и устранение синта
Описание слайда:

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

№ слайда 19 Тест = Некоторая совокупность исходных данных + Точное описание соответствующ
Описание слайда:

Тест = Некоторая совокупность исходных данных + Точное описание соответствующих этим данным всех результатов работы программы в том виде, в котором эти результаты должны быть выданы.

№ слайда 20 2 Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга
Описание слайда:

2 Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга

№ слайда 21 Задача точного определения понятия алгоритма была решена в 30-х годах в работ
Описание слайда:

Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга. Формы на основе понятия рекурсивной функции на основе описания алгоритмического процесса

№ слайда 22 Типы алгоритмов Алгоритмические машины Функции вычислимые алгоритмом Исчисления
Описание слайда:

Типы алгоритмов Алгоритмические машины Функции вычислимые алгоритмом Исчисления

№ слайда 23 Алгоритмические машины Алгоритм представляется набором правил команд процессо
Описание слайда:

Алгоритмические машины Алгоритм представляется набором правил команд процессора, последовательность выполнения которых управляет состоянием памяти. Основные АМ, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов были предложены в ХХ в. • Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. • Машина Поста (МР) предложена Постом в 1937 г. • Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.

№ слайда 24 Функции вычислимые алгоритмом В этом случае сам алгоритм не определяется форм
Описание слайда:

Функции вычислимые алгоритмом В этом случае сам алгоритм не определяется формально, а существует как бы в виде «всем понятной механической процедуры». Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г.

№ слайда 25 Исчисления Представляют собой формальные системы, в которых определены поняти
Описание слайда:

Исчисления Представляют собой формальные системы, в которых определены понятия правильно построенных формул (ППФ) и конечного набора правил преобразования ППФ. Алгоритм понимается как цепочка применения последовательности правил к начальной ППФ для получения вывода конечной ППФ. В аксиоматических формальных системах конечные ППФ всегда выводятся из ППФ, которые называются аксиомами. - Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г. - -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г. Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г

№ слайда 26 Структура алгоритма
Описание слайда:

Структура алгоритма

№ слайда 27 Процессорная структура Во всех теоретических конструкциях алгоритмов и больши
Описание слайда:

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

№ слайда 28 Структуры данных Структура данных это способ организация записи, хранения и и
Описание слайда:

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

№ слайда 29 Информационная структура алгоритма Структура функций есть описание конструиро
Описание слайда:

Информационная структура алгоритма Структура функций есть описание конструирования функции от функций из базовых. Функция может быть определена двумя способами: а) структурой (структурным описанием) б) процедурно (последовательностью базовых операций). Языки программирования содержат оба способа задания функций.

№ слайда 30 Логическая структура алгоритма Логическая структура алгоритма суть описание о
Описание слайда:

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

№ слайда 31 Машина Тьюринга
Описание слайда:

Машина Тьюринга

№ слайда 32 – алфавит рабочих символов – алфавит состояний – алфавит действий - набор пра
Описание слайда:

– алфавит рабочих символов – алфавит состояний – алфавит действий - набор правил вида – , Машина Тьюринга

№ слайда 33 Интерпретация Машины Тьюринга Процессор – в МТ называется управляющей головко
Описание слайда:

Интерпретация Машины Тьюринга Процессор – в МТ называется управляющей головкой (УГ). Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ ячейка может быть пустой.

№ слайда 34 Интерпретация Машины Тьюринга Процесс вычислений происходит по тактам в каждо
Описание слайда:

Интерпретация Машины Тьюринга Процесс вычислений происходит по тактам в каждом ti УГ выбирает и выполняет правила Если УГ находится в состоянии Si и указатель головки стоит напротив ячейки, где записан символ аi (видит аi), то головка заменяет его на символ аj, переходит в состояние Sj, производит действие dj (Л – сдвигается на ячейку влево, П – сдвигается на ячейку вправо, Н – остается на месте, stop – МТ останавливается). В начальном такте (t0) УГ находится всегда в состоянии S0, «смотрит» на некоторую ячейку ленты и «ждет» внешнего сигнала «пуск», чтобы начать работу.

№ слайда 35 Интерпретация Машины Тьюринга МТ – останавливается в двух случаях: •	удачное
Описание слайда:

Интерпретация Машины Тьюринга МТ – останавливается в двух случаях: • удачное завершение (фиксация результата), выполняется команда (ak, Sk, stop) переводит УГ в конечное состояние и происходит остановка машины; • неудачное завершение, УГ не может найти правило с условием (ai, Si), ошибка в программе (наборе правил), ошибка в данных. В распознающих МТ неудачные завершение фиксирует «ложность» соответствующего предиката. Процесс остановки

№ слайда 36 Интерпретация Машины Тьюринга Процесс «вечной» работы МТ означает для порожда
Описание слайда:

Интерпретация Машины Тьюринга Процесс «вечной» работы МТ означает для порождающей МТ благополучную ситуацию, когда порождаемое слово может быть бесконечной цепочкой символов. Для распознающей МТ ситуация не предсказуема (либо МТ ещё не нашла значение предиката, либо имеется ошибка в программе). Процесс «вечной» работы

№ слайда 37 Интерпретация Машины Тьюринга Список правил для МТ не упорядочен. Поиск прави
Описание слайда:

Интерпретация Машины Тьюринга Список правил для МТ не упорядочен. Поиск правила происходит по условиям (Si, ai), возникшим в ti такт.

№ слайда 38 Машина Тьюринга Логическую структуру алгоритма (ЛСА), содержащую все возможны
Описание слайда:

Машина Тьюринга Логическую структуру алгоритма (ЛСА), содержащую все возможные последовательности команд удобно показывать на графе «переходов»

№ слайда 39 Машина Тьюринга Граф переходов МТ есть направленный бинарный граф S – вершины
Описание слайда:

Машина Тьюринга Граф переходов МТ есть направленный бинарный граф S – вершины, которые соответствуют множеству состояний МТ; V – множество дуг, которые соответствуют переходам (правилам).из состояния Si в состояние Sj,; Граф переходов GS замечателен тем, что он содержит все возможные «траектории» работы МТ, которые могут быть сколь угодно длинными (но конечными) и (это основное) определяет логику работы МТ, начиная с начального состояния S0, до момента останова. Граф GS в этом случае задаёт так называемую машину состояний.

№ слайда 40 Н.Вирт. Алгоритмы и структуры данных: Пер. с англ. Д.Б.Подшивалова. – М.: Мир
Описание слайда:

Н.Вирт. Алгоритмы и структуры данных: Пер. с англ. Д.Б.Подшивалова. – М.: Мир, 1989. – 360 с., ил. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. Пер. с англ. под ред. В.В.Мартынюка. – М.: Мир, 1981, 368 c. Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач. Учебное пособие. СПб.: Питер, 2005. 237 с.: ил. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: Построение и анализ / Пер. с англ. под ред. А.Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд., стереотип. – 960 с.: 263 ил. Дж.Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. Пер. с англ. под ред. С.К.Ландо, Дополнение М.В.Ульянова. – Москва, Техносфера, 2004 – 368 с. В.С.Новичков, Н.И.Парфилова, А.Н.Пылькин. Алгоритмизация и программирование на Турбо Паскале. Учебное пособие. М.: Горячая линия – Телеком, 2005. 438 с.: ил. Окулов С.М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2004. 424 с.: ил. Окулов С.М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний, 2004. 341 с.: ил. Ставровский А.Б. Первые шаги в программировании. Самоучитель: – М.: Издательский дом “Вильямс”, 2003. 368 с.: ил. Литература

№ слайда 41 ??? Что такое алгоритм? Какие этапы решегия задач на компьютере существуют? П
Описание слайда:

??? Что такое алгоритм? Какие этапы решегия задач на компьютере существуют? Перечислите основные типы алгоритмов? Две формы задач решения алгоритма? Что такое информационная структура алгоритма? Какие формы представления алгоритмов существуют? Что такое процедура структуры? Машина Тьюринга - представление. Контрольные вопросы:

№ слайда 42 Спасибо за Внимание! Спасибо за Внимание! Спасибо за Внимание!
Описание слайда:

Спасибо за Внимание! Спасибо за Внимание! Спасибо за Внимание!

Краткое описание документа:

Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. За 30–40 годы ХХ столетия было предложено примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа. 1.Алгоритмические машины (АМ). Алгоритм представляется набором правил команд процессора, последовательность выполнения которых управляет состоянием памяти. Основные АМ, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов были предложены в ХХ в. ·    Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. ·    Машина Поста (МР) предложена Постом в 1937 г. ·    Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.
Автор
Дата добавления 06.06.2014
Раздел Информатика
Подраздел Презентации
Просмотров762
Номер материала 122329060658
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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