Структуры и алгоритмы компьютерной обработки данных Петухин Вячеслав Алексеевич 1 семестр, 17 часов лекций, 17 часов лабораторных.

Презентация:



Advertisements
Похожие презентации
Анализ вычислительной сложности алгоритмов Теория сложности вычислений.
Advertisements

Вводная лекция Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра.
Структуры и алгоритмы компьютерной обработки данных Представление дисциплины.
Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО.
Понятие сложности алгоритма Для практики недостаточно знать, что задача алгоритмически разрешима. Т. к. ресурсы ЭВМ (ОП и время процессора) ограничены,
NP-полные задачи. Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да»
Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные.
Компьютерное моделирование Петухин Вячеслав Алексеевич 1 семестр, 38 часа лекций, 38 часов лабораторных.
Системы реального времени Лекция 2: Стандарты и расширения. Алгоритмы реального времени.
Анализ трудоёмкости алгоритмов Анализ трудоёмкости алгоритмов позволяет найти оптимальный алгоритм для решения данной задачи. трудоемкость алгоритма количество.
Информатика Выполнила: Балашова Елизавета. Информатика-это Информатика наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки.
Основы алгоритмизации и программирования Лекция 2. А.Ф.ОСЬКИН ПГУ, Полоцк.
Теория экономических информационных систем Представление дисциплины.
Троицкий Д.И. Лингвистическое и программное обеспечение САПР 1 Классификация грамматик и языков Лекция 9 Кафедра «Автоматизированные станочные системы»
1 Сложность, сортировка, поиск Работа по дисциплине «Алгоритмы и структуры данных» Выполнена Садукевич А.В., 271ПИ.
Обработка массивов Сортировка. Сортировка массивов «…создается впечатление, что можно построить целый курс программирования, выбирая примеры только из.
11 августа 2015 г. 11 августа 2015 г. 11 августа 2015 г. 11 августа 2015 г. 11 августа 2015 г.
ЛЕКЦИЯ 13. Курс: Проектирование систем: Структурный подход Каф. Коммуникационные и системы, Факультет радиотехники и кибернетики Московский физико-технический.
Структура содержания базового курса информатики Базовый курс информатики (содержательные линии) Информация и информационные процессы Компьютер (ЭВМ) Компьютерные.
1 Лектор: Кононов Александр Вениаминович НГУ, ауд. 313 четверг 16:00 Приближенные алгоритмы.
Транксрипт:

Структуры и алгоритмы компьютерной обработки данных Петухин Вячеслав Алексеевич 1 семестр, 17 часов лекций, 17 часов лабораторных.

Литература Ахо, Хопкропфт, Ульман. Построение и анализ вычислительных алгоритмов. 1979

Сложность алгоритмов Функция сложности f(x) Для любых входных данных размером не более чем x время работы алгоритма не больше чем f(x) Классы сложности: полиномиальные экспоненциальные

Классы сложности Вычислительные устройства: Машина Тьюринга и эквивалентные ей устройства Недетерминированная машина Тьюринга Класс NP-сложных задач.

Структуры данных и алгоритмы Массив – итеративные алгоритмы Рекурсивные структуры данных (списки, деревья и т.д.) – рекурсия Язык программирования Паскаль

Алгоритмы сортировки Квадратичной сложности: Выборкой максимального Метод пузырька Быстрая сортировка (quicksort) Оптимальные алгоритмы O(n log 2 n) С помощью двоичного дерева