Алгоритмы и структуры данных

Министерство науки и высшего образования Российской Федерации Федеральное государственное образовательное учреждение высшего образования ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Институт математики и информационных систем Факультет автоматики и вычислительной техники Кафедра систем автоматизации управления Лекции Дисциплина: Алгоритмы и структуры данных Преподаватель: Кашина Елена Вячеславовна Киров, 2022 Список литературы по дисциплине «Алгоритмы и структуры данных» Основная 1. Белоцерковская, И. Е. Алгоритмизация. Введение в язык программирования С++ / И.Е. Белоцерковская. - 2-е изд., испр.. - Москва : Национальный Открытый Университет «ИНТУИТ», 2016. 197 с. URL: http://biblioclub.ru/index.php?page=book&id=428935/ (дата обращения: 23.08.2020). Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 2. Вирт, Н. Алгоритмы и структуры данных: пер. с англ. / Н. Вирт. – Издательство: ДМК-Пресс, 2016. – 272 с. 3. Документация по Visual Studio. - URL: https://docs.microsoft.com/ruru/visualstudio/windows/?view=vs-2019 (дата обращения: 23.08.2020). - Режим доступа: docs.microsoft.com. - Текст : электронный. 4. Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы. М.: Вильямс, 2018. – 720 с. (всего 4 тома. Том 2: Получисленные алгоритмы, Том 3: Сортировка и поиск, Том 4: Комбинированные алгоритмы). - URL: https://bookree.org/reader?file=536014 5. Седжвик, Роберт. Алгоритмы на С++: анализ, структуры данных, сортировка, поиск, алгоритмы на графах / Роберт Седжвик [при участии Кристофера Дж. Ван Вика] ; [пер. с англ. А. А. Моргунова]. - Москва [и др.] : Вильямс, 2019. - 1056 с. : ил. - URL: http://intuit.valrkl.ru/course-1215/index.html 6. Семакин, Игорь Геннадьевич. Основы алгоритмизации и программирования : учебник / И. Г. Семакин, А. П. Шестаков. - Москва : Академия, 2018. - 300 с. 7. Структуры данных в C#. Часть I. Линейные динамические структуры: учеб. пособие / Е.В. Симонова, 2018. - URL: http://repo.ssau.ru/bitstream/Uchebnyeizdaniya/Struktury-dannyh-v-C-Ch-173315/1/%D0%A1%D0%B8%D0%BC%D0%BE%D0%BD%D0%BE%D0%B2%D0%B0 %20%D0%95.%D0%92.%20%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82% D1%83%D1%80%D1%8B%20%20%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B% D1%85.%20%D0%A7%D0%B0%D1%81%D1%82%D1%8C%20I.%202018.pdf (дата обращения: 23.08.2020). 8. Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ. Издание 3-е, 2013. - URL: https://e-maxx.ru/bookz/files/cormen.pdf (дата обращения: 23.08.2020). 9. Фленов, Михаил Евгеньевич. Библия С#. - 4-е изд. - Санкт-Петербург : БХВПетербург, 2020. - 512 с. 10. Волченская Т., Князьков В. Введение в теорию графов - URL: https://intuit.ru/studies/courses/1033/241/info 11. Кудрина Е., Огнева М., Портенко М. Программирование на языке С#: разработка консольных приложений - URL: http://repo.ssau.ru/bitstream/Uchebnyeizdaniya/Struktury-dannyh-v-C-Ch-273316/1/%d0%a1%d0%b8%d0%bc%d0%be%d0%bd%d0%be%d0%b2%d0%b0%20%d0 %95.%d0%92.%20%d0%a1%d1%82%d1%80%d1%83%d0%ba%d1%82%d1%83%d1%8 0%d1%8b%20%d0%b4%d0%b0%d0%bd%d0%bd%d1%8b%d1%85.%20%d0%a7%d0% b0%d1%81%d1%82%d1%8c%20II.%202018.pdf 2 Дополнительная 12. Зыков, С. В. Введение в теорию программирования. Объектноориентированный подход / С.В. Зыков. - 2-е изд., испр.. - Москва : Национальный Открытый Университет «ИНТУИТ», 2016. - 189 с.. - (Основы информационных технологий) - URL: http://biblioclub.ru/index.php?page=book&id=429073/ (дата обращения: 23.08.2020). - Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 13. Биллиг, В. А. Основы программирования на С# 3.0: ядро языка / В.А. Биллиг. 2-е изд., испр.. - Москва : Национальный Открытый Университет «ИНТУИТ», 2016. 411 с. - URL: http://biblioclub.ru/index.php?page=book&id=428947/ (дата обращения: 23.08.2020). - Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 14. Леоненков, А. Нотация и семантика языка UML / А. Леоненков. - 2-е изд., исправ.. - Москва : Национальный Открытый Университет «ИНТУИТ», 2016. - 205 с.. (Основы информационных технологий) URL: http://biblioclub.ru/index.php?page=book&id=429143/ (дата обращения: 23.08.2020). Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 15. Суханов, М. В. Основы Microsoft .NET Framework и языка программирования C# : учебное пособие / М.В. Суханов. - Архангельск : ИД САФУ, 2014. - 97 с. - URL: http://biblioclub.ru/index.php?page=book&id=312313/ (дата обращения: 23.08.2020). Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 16. Хританков, А. С. Проектирование на UML : сборник задач / А.С. Хританков, В.А. Полежаев, А.И. Андрианов. - 3-е изд. стер.. - Москва|Берлин : Директ-Медиа, 2018. - 242 с. : ил. - URL: http://biblioclub.ru/index.php?page=book&id=483549/ (дата обращения: 23.08.2020). - Режим доступа: ЭБС Университетская библиотека ONLINE. - Текст : электронный. 17. Фофанов О.Б. Алгоритмы и структуры данных: учебное пособие. – Томск: Изд-во ТПУ, 2014. – 126 с. 18. Как измерить время выполнения программы, кода URL: https://www.youtube.com/watch?v=c0sJ2XNCwwE&feature=emb_logo 19. Измерение времени кода. Stopwatch и DateTime URL: https://habr.com/ru/post/226279/ 20. Коллекции. Список List - URL: https://metanit.com/sharp/tutorial/4.5.php 21. Коллекции List, Dictionary и тип Tuple - URL: https://devpractice.ru/c-sharplesson-10-generics/ 22. Двусвязные списки - URL: https://metanit.com/sharp/algoritm/2.2.php 23. Коллекции. Очередь Queue - URL: https://metanit.com/sharp/tutorial/4.7.php 24. Класс Queue URL: https://docs.microsoft.com/ruru/dotnet/api/system.collections.generic.queue-1?view=netcore-1.1 25. Класс Stack URL: https://docs.microsoft.com/ruru/dotnet/api/system.collections.generic.stack-1?view=netcore-1.1#code-try-4 26. Структуры данных. Дек - URL: https://metanit.com/sharp/algoritm/2.6.php 27. Бинарное дерево. Реализация структуры данных бинарное дерево и методов добавления, удаления и поиска узлов на C# - URL: https://programm.top/c-sharp/datastructures/binary-tree/ 28. Класс Hashtable URL: https://docs.microsoft.com/ruru/dotnet/api/system.collections.hashtable?view=net-6.0 3 29. Основы языка С#. Основы ООП. Типы и структуры данных - URL: https://pptonline.org/287711 30. Коллекция Hashtable C# - URL: https://upread.ru/art.php?id=664 31. Хеш таблица C# - URL: https://shwanoff.ru/hashtable/ 32. Тип данных void - URL: https://ravesli.com/urok-29-void/ 33. Основные структуры данных - URL: https://habr.com/ru/post/422259/ 34. Бо Карнс. 10 структур данных - URL: https://proglib.io/p/datastructures/#comments 35. Эффективностью алгоритма - URL: https://metanit.com/sharp/algoritm/1.1.php 36. Оценка сложности алгоритмов - URL: https://habr.com/ru/post/104219/ 37. Функция T(n) в расчёте сложности алгоритма - URL: https://murnik.ru/slozhnostalgoritmov 38. Математические функции в с#. Класс math URL: https://yandex.ru/images/search?pos=16&img_url=https%3A%2F%2Fmypresentation.ru% 2Fdocuments_5%2F323a5f04050188898bc778a332530f72%2Fimg27.jpg&text=%D0%B C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B 5%D1%81%D0%BA%D0%B8%D0%B5%20%D1%84%D1%83%D0%BD%D0%BA%D 1%86%D0%B8%D0%B8%20%D0%B2%20%D1%81%23&lr=46&rpt=simage&source= wiz 39. Ввод и вывод данных в консоли - URL: https://www.youtube.com/watch?v=L7AZHWRyRs 40. Консольный ввод/вывод и форматирование URL: https://csharp.pro/%D0%BA%D0%BE%D0%BD%D1%81%D0%BE%D0%BB%D1%8C%D0%B D%D1%8B%D0%B9-%D0%B2%D0%B2%D0%BE%D0%B4%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4-%D0%B8%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE %D0%B2%D0%B0%D0%BD/ 41. Convert Класс URL: https://docs.microsoft.com/ruru/dotnet/api/system.convert?view=netcore-3.1 42. Встроенные типы языка C# URL: https://yandex.ru/images/search?pos=3&img_url=https%3A%2F%2Fcf.pptonline.org%2Ffiles%2Fslide%2Fw%2Fw70RLBxz2MnStA3Ye8QpTD6CumJNWcGgFfZ KUV%2Fslide10.jpg&text=%D1%82%D0%B8%D0%BF%D1%8B%20%D0%BF%D0%B5%D1%80% D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85%20c%23%20%D1 %82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0&lr=46&rpt=simage&sou rce=wiz 43. Переменные C# | Типы и виды переменных - URL: https://shwanoff.ru/variable/ 44. Комбинаторные задачи на программирование URL: https://nsportal.ru/shkola/informatika-i-ikt/library/2013/02/07/kombinatornye-zadachi-naprogrammirovanie 4 Раздел 1. Введение в алгоритмы 1.1. Анализ термина «алгоритм» Понятие алгоритм является основным для всей области компьютерного программирования, поэтому начнём мы с тщательного анализа этого термина [4]. Слово «алгоритм» (algorithm) (иногда используется устаревшее «алгорифм») уже само по себе представляет большой интерес. На первый взгляд может показаться, будто кто-то собирался написать слово «логарифм», но случайно переставил первые 4 буквы. Этого слова не было даже в «Новом мировом словаре Вебстера», вышедшем в 1957 году. В нём имелась только устаревшая форма “algorism” – старинное слово, которое означает “выполнение арифметических действий с помощью арабских цифр”. В средние века абакисты считали на абаках (счётных досках), а алгоритмики использовали “algorism”. В эпоху Возрождения происхождение этого слова оказалось забытым. Одни лингвисты того времени пытались объяснить его значение путем сочетания слов algiros [больной] и arithmos [число], другие не соглашались с таким толкованием и утверждали, что это слово происходит от “Алгор король Кастилии (King Algor of Castile)”. Наконец историки математики обнаружили истинное происхождение слова “algorism”: оно берет начало от имени автора знаменитого персидского учебника по математике – средневекового математика аль-Хорезми. АльХорезми написал знаменитую книгу “Книга о восстановлении и противопоставлении” (IX в. (825 г.)). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово – “алгебра”. В книге Аль-Хорезми дал правила выполнения четырёх 5 арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом. Постепенно форма и значение слова algorism исказились; как объясняется в Оксфордском Словаре Английского языка, это слово “претерпело множество псевдоэтимо-логических искажений, включая последний вариант algorithm, где произошла путаница” с корнем слова греческого происхождения arithmetic (арифметика). Этот переход от “algorism” к “algorithm” кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто. С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырёх операций арифметического исчисления. В старинном немецком математическом словаре Vollst;ndiges mathematisches Lexicon (Лейпциг, 1747) дается следующее определение слова algorithmus: “Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении”. Латинское выражение algorithmus infinitesimalis в то время использовалось для определения “способов выполнения действий с бесконечно малыми величинами, открытых Лейбницем”. К 1950 г. алгорисмус стал алгорифмом. К 1950 году слово “алгоритм” чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм был впервые приведен в книге Евклида «Начала» (около 300 г. до н.э.). {На правтике рассмотрим его более подробно} Современное значение слова «алгоритм» во многом аналогично таким понятиям, как рецепт, метод, процесс, способ, процедура, программа, но всё таки слово алгоритм имеет дополнительный смысловой оттенок. Алгоритм это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определённого типа. Помимо этого он имеет ряд важных особенностей – конечность, определенность, понятность, дискретность, массовость. 6 1.2. Понятие алгоритма, исполнителя алгоритма Понятие алгоритма одно из основных понятий информатики. Это фундаментальное «первоначальное» понятие, которому нельзя дать строгого определения. Существуют описательные определения алгоритма, которые уточняют это понятие. Например: Алгоритм – это последовательность действий со строго определёнными правилами выполнения. Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели или решение поставленной задачи. Будем придерживаться следующего понятия алгоритма:  Алгоритм (не определяемое понятие, его можно только пояснить) – это система точно сформулированных команд, определяющая процесс преобразования исходных данных в желаемый результат за конечное число шагов. В быту каждый человек сталкивается с алгоритмом как с последовательностью действий, приводящих к достижению цели: существует достаточно строго определенный порядок пеленания младенца, порядок одевания, порядок совершения утреннего туалета и т. д. В начальных классах школы дети изучают порядок выполнения арифметических действий над многозначными числами. Этот порядок был предложен выдающимся математиком средневекового Востока Мухаммедом альХорезми и по латинскому написанию его имени (Alhorithmi) был назван алгоритмом. В дальнейшем это понятие в значительной мере расширилось. В профессиональной деятельности мы также сталкиваемся с необходимостью строго следовать установленному порядку действий: правилам работы на токарном станке, инструкции по заправке нити в швейную машинку, порядку выполнения медицинских процедур (например, инъекций) и др. Пример 1. Вычислить значения y по формуле 7 Y=(Ax+B)*(Cx-D) для любого значения х, при заданных значениях констант A, B, C, D. Чтобы решить эту задачу достаточно выполнить последовательность следующих действий (т.е. алгоритм): 1) Умножить А на х, результат обозначить R1. 2) R1 сложить с В, результат обозначить R2. 3) Умножить С на х, результат обозначить R3. 4) Из R3 вычесть D, результат обозначить R4. 5) Умножить R2 на R4, считать результат значением y. Это предписание является алгоритмом решения поставленной задачи. Для человека, выполняющего действия, уже необязательно знать исходную формулу для вычисления значения y. Ему нужно всего лишь строго следовать указанному предписанию, исполняя его пункт за пунктом. Каждый алгоритм строится в расчёте на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он был в состоянии выполнить каждое действие, предписываемое командами алгоритма. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя.  Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя хаpактеpизуют: сpеда; элементаpные действия; cистема команд; отказы. Сpеда (или обстановка) – это «место обитания» исполнителя. Напpимеp, для исполнителя Pобот из учебника сpеда – это бесконечное клеточное поле. Стены и закpашенные клетки тоже часть сpеды. А их pасположение и положение самого Pобота задают конкpетное состояние среды. Система команд. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка – системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения 8 команды. Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат – смещение Pобота на одну клетку ввеpх.  Набор команд, которые может выполнить данный исполнитель, называется системой команд исполнителя (СКИ), или набором допустимых действий исполнителя. Пример 2: Продолжение примера 2: После вызова команды исполнитель совеpшает соответствующее элементаpное действие. 9 Отказы исполнителя возникают, если команда вызывается пpи недопустимом для неё состоянии сpеды. Обычно исполнитель ничего не знает о цели алгоpитма. Выполняет все полученные команды формально (не обдумывая, не задавая вопросов "почему" и "зачем"). Не формальный исполнитель может вносить изменения в алгоритм (например, ребёнок, сотрудник, собака). Формальное исполнение алгоритмов лежит в основе управления автоматическими устройствами. Действительно, простейшие операции, на которые при создании алгоритма расчленяется процесс решения задачи, может реализовать и машина, специально созданная для выполнения отдельных команд алгоритма и выполняющая их в последовательности, указанной в алгоритме. Однако и человек может быть формальным исполнителем. Если он не знает цели выполняемой работы, ему придется строго следовать инструкциям. Компьютер является формальным исполнителем алгоритмов. Чтобы он мог решать задачу в строгом соответствии с инструкциями, он должен получить алгоритм решения. Таким образом, алгоритм является управляющей информацией. Кроме того, последовательность действий исполнителя всегда применяется к некоторым исходным данным. Например, для вышеуказанного алгоритма в примере 1 необходимо знать значения всех переменных, входящих в формулу. Полный набор данных – необходимый и достаточный набор данных для решения поставленной задачи (получения исходного результата). Однако, алгоритм – это не просто набор конечного числа команд. Алгоритм обладает следующими свойствами. 10 1.3. Свойства алгоритма Точность (определенность, однозначность) – каждая команда 1) однозначно воспринимается исполнителем; выполнив шаг, исполнитель точно знает, какой шаг выполнить дальше. Примером неточного алгоритма является фраза из рецепта «всыпать 2-4 столовые ложки сахара» или классическое изречение «казнить нельзя помиловать». Дискретность 2) – алгоритм имеет прерывистую (дискретную структуру), т.е. только выполнив одну команду исполнитель может приступить к выполнению следующей; Выполнимость (конечность) – исполнение алгоритма приводит к 3) получению результата за конечное число шагов; Массовость – алгоритм можно применить для некоторого класса 4) однотипных задач. Желательно, чтобы алгоритм удовлетворял свойству массовости, т.е. мог быть применен для решения не только одной конкретной задачи, но и некоторого класса однотипных задач. Например, правило сложения многозначных чисел не зависит от количества разрядов в слагаемых или их цифрового состава. Оно работает, даже если число представлено не в десятичной системе счисления, а в позиционной системе счисления с любым целочисленным основанием. 5) Понятность – содержит только те команды, которые входят в систему команд исполнителя. Понятными для исполнителя считаются те команды, которые он может выполнить. Например, человек, не умеющий складывать однозначные числа (не знающий таблицы сложения), не сможет воспользоваться описанным аль-Хорезми порядком сложения многозначных чисел. 6) Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т.е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из 11 определённого набора объектов. Например, в алгоритме Евклида есть два входных значения, которые принадлежат множеству целых положительных чисел. Вывод. У алгоритма есть одно или несколько выходных данных, т. е. 7) величин, имеющих вполне определённую связь с входными данными. Например, у алгоритма Евклида имеется только одно выходное значение – это наибольший общий делитель двух входных значений. Эффективность. Алгоритм обычно считается эффективным, если все 8) его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги. Например, в алгоритме Евклида используются только следующие операции: деление одного целого положительного числа на другой, сравнение с нулём и присвоение одной переменной значения другой. Эти операции являются эффективными, так как целые числа можно представить на бумаге с помощью конечного числа знаков и так как существует, по меньшей мере, один способ («алгоритм деления») деления одного целого числа на другое. Но те же самые операции были бы неэффективными, если бы они выполнялись над действительными числами, представляющими собой бесконечные десятичные дроби. 1.4. Критерии качества и рабочие характеристики алгоритмов На практике нам нужны не просто алгоритмы, а хорошие алгоритмы в широком смысле этого слова. Одним из критериев качества алгоритма является время, необходимое для его выполнения; данную характеристику можно оценить по тому, сколько раз выполняется каждый шаг. Другими критериями являются адаптируемость алгоритма к различным компьютерам, его простота, изящество и т. д. Часто решить одну и ту же проблему можно с помощью нескольких алгоритмов и нужно выбрать наилучший из них. Таким образом, возникает чрезвычайно интересная и крайне важная область анализа алгоритмов. Предмет этой области состоит в том, чтобы для заданного алгоритма определить рабочие 12 характеристики. Как правило, это среднее число операций, необходимых для выполнения алгоритма – Tn, где n – параметр, характеризующий каким-то образом исходные данные, например число входных данных. Для обозначения области подобных исследований используется термин анализ алгоритмов. Основная идея заключается в том, чтобы взять конкретный алгоритм и определить его количественные характеристики. Можно выяснять, является ли алгоритм оптимальным в некотором смысле. Теория алгоритмов – это совершенно другая область, в которой, в первую очередь, рассматриваются вопросы существования или не существования эффективных алгоритмов вычисления определённых величин. Алгоритмы, как и аппаратное обеспечение компьютера, представляют собой технологию. Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности применяющегося аппаратного обеспечения. В области разработки алгоритмов происходит такое же быстрое развитие, как и в других компьютерных технологиях. Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как:  аппаратное обеспечение с высокими тактовыми частотами, конвейерной обработкой и суперскалярной архитектурой;  легкодоступные, интуитивно понятные графические интерфейсы (GUI);  объектно-ориентированные системы;  локальные и глобальные сети Ответ – да, безусловно. Несмотря на то, что иногда встречаются приложения, – которые не требуют алгоритмического наполнения (например, некоторые простые Web-приложения), для большинства приложений определенное алгоритмическое наполнение необходимо. Например, рассмотрим Web-службу, определяющую, как добраться из одного места в другое. В основе её реализации лежит высокопроизводительное аппаратное обеспечение, 13 графический интерфейс пользователя, глобальная сеть и, возможно, объектноориентированный подход. Кроме того, для определенных операций, выполняемых данной Web-службой, необходимо использование алгоритмов – например, таких как вычисление квадратных корней (что может потребоваться для определения кратчайшего пути), визуализации карт и интерполяции адресов. Более того, даже приложение, не требующее алгоритмического наполнения на высоком уровне, сильно зависит от алгоритмов. Известно, что работа приложения зависит от производительности аппаратного обеспечения, а при его разработке применяются разнообразные алгоритмы. Все мы также знаем, что приложение тесно связано с графическим нитерфейсом пользователя, а для разработки любого графического интерфейса пользователя требуются алгоритмы. Вспомним приложения, работающие в сети. Чтобы они могли функционировать, необходимо осуществлять маршрутизацию, которая, как уже говорилось, основана на ряде алгоритмов. Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, которые нитенсивно используют различные алгоритмы. И таким примерам нет числа. Кроме того, ввиду постоянного роста вычислительных возможностей компьютеров, они применяются для решения все более сложных задач. С ростом сложности решаемой задачи различия в эффективности алгоритмов проявляются всё значительнее. Знание основных алгоритмов и методов их разработки – одна из характеристик, отличающих умелого программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи можно решить и без основательного знания алгоритмов, однако знания в этой области позволяют достичь намного большего. 1.5. Анализ алгоритмов Время выполнения алгоритма или операции над структурой данных зависит, как правило, от целого ряда факторов, вследствие чего возникает вопрос – как следует проводить его измерение. 14 При резлизации алгоритма можно определить затраты времени, регистрируя действительное время, затраченное на выполнение алгоритма в каждом отдельном случае запуска с различными исходными данными. Подобные измерения должны проводиться с достаточной точностью с помощью системных вызовов, встроенных в язык или операционную снстему, для которой написан данный алгоритм (например, класс Stopwatch в C#). Задание 1: 1) посмотрите видео: https://www.youtube.com/watch?v=c0sJ2XNCwwE&feature=emb_logo 2) Прочитайте: https://habr.com/ru/post/226279/ 3) Реализуйте на любых двух созданных ранее программах измерение времени их выполнения. 4) Оформите отчёт по данному заданию, вышлите на почту (код в текстовом виде и скрин результата работы программы обязательны). В общем, требуется определить, каким образом время выполнения программы зависит от количества исходных данных. Для решения этой задачи можно провести ряд экспериментов, в которых будет использовано различное количество исходных данных. Далее полученные результаты наглядно представляются с помошью графика, где каждый случай выполнения алгоритма обозначается с помошью точки, координата х которой равна размеру исходных данных n, а координата у – времени выполнения алгоритма t (рис. 1). Рис. 1 15 Чтобы сделать определенные выводы на основе полученных экспериментов, необходимо использовать качественные образцы исходных данных и провести достаточно большое число экспериментов, что позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритма. Результаты экспериментального исследования времени выполнения алгоритма. Точка с координатами (n, t) обозначает, что при размере исходных данных n время выполнения алгоритма составило t миллисекунд (мс). На рис. 1 (а) представлены результаты выполнения алгоритма на компьютере с быстрым процессором, на рис. 1 (б) представлены результаты выполнения алгоритма на компьютере с медленным процессором. В целом можно сказать, что время выполнения алгоритма или метода доступа к полям структуры данных возрастает по мере увеличения размера исходных данных, хотя оно зависит и от типа данных, даже при равном размере. Кроме того, время выполнения зависит от аппаратного обеспечения (процессора, тактовой частоты, размера памяти, места на диске н др.) и программного обеспечения (операционной среды, языка программирования, компилятора, интерпретатора и др), с помошью которых осуществляется реализация, компиляция и выполнение алгоритма. Например, при всех прочих равных условиях время выполнения алгоритма определенного количества исходных данных будет меньше при использовании более мощного компьютера или при записи алгоритма в виде программы на машинном коде по сравнению с его исполненнем виртуальной машиной, проводящей интерпретацию в байт-коды. Экспернментальные исследования, безусловно, очень полезны, однако при их проведении существуют три основных ограничения:  эксперименты ограниченного набора могут проводиться исходных данных; лишь с результаты, использованием полученные с использованием другого набора, не учитываются;  для сравнения эффективности двух алгоритмов необходимо, чтобы эксперименты по определению времени их выполнения проводились на одинаковом аппаратном н программном обеспечении; 16  для экспернментального изучения времени выполнения алгоритма необходимо провести его реализацию и выполнение. Обычно для сравнительного анализа рассматривается, так называемая общая методология анализа времени выполнения алгоритмов, которая:  учитывает различные типы входных данных;  позволяет производить оценку относительной эффективности любых двух алгоритмов независимо от аппаратного и программного обеспечения;  может проводиться по описанию алгоритма без его непосредственной реализации или экспериментов. Сущность такой методологии состоит в том, что каждому алгоритму соответствует функция, которая представляет время выполнения алгоритма как функцию размера исходных данных n. Наиболее распространенными являются функции n и n2. Например, можно записать следующее утверждение: «Время выполнения алгоритма А пропорционально n». В этом случае, в результате проведения экспериментов, окажется, что время выполнения алгоритма А при любом размере входных данных n не превышает значения cn, где с является константой, определяемой условиями используемого аппаратного и программного обеспечения. Если имеются два алгоритма А и В, причём время выполнения алгоритма А пропорционально n, а время выполнения В пропорционально n2 то предпочтительнее использовать алгоритм А, так как функция n возрастает медленнее, чем Функция n2. Выводы о скорости возрастания этих функций являются, безусловно, очевидными, однако предлагаемая методология содержит точные определения данных понятий. Прочитайте про оценку сложности алгоритмов по ссылкам: https://habr.com/ru/post/104219/ и https://murnik.ru/slozhnost-algoritmov 17 Раздел 2. Способы записи алгоритмов. Основные типы алгоритмов. Алгоритмизация, как один из основных этапов создания программы 2.1. Способы записи алгоритмов IV. Способы записи алгоритмов. Существует несколько способов записи алгоритмов. 1) Для человека основным является словесно-формульный способ записи алгоритмов, т. е. описание алгоритма с помощью слов и формул. 2) Для компьютера запись алгоритма производится на одном из языков программирования. 3) Графические схемы алгоритмов, где различные алгоритмические конструкции изображаются в виде определенных геометрических фигур (блоков), соединенных в последовательности их выполнения. Например, блоксхема – это графическая форма записи алгоритма. 4) Способ, использующий псевдокоды.  Псевдокод – это интерпретация шагов алгоритма на обычном языке, которая описывает действие команд. Псевдокод ориентирован на человека, но облегчает перевод на язык программирования, т.к. требует соблюдения определенных правил записи. Пример псевдокода: школьный алгоритмический язык. 2.2. Типовые блоки для записи алгоритма в виде блок-схемы 18 2.3. Основные типы алгоритмов В зависимости от особенностей своего построения алгоритмы делятся на 3 основные группы: 1) линейные. 2) разветвляющиеся. 3) циклические. Разнообразие алгоритмов определяется тем, что любой алгоритм распадается на части и каждая часть представляет собой алгоритм одного из 3 указанных типов. 2.3.1. Линейные алгоритмы  Линейный алгоритм – это алгоритм, в котором действия выполняются последовательно, одно за другим. На школьном алгоритмическом языке линейный алгоритм выглядит следующим образом: … Команда 1 Команда 2 Команда 3 … Команда N … Графическая схема линейного алгоритма: 2.3.2. Разветвляющиеся алгоритмы  Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от выполнения (невыполнения) некоторого условия выполняется одна из двух серий команд. Если <условие> то <серия команд 1> иначе <серия команд 2> конец ветвления 19 2.3.3. Циклические алгоритмы  Циклический алгоритм – это алгоритм, в котором выполнение одной и той же последовательности действий повторяется несколько раз.  1) Цикл с параметром: Для <имя параметра> от <начальное значение параметра> до <конечное значение параметра > шаг <шаг изменения параметра> Нц <тело цикла> да нет кц Условие 2) Цикл с предусловием пока <условие> Нц <тело цикла> кц Тело цикла 3) Цикл с постусловием повторять <тело цикла> до <условие> Тело цикла нет 2.4. Алгоритмизация, как Условие один из основных да этапов создания программы Процесс создания программы Постановка задачи Алгоритмизация решения задачи Программирование Эксплуатация 20  Постановка задачи – определение содержательной стороны обработки данных: конкретизация основных параметров, входных и выходных данных, их структуры.  Входные данные – данные, используемые для решения задачи.  Выходные данные – результаты, представленные в форме документов, файлов, управляющего сигнала и т.п.  Компьютерная программа – это комбинация компьютерных инструкций и данных, позволяющая аппаратному обеспечению вычислительной системы выполнять вычисления или функции управления  Программирование – с одной стороны, это создание программ, но это также и отрасль хозяйственной деятельности, связанная с затратами материальных, трудовых и финансовых ресурсов. Рис. 1. Этапы создания программы 21 2.5. Алгоритмы работы с величинами (с примерами) Величина – это отдельный информационный объект, который имеет имя, значение и тип. Величины бывают постоянными и переменными. Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма. Константа может обозначаться собственным значением (числа 10, 3.5) или символьным именем (число). Переменная величина (переменная) может изменять значение в ходе выполнения алгоритма. Переменная всегда обозначается символическим именем (X, A, R5 и т.п.). Тип величины определяет множество значений, которые может принимать величина, и множество действий, которые можно выполнять с этой величиной. Основные типы величин: целый, вещественный, символьный, логический. Выражение – запись, определяющая последовательность действий над величинами. Выражение может содержать константы, переменные, знаки операций, функции. Например: A+B, 2*X-Y, K+L-sin(X). Команда присваивания – команда исполнителю, в результате которой переменная получает новое значение. Формат команды: Имя_переменной=выражение; Исполнение команды присваивания происходит в таком порядке: сначала вычисляется выражение, затем полученное значение присваивается переменной. Пример 1. Пусть переменная А имела значение 6. Какое значение получит переменная А после выполнения команды: А=2*А-1. Решение. Вычисление выражения 2*А-1 при А=6 даст число 11. Значит новое значение переменной А будет равно 11. Пример 2. (Циклическая перестановка.) Написать последовательность команд присваивания, в результате выполнения которых переменные А и В поменяются местами. Решение. Для решения этой задачи потребуется еще одна дополнительная переменная С. С=А; A=B; B=C; Составим трассировочную таблицу для начальных значений A=3, B=7. A 3 3 7 3 B 7 7 7 7 C 3 3 3 Любой алгоритм может быть построен из команд присваивания, ввода, вывода, ветвления и цикла. Команда ввода – команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру). 22 Пример. Ввод А; – ввод значения переменной А с клавиатуры компьютера. Команда вывода – команда, по которой значение величины отражается на устройстве вывода компьютера (например, на экран дисплея). Пример. Вывод Х ;– значение переменной Х выводится на экран. Команда ветвления – разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгоритма выходит на общее продолжение. Ветвление бывает полное и неполное. Полное ветвление: если (условие) то действие 1 иначе действие 2 кв Неполное ветвление: если (условие) то действие кв Пример. Записать алгоритм нахождения большего из двух чисел А и В. 23 Решение. алг максимальное число вещ А,В нач ввод А,В; если (А>B) то вывод А; иначе вывод В; кв кон Команда цикла Команда цикла обеспечивает повторное выполнение последовательности команд (тела цикла) по некоторому условию. Циклы бывают трех типов: цикл с параметром, цикл с предусловием и цикл с постусловием. Цикл с предусловием – цикл, выполнение которого повторяется, пока истинно условие цикла: пока (условие) нц тело цикла кц Пример. Вывести на экран заданное количество приветствий. 24 Решение. алг Привет цел i нач ввод i пока (i>0) нц вывод ―Привет; i=i-1; кц кон Цикл с постусловием – цикл, выполнение которого выполняет, пока истинно условие цикла, которое располагается после тела цикла. нц тело цикла кц пока (условие) Тело цикла с предусловием может ни разу не выполняться, если условие продолжения цикла сразу не выполняется. Цикл с постусловием выполняется всегда, по крайней мере, один раз. Пример. Вывести на экран заданное количество приветствий. Решение. алг Привет цел i нач ввод i 25 нц вывод ―Привет‖; i=i-1; кц пока (i>0); кон Недостатком данного алгоритма в отличие от предыдущего является то, что строка ―Привет выведется на экран даже в том случае, если пользователь введет неположительное число i (целое – не означает только положительные). 19 Цикл с параметром –повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik) c шагом k. для i от In до Ik шаг k нц тело цикла кц Пример. Вывести на экран заданное количество приветствий. Решение. алг Привет цел n, i нач ввод n; для i от 1 до n шаг 1 нц вывод ―Привет‖; кц кон Итак, любая задача может быть разбита на элементарные действия. Для любой математической задачи или ситуации из жизни можно составить алгоритм решения. Алгоритм может быть описан словесно, псевдокодом, графически или 26 программно. Задача всегда решается с помощью базовых типов алгоритма – линейного, разветвляющегося или циклического. Задание 1 1. Составьте алгоритмы по походу в магазин за яблоками. Используйте линейный и разветвляющийся алгоритмы. Реализуйте их словесно. 2. Составьте алгоритм по нахождению корней квадратного уравнения через дискриминант. Используйте разветвляющийся алгоритм. Реализуйте его псевдокодом. 2.6. Алгоритмы поиска словесной информации Прочитайте: https://intuit.ru/studies/courses/648/504/lecture/11468 27 Раздел 2. Структуры данных 2.1. Понятие и примеры структур данных Структуры данных и алгоритмы – это основные составляющие, из которых строятся программы. Структуры данных предназначены для удобного хранения и доступа к информации.  Структура данных – способ организации хранения данных и доступа к ним, предназначенный для выполнения определённого набора операций над этими данными. Для каждой структуры вводится понятие удобных и неудобных операций. Удобные операции – те, которые выполняются при использовании быстрее, чем при использовании других структур. Неудобные операции – те, которые либо не могут быть выполнены, либо те, которые выполняются медленнее по сравнению с другими структурами. Основные структуры данных: массивы, стеки, очереди, связанные списки, графы, деревья, префиксные деревья, хэш таблицы. Простейшие структуры данных: массив, линейный однонаправленный список, стек, очередь. Например, Массив – это именованная совокупность фиксированного количества пронумерованных однотипных данных. Удобные операции:  доступ к элементу массива по индексу;  просмотр элементов по возрастанию индексов;  поиск элемента по значению в упорядоченном массиве. Неудобные операции:  вставка элементов в произвольное место массива и удаление из произвольного места;  поиск элемента по значению в неупорядоченном массиве. Массив относят к статическим структурам данных. Т.е. память под 28 массив выделяется один раз. Даже если рассматривать динамический массив, то объем памяти, выделенной при его создании остается неизменным до уничтожения массива. Динамические структуры данных характеризуются тем, что элементы этой структуры расположены по произвольным адресам памяти. Для установления связи между элементами используются указатели. Элемент динамической структуры состоит как минимум из полей двух типов: 1) информационного поля, в котором содержатся те данные, ради которых создается структура; 2) поля связок, в которых содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры. Пример динамической структуры данных: Список – совокупность элементов, каждый из которых, кроме последнего, содержит информацию (ссылку) о следующем элементе. Отдельно должна храниться информация о первом элементе списка. Удобные операции над списками:  вставка в заранее определённое место списка;  удаление из заранее определённого места списка. Неудобные операции над списками:  поиск элемента по значению;  доступ к элементу по его номеру. Линейные структуры данных – это структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов. Например, Динамические линейные структуры: 1) Очередь – добавление – в конец, а удаление – из начала. 2) Стек –добавление и удаление с одной стороны. 3) Дек –добавление и удаление с двух сторон. 29 Нелинейные структуры данных – это структуры данных, у которых связи между элементами зависят от выполнения определенного условия. Это структуры данных, которые выражают более сложные отношения порядка между объектами, чем отношения предшествования и следования. Например, Графы, деревья. Древовидные структуры позволяют определить такие отношения, как предок, потомок, брат и т.п. 2.2. Классификация абстрактных структур данных Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, представленные в таком виде, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации данных получают на основе понятия «структуры данного». Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. При этом различают физическую и абстрактную структуры данных.  Понятие физическая структура данных отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.  Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или логической структурой. Рассмотрим классификацию структур данных. {абстрактных} 30 Различают ПРОСТЫЕ (базовые) структуры данных и СЛОЖНЫЕ (интегрированные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Сложными называются такие структуры данных, составными частями которых являются другие структуры данных – простые или в свою очередь сложные. Сложные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования. Одним из важных признак структуры данных является ее изменчивость – изменение числа элементов или связей между элементами структуры. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки). 31 Важный признак структуры данных – характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ (переход от одного элемента данных к другому не зависит от каких-либо логических условий) И НЕЛИНЕЙНЫЕ структуры. В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур – многосвязные списки, деревья, графы (связи между элементами зависят от выполнения определенного условия). Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. 2.3. Связный список 2.3.1. Виды связных списков Если в программе необходимо хранить неупорядоченное множество элементов, число которых заранее известно, то логично использовать массив. Но если число элементов постоянно меняется, то в таких случаях для хранения применяют динамические структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Связный список представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном. Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. 32 По типу связности выделяют односвязные (или однонаправленные), двусвязные (или двунаправленные), XOR-связные, однонаправленные, кольцевые и некоторые другие списки. {Исключающее ИЛИ (XOR) – в случае двух переменных результат выполнения операции истинен тогда и только тогда, когда один из аргументов истинен, а другой – ложен} В случае односвязного списка поле связок next, будет указывать на следующий элемент (поле содержит адрес следующего элемента). В двусвязном списке добавляется еще поле prev, содержащее указатель на предыдущий элемент. Если элемент не связан ни с каким другим, то в поле указателя записывают значение NULL. Указателем на первый элемент списка является особый элемент, называемый head. Рис. 1. Структура односвязного линейного списка Рис. 2. Структура односвязного кольцевого списка Опишем тип данных для хранения элементов односвязного списка: struct zveno {int info; //информационное поле zveno *next; //поле связки элементов, указатель на следующий элемент }; 33 Классический двунаправленный или двусвязный список хранит в каждом элементе отдельно адреса предыдущего и следующего своего соседа, для хранения которых требуется два указателя: struct zveno {int info; //информационное поле zveno *next; //поле связки элементов, указатель на следующий элемент zveno *prev; //поле связки элементов, указатель на предыдущий элемент }; Рис. 3. Структура двусвязного линейного списка XOR-связный список это структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранится только один составной адрес – результат выполнения операции XOR (исключающее или) над адресами предыдущего и следующего элементов списка. {Исключающее ИЛИ (XOR ) – в случае двух переменных результат выполнения операции истинен тогда и только тогда, когда один из аргументов истинен, а другой – ложен} Рис. 4. Структура XOR списка 34 Таким образом, в нашем списке в поле next для элемента a хранится cb, для b – ac, для c – ba. 2.3.2. Операция добавления элемента в односвязный линейный список Алгоритм добавления элемента в односвязный линейный список: 1) Создать новый элемент списка 2) Определить место вставки. 3) Включить элемент в список. Самым простым вариантом является добавление элемента в начало списка. Рис. 5. Вставка элемента в начало списка Рис. 6. Вставка элемента в конец списка Рис. 7. Вставка элемента в середину списка 35 2.3.3. Операция удаления элемента из односвязного линейного списка Алгоритм удаления элемента: 1) найти элемент, удовлетворяющий условию, 2) переставить указатель, 3) удалить элемент. Рис. 8. Удаление элемента из середины списка Отдельным случаем является удаление первого элемента, когда нужно переместить указатель головы списка. 2.3.4. Реализация односвязных и двусвязных списков в C# (Классы List и LinkedList ) Для того, чтобы понять внутреннюю структуру списка необходимо рассматривать элементарную реализацию данной динамической структуры. Примеры такой реализации на элементарном уровне предложены в лекции выше и на практике по ссылке (см. ЛР8_2). Д/з: прочитать и разобраться! На практике в C# динамическая структура данных «Связный Список» уже реализована намного лучше внутри платформы .NET в виде Классов List (односвязный список) и LinkedList (двухсвязный список). На ЛР мы используем именно эти классы и их методы. (методы см. по ссылке: https://metanit.com/sharp/tutorial/4.5.php) I. Класс List Фирмой Microsoft разработаны коллекции с обобщенными типами (их ещё называют дженерики), они расположены в пространстве имен System.Collections.Generic. Суть их заключается в том, что мы не просто создаём объект класса List, но и указываем, объекты какого типа будут в нем 36 храниться, делается это так: List, где T может быть int, string, double (любой встроенный тип) или какой-то ваш собственный. List представляет простейший односвязный список однотипных элементов, доступных по индексу, с динамически изменяемым размером. Создание объекта класса List 1 способ: List numsList = new List(); // создание пустого списка numsList.Add(1); // добавление в список элемента с помощью метода Add() 2 способ (через указание набора объектов, который будет храниться в списке): List nums = new List {1, 2, 3, 4, 5}; var words = new List {"one", "two", "three"}; Работа с объектами List Рассмотрим некоторые полезные свойства и методы класса List. Свойства класса List СВОЙСТВО ОПИСАНИЕ ПРИМЕР Count Количество элементов в Console.WriteLine($"Количество списке элементов в списке {nums.Count}."); Capacity Емкость списка – Console.WriteLine($"Емкость количество элементов, списка= {nums.Capacity}."); которое может вместить список без изменения размера = {Для встраивания отдельных значений в выводимую на консоль строку используются фигурные скобки, в которые заключается встраиваемое значение. Это может быть значение переменной ({name}) или более сложное выражение (например, операция сложения {4 + 7}). А перед всей строкой ставится знак доллара $.} Capacity – это число элементов, которое в List может храниться до изменения размера, в то время как Count – это количество элементов, которые фактически находятся в List. Capacity всегда>= Count . При добавлении элементов, если Count превышает Capacity, тогда Capacity автоматически увеличивается. 37 Если емкость значительно больше, чем число, и необходимо уменьшить объем памяти, используемой объектом List , можно уменьшить емкость, вызвав TrimExcess метод или Capacity, явно задав для свойства более низкое значение. Методы класса List МЕТОД Add(T) ОПИСАНИЕ Добавляет элемент к списку ПРИМЕР words.Add("Четыре"); BinarySearch(T) Выполняет поиск по списку. Использует алгоритм двоичного поиска для нахождения определенного элемента в отсортированном списке List или в его части. Возвращает индекс элемента, отсчитываемый от нуля, если элемент найден. В противном случае – отрицательное число, которое является поразрядным дополнением индекса следующего элемента, большего, чем искомый элемент, или, если большего элемента не существует, поразрядным дополнением значения Count. Вставляет элемент в указанную позицию Возвращает true, если список содержит указанный элемент int index = words.BinarySearch("EFGH"); if (index < 0) { words.Insert(~index, "EFGH"); } Insert(Int32, T) Contains(T) {~ - это побитовое отрицание. Работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита. Например, a = 65; b = ~a; Выведет -66, так как 65 это 01000001, а инверсия даст 10111110 (а это число 66)} См. выше // Проверка наличия элемента перед его добавлением. if (!nums.Contains(6)) //Если 6 не входит (у нас это True) { nums.Add(6); } {! - Оператор логического отрицания} 38 IndexOf(T) Возвращает отсчитываемый от нуля индекс первого вхождения элемента во всем списке, если он найден; в противном случае -1. ForEach(Action) Выполняет указанное действие для всех элементов списка Console.WriteLine (words.IndexOf("two")); //выведет 1 Console.WriteLine (words.IndexOf("one", 1, 2)); //выведет -1, т.к. нет этого элемента при просмотре среди элементов с 1-го двух элементов. Элементы считаются с нуля. IndexOf(T, Int32) //Осуществляет поиск указанного объекта и возвращает отсчитываемый от нуля индекс первого вхождения в диапазоне элементов списка List, начиная с заданного индекса (Int32) и до последнего элемента. // Вывод элементов списка. foreach(var item in nums) { Console.WriteLine(item); } find = words.Find(x => x == "abc"); {оператор => используется для отделения входных параметров с левой стороны от тела лямбдавыражения с правой стороны} // Получение элемента списка по индексу. var firstElement = nums[0]; Console.WriteLine(firstElement); // Удаление элемента из списка. nums.Remove(firstElement); words.Remove("two"); // Удаление элемента из списка по индексу. words.RemoveAt(1); nums.Sort(); nums. Reverse(); Find(Predicate) Осуществляет поиск первого элемент, для которого выполняется заданный предикат Remove(T) Удаляет указанный элемент из списка RemoveAt(Int32) Удаляет элемент заданной позиции Sort() Reverse() Сортирует список Меняет порядок расположения элементов на противоположный Очистка списка nums.Clear(); Clear() из 39 Прочитайте про Коллекции в языке https://devpractice.ru/c-sharp-lesson-10-generics/ C#. Ссылка: Класс Dictionary реализует структуру данных Отображение, которую иногда называют Словарь или Ассоциативный массив. Кортежем называют структуру данных типа Tuple или ValueTuple. II. Класс LinkedList Класс LinkedList представляет двухсвязный список, в котором каждый элемент хранит ссылку одновременно на следующий и на предыдущий элемент. Это динамичная коллекция, которая растет в соответствии с потребностями вашей программы. Это также обеспечивает быструю вставку и удаление элементов. Создание объекта класса LinkedList 1 способ: LinkedList my_list1 = new LinkedList(); //создали пустой список my_list1.AddLast("Первый"); // добавляем элементы my_list1.AddLast("Второй"); 2 способ: string[] wordsMass = { "сент", "окт", "нояб" }; // Создаем массив строк LinkedList my_list2 = new LinkedList(wordsMass); // Создаем объект связанного списка и инициализируем его массивом строк Работа с объектами LinkedList Рассмотрим некоторые свойства и методы класса LinkedList. Если в простом списке List каждый элемент представляет объект типа T, то в LinkedList каждый узел представляет объект класса LinkedListNode. Этот класс имеет следующие свойства: 40 Свойства класса LinkedList СВОЙСТВО ОПИСАНИЕ Value само значение узла, представленное типом T Next ссылка на следующий элемент типа LinkedListNode в списке. Если следующий элемент отсутствует, то имеет значение null Previous ссылка на предыдущий элемент типа LinkedListNode в списке. Если предыдущий элемент отсутствует, то имеет значение null Count Получает число узлов, которое в действительности хранится в LinkedList First Получает первый узел объекта LinkedList Last Получает последний узел объекта LinkedList ПРИМЕР // Вывод последнего узла LinkedList if (myList1.Count > 0) Console.WriteLine(myList1.Last.Value); else Console.WriteLine("Список пуст"); Используя методы класса LinkedList, можно обращаться к различным элементам, как в конце, так и в начале списка. Методы класса List МЕТОД ОПИСАНИЕ ПРИМЕР для добавления нового См. выше узла или значения: после * существующего узла в  AddAfter LinkedList; перед существующим  AddBefore узлом; в начале;  AddFirst в конце.  AddLast для удаления всех узлов * Clear () из LinkedList; Remove (LinkedListNode) для удаления указанного узла из LinkedList; для удаления первого Remove(Т) вхождения указанного значения из LinkedList; RemoveFirst() удаляет первый узел из списка. После этого новым первым узлом 41 RemoveLast() foreach Contains (T) становится узел, следующий за удаленным; удаляет последний узел из списка Выполняет указанное // Доступ к элементам действие для всех foreach(string str in my_list1) элементов списка { Console.WriteLine(str);} // создаем строковый массив и переносим туда все элементы из связанного списка: string[] strArray = new string[my_list2.Count]; my_list2.CopyTo(strArray,0); foreach (string s in strArray) { Console.WriteLine(s); } Для определения, if (my_list1.Contains("первый") находится ли значение в == true) LinkedLis {Console.WriteLine("Элемент найден"); } 42 2.4. Стек Стек – это абстрактная структура данных, включение и исключение элементов из которой выполняются только с одной стороны, называемой вершиной стека. Стек – это контейнер, работающий по принципу "последний вошёл – первый вышел" (last in, first out – LIFO). Основные операции над стеком – включение нового элемента (англ. push – заталкивать) и исключение элемента из стека (англ. pop – выскакивать). Вспомогательные операции: определение текущего числа элементов в стеке, очистка стека, чтение элемента с вершины стека. Рис. 9 Стек Реализовать эту структуру данных можно на основе массива, линейного списка или коллекции Stack (в C#). Рассмотрим пример реализации основных операций со стеком в C# на основе коллекции Stack. {https://metanit.com/sharp/tutorial/4.7.php} Класс Stack Класс Stack представляет коллекцию переменного размера экземпляров одинакового заданного типа, которая использует алгоритм LIFO ("последний вошел – первый вышел"). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции 43 происходит в обратном порядке – извлекается тот элемент, который находится выше всех в стеке. Создание объекта класса Stack 1 способ: Stack numbers = new Stack(); //создали пустой стек // добавляем элементы: numbers.Push(3); // в стеке 3 numbers.Push(5); // в стеке 5, 3 numbers.Push(8); // в стеке 8, 5, 3 2 способ: string[] wordsMass = { "сент", "окт", "нояб" }; // Создаем массив строк Stack my_stack2 = new Stack(wordsMass); // Создаем стек, который содержит элементы, скопированные из указанного массива строк Работа с объектами Stack Свойства и методы класса Stack СВОЙСТВО, ОПИСАНИЕ МЕТОДЫ Получает число Count (свойство) элементов, хранящихся в стеке СоруТо Push ПРИМЕР // Вывод массива, сформированного из стека (выводит стек в обратном порядке) int[] Му_array = new int[numbers.Count]; // создаём массив, той же размерностью, что и стек numbers.CopyTo(Му_array, 0); // Копируем элементы коллекции в массив, начиная с указанного индекса массива for (int i = 0; i < numbers.Count; i++) { Console.WriteLine(Му_array[i]); } Стек заполняли: 3,5,8 Массив: 8, 5, 3 (т.к. с конца достаём) См. выше Копирует элементы коллекции добавляет элемент См. выше в вершину стека 44 Pop удаляет и возвращает элемент из вершины стека int n = numbers.Pop(); // в стеке 5, 3 Console.WriteLine(n); // выведет 8 // так как вверху стека будет находиться число 8, то оно и извлекается Peek возвращает элемент из вершины стека, не удаляя его при этом проверяет наличие элемента в стеке и возвращает true в случае нахождения его там Выполняет указанное действие для всех элементов списка * Удаляет все объекты из стека my_stack2.Clear(); Contains Foreach Clear if (numbers.Contains(5) == true) {Console.WriteLine("Элемент найден"); } //Вывод всех элементов стека foreach (int m in numbers) Console.WriteLine(m); Подробнее см. на https://docs.microsoft.com/ruru/dotnet/api/system.collections.generic.stack-1?view=netcore-1.1#code-try-4 (другие методы) 45 2.5. Очередь Очередь – это абстрактная структура данных, включение элементов в которую выполняется только с одной стороны, а исключение только с другой. Очередь – это контейнер, работающий по принципу "первый пришёл – первый вышел» (first in, first out – FIFO)." Рис. 10 Очередь Реализовать очередь можно на основе массива, односвязного списка, двусвязного списка или коллекции Queue (в C#) (читается [kjuː]). Рассмотрим пример реализации основных операций с очередью в C# на основе коллекции Queue. {https://metanit.com/sharp/tutorial/4.7.php} Класс Queue Класс Queue представляет очередь, работающую по алгоритму FIFO ("первый вошел – первый вышел"). Создание объекта класса Queue 1 способ: Queue queue1 = new Queue(); //создали пустую очередь // добавляем элементы: queue.Enqueue("А"); queue.Enqueue("Б"); queue.Enqueue("В");/ / в очереди В, Б, А 2 способ: string[] wordsMass = { "сент", "окт", "нояб" }; // Создаем массив строк Queue my_Queue2 = new Queue(wordsMass); // Создаем очередь, которая содержит элементы, скопированные из указанного массива строк 46 Работа с объектами Queue Свойства и методы класса Queue СВОЙСТВО, ОПИСАНИЕ ПРИМЕР МЕТОДЫ Получает число // Создаём массив в два раза больше очереди и Count (свойство) элементов, хранящихся в копируем элементы очереди, начиная с стеке середины массива. string[] array2 = new string[numbers.Count * 2]; numbers.CopyTo(array2, numbers.Count); Копирует элементы См. выше СоруТо коллекции Добавляет объект в См. выше Enqueue конец очереди Удаляет объект из // получаем первый элемент очереди (А) Dequeue начала очереди и string m = queue1.Dequeue(); возвращает его //теперь очередь В, Б Console.WriteLine(m); //Вывод А Peek ToArray Contains Foreach Clear Возвращает объект, находящийся в начале очереди, но не удаляет его Копирует элементы очереди в новый массив проверяет наличие элемента в стеке и возвращает true в случае нахождения его там Выполняет указанное действие для всех элементов очереди Удаляет все объекты из очереди * var array2 = queue1.ToArray(); if (numbers.Contains(5) == true) {Console.WriteLine("Элемент найден"); } //Вывод всех элементов очереди foreach (int m in numbers) Console.WriteLine(m); my_stack2.Clear(); Подробнее см. на https://docs.microsoft.com/ruru/dotnet/api/system.collections.generic.queue-1?view=netcore-1.1 (другие методы) 47 2.6. Дек Дек – упорядоченный набор элементов, в котором добавление новых и удаление элементов допустимо с обоих концов (двусторонняя очередь). Рис. 11 Дек Реализовать дек можно на основе массива, двусвязного списка или коллекции Deque (в C#). Рассмотрим пример реализации основных операций с деком в C# на основе коллекции Deque. { https://metanit.com/sharp/algoritm/2.6.php} Пример: Deque D1 = new Deque(); // создали пустой дек // добавляем элементы: Консольный вывод примера: D1.AddFirst("Алиса"); Алиса D1.AddLast("Катя"); Катя D1.AddLast("Толя"); Толя // выводим элементы дека на экран: foreach(string s in D1) Удален: Алиса Console.WriteLine(s); Катя // удаляем и выводим первый элемент из дека: string S = D1.RemoveFirst(); Толя Console.WriteLine("Удален: "+S); // выводим оставшиеся элементы дека: foreach (string s in D1) Console.WriteLine(s); 48 2.7. Деревья. Бинарные деревья. Красно-чёрные деревья В моодле посмотрите видеолекцию по графам. Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации. Граф – это непустое множество точек (вершин) и множество отрезков (рёбер) концы которых принадлежат заданному множеству точек. Граф=вершины (узлы) + рёбра (дуги) Если на каждом ребре задать направление, то граф будет ориентированным. Если, двигаясь по рёбрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путём. Замкнутый путь, состоящий из различных рёбер, называется циклом. Граф называется связным, если любые две его вершины соединены путём. Рис. 12. Несвязный граф с циклом Дерево – связный граф без циклов. Рис. 13. Дерево Рис. 14. Ориентированное дерево С каждой вершиной (узлом) дерева связывается конечное число отдельных деревьев, называемых поддеревьями. 49 Теорема (о числе ребер дерева). Если в дереве n вершин и m ребер, то m=n-1. Следствие 1 из теоремы. Если в графе, не имеющем циклов, n вершин и m ребер и m=n-1, то этот граф – дерево. Следствие 2. Если в связном графе n вершин и m ребер и m=n-1, то этот граф – дерево. Корневым деревом называют дерево с выделенной вершиной – корнем. Высота корневого дерева – это расстояние от корня до самого удаленного листа. Если в корневом дереве путь, соединяющий вершину х с корнем, проходит через вершину y, то говорят, что y – предок x, а x– потомок y. В частности, каждая вершина является предком и потомком самой себя. Предок (потомок) вершины, отличный от нее самой, называется собственным предком (потомком). Множество всех предков вершины порождает путь из корня в эту вершину. Множество всех потомков вершины x порождает дерево с корнем x, оно называется ветвью (поддеревом) дерева в вершине x. Если предок и потомок соединены ребром, то они называются соответственно отцом и сыном. Компактный и полезный во многих случаях способ задать корневое дерево состоит в указании для каждой вершины ее отца (отцом корня иногда считают саму эту вершину). Если вершина не имеет потомков, кроме себя, то она называется терминальной (висячей) вершиной или листом, если имеет, то называется внутренней вершиной. В дереве имеется не менее двух листьев. Количество собственных потомков вершины называется её степенью. Степень дерева – это максимальная степень вершин, входящих в дерево. Например: Вершина степени 0 в дереве – это лист. Вершина x на рисунке 13 имеет степень 3. Вершина d3 на рисунке 14 имеет степень 1. Степень дерева на рисунке 13 =3. Степень дерева на рисунке 14 =2. 50 Двоичное (бинарное) дерево – это дерево, в котором из каждой вершины исходит не более двух рёбер. (2, 1, 0 рёбер). Пример – на Рис. 14. Дерево называют полным бинарным деревом, когда у каждой ветви 2 потомка, а все листья находятся в одном ряду. Рис. 15. Полное бинарное дерево Сбалансированное дерево – это дерево, у которого (в идеале) у каждого узла слева и справа одинаковое количество потомков. Примером сбалансированных деревьев являются RB деревья. Красно-чёрное дерево (англ. red-black tree, RB tree) – двоичное дерево поиска, в котором баланс осуществляется на основе цвета узла дерева, который принимает только два значения: "красный" (red) и "чёрный" (black). Рис. 16. Красно-чёрное дерево Как бинарное дерево, красно-черное обладает свойствами: 1) Оба поддерева являются бинарными деревьями поиска. 2) Для каждого узла с ключом k выполняется критерий упорядочения: ключи всех левых потомков <= k < ключи всех правых потомков Это неравенство должно быть истинным для всех потомков узла, а не только его дочерних узлов. (Ключ – это значение, связанное с узлом дерева, по которому выполняется поиск) Свойства красно-черных деревьев: 51 1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета). 2) Корень окрашен в черный цвет. 3) Листья (так называемые NULL-узлы) окрашены в черный цвет. 4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные. 5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота). Красно-черные деревья не гарантируют строгой сбалансированности (разница высот двух поддеревьев любого узла не должна превышать 1). Но соблюдение свойств красно-черного дерева позволяет обеспечить выполнение операций вставки, удаления и выборки за время . Ассоциативные массивы в большинстве библиотек созданы именно с помощью красно-черных деревьев. Ассоциативные массивы в C# реализованы словарями – это класс Dictionary и хэш-таблицами (подробнее см. ниже). * Реализацию структуры данных бинарное дерево и методов добавления, удаления и поиска узлов на C# посмотреть по ссылке: https://programm.top/c-sharp/datastructures/binary-tree/ 2.8. Хэш-таблицы в C#  Хэш-таблица – это структура данных, в которой все элементы хранятся в виде пары ключ-значение, где: ключ – уникальное число, которое используется для индексации значений; значение – это данные, которые с этим ключом связаны. Например, Рис. 17. Пара ключ-значение в Хэш-таблице хэш-таблица может содержать ряд IP-адресов и имен компьютеров, где IP-адреса являются ключами, а имена компьютеров – значениями, или наоборот. Ключ (IP-адрес ПК) Данные (имя ПК) 198.162.0.95 ПК1 198.162.0.115 ПК13 Рис. 18. Пример хэш-таблицы 52 Два основных вида хэш-таблиц: 1) хэш-таблица с открытой адресацией – это хэш-таблица, которая содержит некоторый массив, элементы которого есть пары, 2) хэш-таблица с цепочками – это хэш-таблица, которая содержит некоторый массив, элементы которого есть списки пар.  Хэширование (от англ. hashing) – это преобразование массива входных данных произвольной длины в битовую строку фиксированной длины, выполняемое определённым алгоритмом.  Хэш-функция – это функция, реализующая алгоритм хэширования.  Хэш (хэш-сумма, хэш-код) – это результат выполнения хэширования. Выполнение операции в хэш-таблице начинается с вычисления хэшфункции от ключа. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива. Ситуация, когда для различных ключей получается одно и то же хешзначение, называется коллизией. Механизм разрешения коллизий – важная составляющая любой хэш-таблицы. Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время O(1). Хеширование применяется в следующих случаях: 1) при построении ассоциативных массивов; 2) при поиске дубликатов (копий) в сериях наборов данных; 3) при построении уникальных идентификаторов для наборов данных; 4) при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (случайных или внесённых намеренно), возникающих при хранении или передаче данных; 5) при сохранении паролей в системах защиты в виде хэш-кода (для восстановления пароля по хэш-коду требуется функция, являющаяся обратной по отношению к использованной хэш-функции); 53 6) при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хэш-образ»). В C# хэш-таблицы реализованы при помощи коллекции Hashtable. Это неуниверсальный тип коллекции, который определен в пространстве имен System.Collections. Важные моменты применения Hashtable:  Элементы хэш-таблицы являются парой ключ/значение.  В хэш-таблице можно хранить элементы одного типа и разных типов.  Ключ должен быть уникальным. Дублирование ключей не допускается.  В Hashtable ключ не может быть нулевым, но значение может быть  ключевые 0. объекты должны быть неизменяемыми, если они используются в качестве ключей в Hashtable.  Емкость Hashtable – это количество элементов, которое может содержать Hashtable.  Хэш-функция предоставляется каждым ключевым объектом в Hashtable. Пример: using System.Collections; //!Подключить! Hashtable ht = new Hashtable();// Создаем хеш-таблицу ht.Add("А1", "12"); Консольный ht.Add("А2", "3M"); вывод примера: ht.Add("A3", "59"); // Добавили несколько записей A3: 59 ICollection keys = ht.Keys; // Считаем коллекцию ключей А1: 12 foreach (string s in keys) А2: 3M Console.WriteLine(s + ": " + ht[s]); Console.ReadLine(); Упорядоченные словари отличаются от хэш-таблиц тем, что ключи всегда отображаются в порядке их перечисления. Порядок ключей в хэш-таблице не определен. 54 Задание по Лекции «Хэш-таблицы в C#»: * Про конструкторы, свойства, методы коллекции Hashtable в C# прочитать по ссылке: https://docs.microsoft.com/ruru/dotnet/api/system.collections.hashtable?view=net-6.0 * Самостоятельно заполнить таблицу (минимум 10 строчек с примерами): Работа с объектами Hashtable Таблица 1. Конструкторы, свойства и методы класса Hashtable КОНСТРУКТОРЫ, СВОЙСТВА И МЕТОДЫ ОПИСАНИЕ ПРИМЕР 55 Выводы: Итак, структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других. Какие бывают структуры данных? Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди. Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья. Основные структуры данных. 1. 2. 3. 4. 5. 6. 7. 8. Массивы Стеки Очереди Связанные списки Графы Деревья Префиксные деревья Хэш таблицы Прочитайте для закрепления знаний: https://habr.com/ru/post/422259/ https://proglib.io/p/data-structures/#comments 56