Алгоритмы программирования

Кафедра медицинской
кибернетики и информатики
РНИМУ им. Н.И. Пирогова Минздрава РФ

Отделение

Инструктаж по технике безопасности и противопожарной безопасности

требования, обязательные для исполнения студентами

Действия при пожаре:

Студент, обнаруживший пожар или его признаки (задымление, запах гари

Специальные требования:

Студент обязан выполнять только ту работу, которая поручена и соответствует

Категорически запрещается:

Работать на неисправном оборудовании.
Приносить в учебные классы еду и
напитки.
Изменять

Что бывает ЗА НАРУШЕНИЕ

Лица, нарушающие требования инструкции:
отстраняются от работы
направляются на

Общие требования к учащимся на кафедре Медицинской кибернетики и информатики
Наличие белых

Алгоритмы программирования.

1.Принципы архитектуры ЭВМ фон Неймана

Использование двоичной системы счисления в вычислительных машинах.

ЭВМ Эниак 1946г.

Компьютер 2019

2.Области применения компьютеров:

Обработка и хранение информации
Анализ данных в различных областях
Работа с

Стоматология

Новейщие информационные медицинские технологии . Телемедицина.

Единая государственная система здравоохранения РФ

ИЭМК-Интегрированная электронная медицинская карта»
ФХД-Финансово-хозяйственная деятельность
Задание

Компьютерная томография

Основные направления IT будущего:

По данным на 2019-2021гг ведущих аналитических изданий Cnews

Темы докладов:

Системы искусственного интеллекта в мед и здравоохранении
Использование облачных решений в

3. Основные понятия IT Опр. 1. Информация – это сведения об объектах

Опр. 2.Информационный процесс

это перенос и восприятие информации от исследуемого объекта

4. Основные понятия

Опр. 3 . Компьютер – это комплекс тех. И

Хранение информации в памяти компьютера Так человек видит изображение:
1111 1111

Процессор — электронный блок, либо интегральная схема (микропроцессор), исполняющая машинные инструкции (код

Общая схема компьютера

5.Единицы измерения информации

Опр. 8. Бит (bit) – базовая единица измерения информации, может

6. Основные направления теории кодирования

П.6 Алгоритмы и их свойства?

Опр. Алгоритм – это совокупность действий, приводящих

Свойства алгоритмов:

Дискретность– это разбиение алгоритма на ряд отдельных законченных действий-шагов.
Детерминированность -

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

Виды алгоритмов

Три основных вида алгоритмов:
линейный алгоритм,
разветвляющийся алгоритм,
циклический алгоритм.

Словесный алгоритм. 1. Линейный алгоритм

Алгоритм перехода через улицу на светофоре:
Подойти к переходу
Дождаться

Задание

1.Написать словесный алгоритм включения компьютера
2. Написать словесный алгоритм измерения площади

2.Разветвляющийся алгоритм – алгоритм с вариантами ( с условиями)

Пример 1. Алгоритм

Задание

1. Написать словесный алгоритм с условием для покупки книги
2. Написать

П.7. Графическая форма представления алгоритма. Блок-схемы. Таб 2. Основные виды блоков представлены

Пример 1. Александр хочет позвонить Пете по городскому телефону.
Надо: составить

Пример 2.
Ученику требуется купить учебник.
Составить блок-схему, описывающую порядок действий

Блок-схема для примера 2

Пример 3.
Даны числа a=2, b=7 .
Вычислить сумму S и

Блок-схема к примеру 3

Графическая реализация разветвляющегося алгоритма

Пример 4.
Джон звонит Полу по городскому телефону, но

Блок-схема для примера 4.

Пример 5.
Ученику требуется купить учебник. В магазине в наличии

Блок-схема для примера 5

3.Циклические алгоритмы. Блок-схемы с циклом.

Циклы бывают двух видов:
с предусловием
с постусловием.

1.

1.Цикл с предусловием

2.Цикл с постусловием.

Пример 3. Вася звонит Пете, но у Пети может быть занята

Пример 4. Ученику требуется купить учебник. Составить блок-схему, описывающую действия ученика

Пример 5. Даны числа a,b. Известно, что число a меняется от

Проверочная работа 2.

Занятие 3.Циклические алгоритмы

Опр. . Тело цикла – это набор инструкций, предназначенный

Виды циклов:

1. С предусловием – если условие верно, то выполняется тело

Цикл с предусловием- сначала проверяется условие, потом выполняется тело цикла

Задача 1

Найти сумму всех чисел от 5 до 45.

Цикл с постусловием сначала выполняется тело цикла, затем проверяется условие

Задача 2

Вычислить и вывести сумму степеней числа 2, пока она не

Цикл со счетчиком. Выполнение цикла фиксированное число раз.

Задача 3

Найти произведение m чисел

Расчет по алгоритму на тестовых данных.

Задача 4. Произвести расчет по алгоритму

Глава 2. Оценка эффективности алгоритмов. Псевдокод.

П. 1. Оценка эффективности алгоритмов.
Этапы:
1.Теоретический анализ
2.Проверочные

Измерение использования ресурсов.

Измерения обычно выражаются как функция от размера входных

Группа Б. Для компьютеров, питающихся от батарей (например, ноутбуков) или для

Опр. Вычислительной сложностью алгоритма называют функцию зависимости объёма работы, которая выполняется

Рассмотрение входных данных большого размера и оценка порядка роста  времени работы алгоритма

Различные виды нотаций

Проверочная работа

Задача 1. Разработать блок-схему алгоритма :
Вычислить сумму нечетных чисел от

П. Основные понятия теории множеств

Опр.1. Множеством называется совокупность некоторых элементов, объединенных каким-либо

Опр.4. Множество, которое не содержит ни одного элемента, называется пустым и

Основные числовые множества:

N={1,2,3,4,…} – множество натуральных чисел;
Z={…,-4,-3,-2,-1,0,1,2,3,4,…} – множество целых чисел

Основные свойства отношений включения между множествами:

∅⊂А для любого множества А;
А⊂А для

Операции над множествами
Опр.6 Пересечением множеств А и В называется множество С,

1.Свойства операции пересечения:

А∩А=А;
А∩∅=∅;
А∩А’=∅;
А∩U=А;
А∩В=В∩А.

Операция объединения множеств

Опр. 7 Объединением множеств А и В называется множество

2.Свойства операции объединения:

А∪А=А;
А∪∅=А;
А∪А’=U;
А∪U=U;
А∪В=В∪А.

Опр.8 Разностью множеств А и В называется множество С, состоящее из

3.Свойства операции разности:
1) А\А=∅;
2) А\∅=А;
3) А\А’=А;
4) А\U=∅;
5)

Дополнение множества А

Приоритет выполнения операций

Порядок выполнения операций над множествами:
Равноправные действия слева

Задачи по теории множеств.

Проверочная работа по теории множеств.

На листочках

П.2. Псевдокод Приведем основные управляющие структуры псевдокода

Пример 1 хорошего начального псевдокода
Если номер счета и пароль подходят, то

Пример псевдокода 2.

Программа должна заменять сочетание букв "to" в текстовом

Этапы написания псевдокода

Сначала опишите цель процесса. Если с помощью псевдокода можно

В процессе описания алгоритма решения задачи на псевдокоде, пишите только по

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

Команды языков программирования в псевдокоде

Важными ключевыми словами могут быть:
READ,
WRITE,
IF,

Конструкции языков в псевдокоде

1. IF Условие THEN Команды.
Это означает,

Структуризация алгоритма в псевдокоде и программе

BLOCK1
BLOCK2
BLOCK3
BLOCK2

Задача 1. Алгоритм решения квадратного уравнения на псевдокоде

Решение

Задача 2. Написать алгоритм в псевдокоде для расчета значения выражения a=k+b/n.

Проверочная работа 2.

Задача 1.Посчитать в тексте кол-во вхождений последовательности “шин” во

П.1. Основные понятия
Опр. 1. Символ — любой печатный знак
Опр.2. Алфавит

Опр. 3. Слово — конечная последовательность символов из алфавита:
Опр. 4. Длина

1.Объектами алгоритма являются слова
и только они.
2.Алгоритм — описание способа

Опр 5. Алгоритмы В и С эквивалентны в алфавите А (на

Опр.6. Алгоритмические языки это формальные языки используемые для записи, реализации или

Описание языков

Описание алгоритмического языка – это описание, которое содержит:
алфавит —

ОСНОВНЫЕ СПОСОБЫ КОМПОЗИЦИИ АЛГОРИТМОВ:

1) Суперпозиция алгоритмов. При суперпозиции двух алгоритмов A

Рекурсия. Рекурсивная функция

Опр. 8. В программировании рекурсия — вызов функции (процедуры) из неё же

Опр. 10. Частично-рекурсивной функцией называется функция, которую можно построить из набора

Опр.11

Понятие вычислений тесно связано с понятием алгоритма, потому, что вычисления являются

ТЕЗИС ЧЕРЧА - совокупность всех частично вычислимых функций совпадает с совокупностью

Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций:
примитивно рекурсивные функции;
общерекурсивные функции;
частично

Алгоритм — описание способа преобразования одного (входного) слова в другое

П.2.Формальное определение алгоритма 1). Машина Тьюринга.

Автомат может выполнять три элементарных действия:
записывать в видимую клетку новый

Программа для машины Тьюринга

Слева перечисляются все состояния, в которых может находиться

Правила выполнения программы:
К началу выполнения программы машина Тьюринга находится в начальной

3. В таблице отыскивается ячейка на пересечении первой строки
(т.к. автомат

Окончание работы программы и результат

В целом возможны два исхода работы МТ

гипотеза Тьюринга – всякий разрешимый алгоритм может быть представлен в виде

П.4. Нормальные алгоритмы Маркова

Уточним:

Правило выполнения нормального алгоритма Маркова

1.На каждом шаге входящие в НАМ формулы

Применимости НАМ:

В обоих случаях говорят, что НАМ применúм к входному слову.

Вставка и удаление символов в НАМ

Правильное решение:

Доп. Теорема 2 Маркова

Существует такой универсальный алгоритм U, который для любого

Глава 4. Типы и структуры данных. П.1. формальные языки и языки программирования

Опр

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

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

Таблица ASCII: символ ASCII код двоичный код

Таблица ASCII -название таблицы кодировки,

Коды ASCII

Таблица Unicode

— стандарт кодирования символов, включающий в себя знаки почти всех письменных языков

Цикл работы команды программы

1. Извлечение инструкции из памяти: используя текущее значение

П.2. Типы данных.

Опр. 1. Типом данных называется класс данных, характеризуемый

Классификация типов данных

1). Простые типы данных.

2). Составные типы данных

Массив — это набор значений одного типа, хранящихся последовательно в памяти.
Структуры

Так в Питоне есть следующие типы данных

Числа
Логические
Строки
Байты
Массивы байтов
Списки
Кортежи
Множества
Словари

П.3.Числовой тип данных

ОПЕРАЦИИ с переменными и константами числового типа:
стандартные арифметические операции,

П.4. Символьный тип данных

Операции:
Ввод символьных значений
Вывод
Присваивание
Все операции сравнения ( по ASCII

П.5. Логический тип данных.Boolean. Основные понятия алгебры логики.

Опр. 2. Логический тип

Доступные операции с этим типом данных:
И (логическое умножение) (AND, &, *),
ИЛИ (логическое сложение) (OR,   |

Основные понятия Алгебры логики.

Опр. 4. Логическое высказывание — это любoе повествовательное пpедлoжение,

Задание 1. Пусть
a = “это утро ясное”,
b = “это

Основные логические операции

Таблицы истинности- значение функции при всех наборах переменных

Отрицание Коньюнкция Дизьюнкция

Дополнительные логические операции

Таблицы истинности доп. лог. операций

Эквивалентность Следование Искл. ИЛИ - XOR

Законы алгебры логики

Последовательность выполнения операций:

Скобки
логическое отрицание
логическое умножение
логическое сложение
исключающее ИЛИ
логическое следование
эквивалентность

Семинар 9.

Алгоритм построения таблицы истинности логической функции(выражения)

Пример 1.таблица истинности для выражения

Задачи 2.Самост. реш

Пример 2. Составим таблицу истинности для формулы 
которая содержит две переменные x

Оператор IF и логические выражения

Проверочная работа по теме: Алгебра логики 1.

Задача 4. Написать псевдокод решения задачи с использованием конструкций IF-THEN-ELSE

Семинар 10.

Задание 2.

Написать псевдокод решения задачи с
Использованием конструкций IF-THEN-ELSE и логических
операторов AND,

Задание 3.

Написать псевдокод решения задачи с использованием конструкций IF-THEN-ELSE и логических

Задача 4.

Псевдокод к задаче, используя цикл с предусловием и for:

Тип данных – Массивы.

Опр. Массив — это структура однотипных данных, занимающих

Объявление массивов:

Массив в языках пр-я задается следующим образом:
тип_элементов идентификатор[размер элемента], где

Инициализация – заполнение массива:

i n t l e a p [

Размерность массивов:
Массивы могут быть одномерными, двумерные (матрицы), трехмерные и т.д.
Размерность массивов

Представления 1-, 2-, 3-х мерных массивов

Алгебра матриц

Матрица – 2-мерный массив данных.
Действия:
Сложение матриц
Вычитание матриц
Умножение матрицы на число
Умножение

Умножение матриц

Работа с массивами:

Для сложения,
вычитания,
умножения,
деления
образования формул
массивы должны

Массивы в Питоне

Python не имеет встроенной поддержки массивов, но вместо этого

Двумерные массивы в Питоне.

Многомерные списки в Питон.

Задачи ДЗ– алгебра матриц

Задача1. Сложить и – массив B и 2B.
Задача

Проверочная работа.
Задача 4.
Написать псевдокод:
Описать 2-мерный массив A целых чисел

На дом.

Задача 7. Описать 2-мерный массив ALA размера m*n (вводятся).

Рекурсия в программировании

Опр. 1. В программировании рекурсия — вызов функции (процедуры) из неё же

Одномерные и двумерные массивы – основные задачи.

1.1.Одномерные
массивы:
Объявление массива
Инициализация, заполнение
Сортировка
Поиск
Замена

Сортировка массива - преобразование последовательности элементов в неубывающую (или невозрастающую) последовательность.

Элементы массива можно сортировать:
по возрастанию — каждый следующий элемент больше предыдущего

Методы сортировки массива

1. При первой итерации цикла элементы массива попарно сравниваются

Сортировка методом Пузырька

2.Сортировка методом выбора (по возрастанию)
в массиве ищется минимальный элемент и

Начертим блок-схему метода выбора

Блок-схема алгоритма сортировки методом выбора

Задача

1.Написать псевдокод для решения задачи :
Упорядочить по возрастанию массив A из

3. Сортировка вставками

Алгоритм:
Временная сложность - O(n2).

Начертим блок-схему метода сортировки вставками

Блок-схема сортировки вставками

Задача 2.

1.Написать псевдокод для решения задачи :
Упорядочить по возрастанию массив B

4.Сортировка Шелла.
Усовершенствованный вариант метода сортировки вставками.
Алгоритм:
сначала сравниваются и

5.Быстрая сортировка или quick sort:
Алгоритм:
Выберем и запомним средний элемент массива (присвоим X=67):
Инициализируем

6.Сортировка слиянием.
Алгоритм:
1.Массив делится на два подмассива, а затем происходит:
Сортировка левой половины

7. Пирамидальная сортировка.
Может рассматриваться как усовершенствованная  сортировка пузырьком, в которой элемент

ДЗ упорядочить массив по убыванию A=[1,7,9,15,10,0,3,8,18,5]

– методами Сортировки Пузырьком и Быстрой

Задачи проверочная: составить блок-схемы к алгоритму:
Задача 1. Дан массив из

Задача 3. Дан массив 20 целых чисел, часть которых -

Алгоритмы поиска значения в массиве

1. Линейный поиск – алгоритм:
поиск

3.Интерполяционный поиск - алгоритм производит предсказание области местонахождения элемента по расстоянию

Одномерные и двумерные массивы – основные задачи.

1.1.Одномерные
массивы.
1.1.Поиск

Задачи:
Задача 1. Дан массив целых чисел. Количество чисел N вводится с

1.1.Двумерные массивы:
Объявление массива
Инициализация, заполнение
Сортировка элементов в столбце или строке
Поиск элементов в

Семестр 2.

Дисциплина
Вычислительная математика.
Алгоримы на Python.

Современная вычислительная математика включает в круг своих проблем изучение особенностей вычисления

В вычислительной математике выделяют следующие

Глава 1. Структуры данных: Строки, Списки, Деревья.

П.1. Тип - Строки
Опр.

В языках программирования возможны следующие операции со строками:

получение символа

Функции и процедуры со строковыми переменными в ПИТОНЕ

Продолжение - функции строк в Питоне

П.2. Динамические структуры в ЯП.

Динамические структуры данных – это структуры данных, память под которые

Динамическая структура данных характеризуется тем, что:
она не имеет имени;
этой структуре выделяется память

Особенности динамических структур

Каждой динамической структуре данных сопоставляется статическая переменная типа указатель (ее значение – адрес этого объекта), с

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

Порядок работы с динамическими структурами данных :

создать (отвести место в динамической памяти);
работать при

Динамическая структура может занимать несмежные участки оперативной памяти.
Динамические структуры широко применяют и

п.3. Тип данных – 2).Списки Опр.2. Списком называется упорядоченное множество, состоящее из

В языках программирования возможны следующие операции со списками:

1.создание списка; 2.печать (просмотр)

3.1.Односвязные списки.
Опр.3. Односвязный список – это структура данных, представляющая собой последовательность элементов,

3.2. Двусвязный список

Опр.4. Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности

Списки в Питон – это упорядоченные изменяемые коллекции объектов произвольных типов.

Продолжение - Методы списков в Питоне

Типы 3.Стек и 4.Очередь -динамические структуры данных, которые  можно организовать на

Операции со стэком:
создание стека;
печать (просмотр) стека;
добавление элемента в вершину стека;
извлечение

4) Очередь – это динамическая структура данных, представляющая собой последовательность элементов, образованная в

Основные операции, производимые с очередью:
создание очереди;
печать (просмотр) очереди;
добавление элемента в конец очереди;
извлечение

П.5.Тип данных 5.Дэк (дек)

Опр.5. Дек (двухсторонняя очередь) – это структура данных, представляющая собой последовательность

Опр.6.дек с ограниченным входом – из конца дека можно только извлекать элементы;
Опр.7.дек с ограниченным выходом

Основные операции с деком:

1.создание дека;
2.печать (просмотр) дека;
3.добавление элемента в левый конец дека;
4. добавление элемента

П.6.Тип данных-Деревья

Опр.8. Дерево – это динамическая структура данных, представляющая собой совокупность элементов

Опр. 12. Корень дерева – это начальный узел дерева, ему соответствует нулевой

Опр.15. Потомки – это все вершины, в которые входят ветви, исходящие из

Опр.18.Степень вершины – это количество дуг, которое выходит из этой вершины.
Опр.19.Степень дерева –

Опр. 22. Обход дерева – это упорядоченная последовательность вершин дерева, в которой

П.7.Тип данных 7. Бинарные деревья

Опр. 23. Бинарное (двоичное) дерево – это дерево, в

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

Адресация в бинарном дереве

Основными операциями с бинарными деревьями, являются:
создание бинарного дерева;
печать бинарного дерева;
обход бинарного дерева;
вставка элемента в бинарное

Глава 2. Задача поиска подстроки в строке.
П.1. Определения.
Алфавит – конечное множество символов.
Строка

Постановка задачи поиска подстроки в строке:
Пусть задана строка, состоящая

П.2. Наивный (прямой) алгоритм поиска подстроки в строке.
Суть алгоритма:
1). В

Алгоритм прямого поиска
Идея алгоритма: 1. I=1, 2. сравнить I-й символ массива T с

Вычислительная математика.

Лекция 2.
Алгоритмы поиска Кнутта-Морис –Пратта.
Хэширование.
Алгоритм поиска Рабина-Карпа.

П.3.Алгоритм Кнута, Морриса и Пратта. Префикс-функция:

Пусть дана строка S длины n.
Опр.4. Префикс-функция –

Пример 1. Для строки "abcabcd" префикс-функция равна:  [0,0,0,1,2,3,0], так как:
у строки "a" нет

Ответ на пример 2

(она равна: [0,1,0,1,2,2,3])

Алгоритм Кнута-Мориса-Пратта

Суть алгоритма: сдвиг подстроки выполняется не на один символ

Пример 1.

Пример. (Символы, подвергшиеся сравнению, подчеркнуты.)

После частичного совпадения начальной части образа

П.4. Хеширование

Опр. 5. Хеш-функция — функция, которая по определенному алгоритму преобразовывает

Опр. 7.Хеш-таблица – это структура данных, реализующая  интерфейс ассоциативного массива,
она позволяет

Опр. 7.Коллизия –ситуация, когда разным ключам соответствует одно значение хеш-функции (ключи в этом

Хеш-функция должна удовлетворять следующим условиям:
функция должна быть простой с вычислительной точки

Коллизии нарушают однозначность соответствия между хеш-кодами и данными.
Существуют способы преодоления

П.5.Разрешение коллизий.

1.Разрешение коллизий при помощи цепочек
элементы множества, которым соответствует одно и

2.Разрешение коллизий при помощи открытой адресации

При открытой адресации все записи хранятся

Задача 1. Первое и последнее вхождение

Дана строка. Если в этой строке

Задача 2. Дублирование фрагмента

Дана строка, в которой буква h встречается как минимум два

Задача 3. Замена подстроки

Дана строка. Замените в этой строке все цифры

Банковские проценты

Вклад в банке составляет x рублей. Ежегодно он увеличивается на q процентов, после чего

Задача ДЗ

Написать программу простого поиска подстроки в строке.
Можно использовать циклы, if

П.6.Алгоритм Рабина — Карпа 

это алгоритм поиска подстроки в строке, который ищет шаблон, то

Алгоритм Рабина-Карпа

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7,

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, … k1=31415≡7(mod 13) – вхождение образца, k2=67399≡7(mod

Задача на циклы 1

Задача 2. Номер числа Фибоначчи

Задача 3. Фрагменты.

Дана последовательность натуральных чисел, завершающаяся числом 0.
Определите, какое

Задача 4. Монотонный фрагмент

Максимальная длина монотонного фрагмента
Дана последовательность натуральных чисел, завершающаяся

Задача 5. Банковские проценты

Вклад в банке составляет x  рублей.
Ежегодно он увеличивается

Функция в Python

ЗАДАЧА 1. Найти число сочетаний

Функции в Python

Вместо повторения в алгоритме выше
лучше сделать одну функцию,
вычисляющую факториал любого

Синтаксис функции в Python

Теперь мы можем использовать нашу функцию несколько раз.
В этом примере

Функция нахождения максимума из двух чисел

Итак – задача нахождения наибольшего из

!!! Внутри функции можно использовать переменные,
объявленные вне этой функции
def f():

Задача 1. Напишите функцию min4(a, b, c, d), вычисляющую
минимум четырех чисел,

Задача 3.

Задача 4. Минимальный делитель числа

Лекция 3. Суффиксные деревья

П.9. Суффиксные деревья.

Суффиксное дерево — это способ представления текста.
Опр.8. Бором называется

Для сокращения количества вершин оптимизируем бор:
рассмотрим цепочку вершин бора, такую

Опр. 9. Сжатый бор — это корневое дерево, на каждом
ребре

Опр.10. Суффиксным деревом строки S называется сжатый бор, построенный на всех

Пример 1. Рассмотрим строку "алгоритм", у нее есть следующие суффиксы:
Номер Суффикс
0             "алгоритм"
1             "лгоритм"
2             "горитм"
3             "оритм"
4             "ритм"
5             "итм"
6             "тм"
7             "м"
Первым суффиксом

Пример 2. Суффиксное дерево строки abca

Пример 3. Суффиксное дерево строки xabxa

Основные задачи, решаемые с использованием суффиксных деревьев и суффиксных массивов:
Определение количества

Продолжение. Задачи, решаемые с помощью суффиксных деревьев:

4.Определение длины наибольшего общего префикса

П. 10. Алгоритм Лемпеля-Зива – алгоритм сжатия данных.
В 1977 году Абрахам

Алгорим Лемпеля-Зива

На каждом шаге выводится тройка:
(d-смещение относительно текущей позиции,
L-длина

Рассмотрим реализацию 2:
Если в тексте встретится повторение строк символов, причем

Глава 3. Теория графов и использование графов в алгоритмах.

П.1. основные термины

Опр. 4. Два ребра называются кратными, если они соединяют одну и ту

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

Опр.11.Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в

В теории графов два типа объектов называются циклами:
1). замкнутый обход, состоит из последовательности вершин,

Опр.14. Степенью вершины в неориентированном графе называется число инцидентных данной 
вершине

Свойства графов

A. В любом графе число вершин нечетной степени – четно.

П.2. Способы представления графов в памяти.

Представление графов в памяти –

Способы представления графов в памяти:
Матрица смежности
Списки смежных вершин
Список ребер

1.Матрица смежности

При представлении графа матрицей смежности информация о ребрах графа хранится в квадратной

2. Хранение графа в виде списка ребер.

При представлении графа списком ребер для каждого

3. Представление графа списками смежности

1. Для каждой вершины i хранится список W[i]

П.3.Алгоритмы поиска в графе.

Опр.16. Вершина, которая еще не посещена,

Опр.17. Взвешенным графом называется граф, у которого любая пара вершин (ребро)

Опр. 18. Кратчайшим путем называется путь в графе, содержащий наименьшее количество

1.Алгоритм поиска в глубину.
Алгоритм поиска (или обхода) в глубину реализует обход

Алгоритм является рекурсивным — для обхода всего графа нужно переместиться

Задачи, решаемые поиском в глубину:
Поиск элементов
Поиск компонент связности
Поиск циклов и др.
Оценка

Лекция и семинар 7.

3.2. Поиск в ширину в графе.
Идея поиска в ширину состоит в том, чтобы

Оценка времени работы алгоритма поиска в ширину:
Если граф задан списками смежности

Алгоритм поиска в ширину:
Для каждой вершины в массиве d будем хранить

П.4. Задача 1. Вычисление Количества путей в графе

Пусть есть схема

Рекуррентная формула:
Если в город Z можно приехать только из городов B,

Решение Задачи 1

Задача 2.

На рисунке — схема дорог, связывающих города А, Б, В, Г,

Решение:Начнем считать количество путей с конца маршрута – с города К.

Задачи на вычисление путей в графе с избегаемыми вершинами

Задача 3. На

Решение задачи 3:количество путей до города Х = количество путей в

А = 1.
Б = А = 1.
В = А + Б

Задача 4. На рисунке – схема дорог, связывающих пункты А, Б,

Решение:
А = 1.
Б = А = 1.
В = А = 1.
Г

П.5. Эйлеров цикл.

Опр. 19. Эйлеровым циклом в графе называется цикл, содержащий

Эйлеров цикл в графе означает, что следуя вдоль цикла, можно нарисовать

П.6.Задача 2. Задача о Кенигсбергских мостах:

У жителей 
Кенигсберга  
была загадка: как пройти

В 1736 году фон Эйлер решил Задачу о семи мостах.
Решение

Решение задачи Эйлера:
На схеме города - графе мостам соответствуют линии -

Теорема 1. Если граф  обладает эйлеровым циклом, то он является связным, а все

Теорема 3. Если граф  G обладает эйлеровым путем с концами VA и VB  и VA не совпадает с

Контрольная

Глава 3. Математическое программирование –
– это раздел прикладной математики, посвященный теории

пI. Динамическое программирование

Сущность метода Динамического программирования - рассмотрим операцию О, состоящую

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

В основе решения всех задач динамического программирования лежат принципы оптимальности и

Рассмотрим особенности математической модели динамического программирования

задача оптимизации формулируется как конечный многошаговый

Виды задач, решаемых методами динамического программирования

Задача о нахождении кратчайшего либо наилучшего

Задача о нахождении кратчайшего пути в графе.
Пусть транспортная сеть состоит из 10 узлов,

Процедура решения задач методом динамического программирования состоит из 2-х стадий:
1.

Понятие о NP-полных задачах. Примеры.

Опр. 2. P – класс задач, решаемых

Список Карпа — список, состоящий из формулировки и доказательства NP- полноты 21 задачи,

Алгоритм имитации отжига  — алгоритм решения различных оптимизационных задач.

Лев Семенович Понтрягин –выдающийся российский ученый

Родился 21 августа (3 сентября) 1908 г., Москва.

В 14 лет Лев потерял зрение в результате несчастного случая (взорвавшийся

Этапы пути

Л. С. Понтрягин окончил физико-математический факультет МГУ по специальности «чистая математика»

Ученая степень доктор физико-математических наук присуждена без защиты диссертации в 1935 г.

Области научных интересов Л. С. Понтрягина

топология и топологическая алгебра,
теория дифференциальных уравнений,

ТРУДЫ – более 300.

Математическая теория оптимальных процессов. — 2-е изд. — М.:

Почетные звания и награды

Почётный член Лондонского математического общества (1953)
Почётный

Хобби

1.Музыка
2.Лыжи
3. Коньки
4.Литература