Алгоритмы и структуры данных (syllabus): различия между версиями

Материал из Поле цифровой дидактики
 
(не показаны 34 промежуточные версии этого же участника)
Строка 1: Строка 1:
<center>
{|
|+ [[:Категория:ПБД221м]]
|[[Файл:Alg video01.png|500px]]| [[Файл:Alg video 05 Json PlantUML.png|400px]]
|
|}
</center>
{{Curriculum
{{Curriculum
|Learning_outcomes=; Цель
|Learning_outcomes=Цель
* теоретические знания и практический опыт в области основ алгоритмизации задач, классификации языков программирования, типов данных, структур данных, взаимосвязь алгоритмов и структур данных, особенностей реализации алгоритмов и типов данных в языках блочного программирования Scratch, Snap!, GP
* теоретические знания и практический опыт в области основ алгоритмизации задач, классификации языков программирования, типов данных, структур данных, взаимосвязь алгоритмов и структур данных, особенностей реализации алгоритмов и типов данных в языках блочного программирования Scratch, Snap!, GP
; Знать
; Знать
Основные понятия, связанные с миром алгоритмов и структур данных См. Категория:Понятие
: Основные понятия, связанные с миром алгоритмов и структур данных  
основы алгоритмизации задач, структуры данных;
: основы алгоритмизации задач, структуры данных;
типы данных, структуры данных;
: типы данных, структуры данных;
методы и алгоритмы поиска и сортировки данных;
: методы и алгоритмы поиска и сортировки данных;
; Уметь
; Уметь
* обращаться к внешним и внутренним данным из среды Semantic MediaWiki, уметь использовать различные типы данных внутри Semantic MediaWiki
* обращаться к внешним и внутренним данным из среды Semantic MediaWiki, уметь использовать различные типы данных внутри Semantic MediaWiki
Строка 14: Строка 22:
* проектировать и программировать линейные и разветвляющиеся структуры алгоритмов;
* проектировать и программировать линейные и разветвляющиеся структуры алгоритмов;
* планировать процесс реализации алгоритма при помощи псевдокода и диаграмм  
* планировать процесс реализации алгоритма при помощи псевдокода и диаграмм  
* использовать язык dgl и mermaid встраивать диаграммы алгоритмов в вики страницы  
* использовать язык '''dgl''' , mermaid, '''PlantUML''' встраивать диаграммы алгоритмов в вики страницы  
* представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
* представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
* создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
* создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
* оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
* оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
* использовать рекурсию в командах и процедурах, использовать рекурсию при создании собственных функций
* использовать рекурсию в командах и процедурах, использовать рекурсию при создании собственных функций
использовать объекты первого класса и лямбда исчисления.
* использовать объекты первого класса и лямбда исчисления.
|Description=Содержание
; 1. Введение в алгоритмы и структуры данных
* Определение алгоритма и структуры данных
; 2. Основные алгоритмы
* Линейный поиск
* Бинарный поиск
* Сортировка (вставками, выбором, слиянием, быстрая сортировка)
* Рекурсия и рекурсивные алгоритмы
; 3. Структуры данных
* Массивы и связные списки
* Стеки и очереди
* Деревья (бинарные, сбалансированные, двоичные деревья поиска)
* Графы (ориентированные и неориентированные, поиск в глубину и ширину)
|Environment=Snap!, R, RStudio, Lua, Python
|Book=Стили и методы программирования, Computer Science with Snap! by Examples, Initiation to Algorithmics with Scratch
}}
}}
Учебная группа, работающая с курсом Алгоритмы и структуры данных данных в в 2022 году -  [[:Категория:ПБД211М|ПБД211М]]
; Учебная группа, работающая с курсом Алгоритмы и структуры данных данных в в 2023 году -  [[:Категория:ПБД221м|ПБД221м]]
* Учебная группа, работающая с курсом Алгоритмы и структуры данных данных в в 2022 году -  [[:Категория:ПБД211М|ПБД211М]]
 
; Особенность курса - [[Active Essay]]  смотрим и тестируем на поле


<graphviz>
<scratchblocks>
digraph Digida1 {
when [up arrow v] key pressed
layout = "neato";
point in direction (0)
node[color="#2471A3",fontsize=12, fontcolor="white",style=filled, shape="box"] ;
move (10) steps
видеоигры  ;
when [down arrow v] key pressed
паттерны ;
point in direction (180)
сообщества ;
move (10) steps
компетенции ;
when [right arrow v] key pressed
роботы ;
point in direction (90)
писатели ;
move (10) steps
книги ;
when [left arrow v] key pressed
участники ;
point in direction (-90)
события ;
move (10) steps</scratchblocks>


node[color="#FF0000",fontsize=14, fontcolor="white",style=filled, shape="box"] ;
: И смотрим на то, как они выполняются
языки ;
<scratch project="210120481" />
понятия;
: или в [[Snap!]]
рецепты ;
диаграммы ;
данные
}
</graphviz>


<snap project="Flocking_Snap" user="patarakin" />


== Цель, результаты освоения дисциплины ==
== Цель, результаты освоения дисциплины ==
Строка 64: Строка 86:
# проектировать и программировать  линейные и  разветвляющиеся структуры алгоритмов;
# проектировать и программировать  линейные и  разветвляющиеся структуры алгоритмов;
# планировать процесс реализации алгоритма при помощи псевдокода и диаграмм - [[:Категория:Diagrams]]
# планировать процесс реализации алгоритма при помощи псевдокода и диаграмм - [[:Категория:Diagrams]]
# использовать язык dgl и [[mermaid]] встраивать диаграммы алгоритмов в вики страницы см. Graphviz + [[:Категория:Diagrams]] -  
# использовать язык [[graphviz]], [[mermaid]], [[PlantUML]] встраивать диаграммы алгоритмов в вики страницы см. Graphviz + [[:Категория:Diagrams]] -  
# представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
# представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
# создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
# создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
Строка 123: Строка 145:
Список случайных чисел из  %сколько от %min до %max
Список случайных чисел из  %сколько от %min до %max
[[Файл:Table sprite.png|800px]]
[[Файл:Table sprite.png|800px]]
===  Структуры данных ===
[[Файл:Collab dataset JSON.png]]
* [[Массив]]ы и связные [[список|списки]]
* Стеки и очереди
* Деревья (бинарные, сбалансированные, двоичные деревья поиска)
* Графы (ориентированные и неориентированные, поиск в глубину и ширину)


=== Алгоритмы сортировки и поиска ===  
=== Алгоритмы сортировки и поиска ===  
Сравнение эффективности и вычислительной сложности алгоритмов
Сравнение эффективности и вычислительной сложности алгоритмов
* [[Временная сложность алгоритма]]
* [[Временная сложность алгоритма]]
* https://snap.berkeley.edu/snap/snap.html#present:Username=patarakin&ProjectName=Time_consumpion
<snap project="Time_consumpion" user="patarakin" />


=== Рекурсия ===
=== Рекурсия ===
* [[Рекурсия]]
* [[Рекурсия]]
* [[Фрактал]]
* [[Фрактал]]
[[Файл:Tree recursion.png|800px]]


== Литература ==
== Литература ==
=== Основная литература  ===
=== Основная литература  ===
# [[Стили и методы программирования]],
# [[Computer Science with Snap! by Examples]],
# [[Initiation to Algorithmics with Scratch]]


=== Дополнительная литература  ===
=== Дополнительная литература  ===
https://snap.berkeley.edu/snap/help/SnapManual.pdf - Руководство по Snap!
https://snap.berkeley.edu/snap/help/SnapManual.pdf - Руководство по Snap!


== Видеоматериалы ==
== Критерии оценки по дисциплине (2022 - 2023) ==
 
== Критерии оценки по дисциплине ==


{| {{prettytable}}
{| {{prettytable}}
Строка 170: Строка 205:
* [[Flowchart]]
* [[Flowchart]]
|-  
|-  
| Умеет создавать собственные блоки (команды и процедуры с входными параметрами) в среде [[Snap!]] (создавать функции с использованием различных типов данных))
| Умеет создавать собственные блоки (команды и процедуры с входными параметрами) в среде [[Snap!]] (создавать [[Функция|функции]] с использованием различных типов данных))
| Основные характеристики изучаемого алгоритмического языка
| Основные характеристики изучаемого алгоритмического языка
| Процедуры видоизменения данных в среде [[Snap!]]
| Процедуры видоизменения данных в среде [[Snap!]]
Строка 176: Строка 211:
|-  
|-  
| оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
| оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
| Алгоритмы сортировки и поиска
| [[Алгоритм]]ы сортировки и поиска
| Сравнить эффективность выполнения процедур над данными
| Сравнить эффективность выполнения процедур над данными
| Готовые [[датасет]]ы из категории [[:Category:Dataset]]. [[Сортировка вставками]], [[Быстрая сортировка]]
| Готовые [[датасет]]ы из категории [[:Category:Dataset]]. [[Сортировка вставками]], [[Быстрая сортировка]]
Строка 185: Строка 220:
| [[Рекурсия]], [[Фрактал]]
| [[Рекурсия]], [[Фрактал]]
|}
|}
== Напоминание по работа в вики среде ==
; [[Мастер-класс «Совместная работа со знаниями на поле цифровой дидактики»]]


----
----


[[Category:РУП]]
[[Category:РУП]]

Текущая версия на 19:15, 18 декабря 2023

Категория:ПБД221м
Alg video01.png| Alg video 05 Json PlantUML.png



Планируемые результаты обучения (Знать, Уметь, Владеть) Цель
  • теоретические знания и практический опыт в области основ алгоритмизации задач, классификации языков программирования, типов данных, структур данных, взаимосвязь алгоритмов и структур данных, особенностей реализации алгоритмов и типов данных в языках блочного программирования Scratch, Snap!, GP
Знать
Основные понятия, связанные с миром алгоритмов и структур данных
основы алгоритмизации задач, структуры данных;
типы данных, структуры данных;
методы и алгоритмы поиска и сортировки данных;
Уметь
  • обращаться к внешним и внутренним данным из среды Semantic MediaWiki, уметь использовать различные типы данных внутри Semantic MediaWiki
  • обмениваться проектами и блоками программ в Snap!
  • сравнивать и объединять статьи о языках программирования
  • импортировать и экспортировать данные в среду визуального программирования Snap!
  • проектировать и программировать линейные и разветвляющиеся структуры алгоритмов;
  • планировать процесс реализации алгоритма при помощи псевдокода и диаграмм
  • использовать язык dgl , mermaid, PlantUML встраивать диаграммы алгоритмов в вики страницы
  • представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
  • создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
  • оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
  • использовать рекурсию в командах и процедурах, использовать рекурсию при создании собственных функций
  • использовать объекты первого класса и лямбда исчисления.
Содержание разделов курса Содержание
1. Введение в алгоритмы и структуры данных
  • Определение алгоритма и структуры данных
2. Основные алгоритмы
  • Линейный поиск
  • Бинарный поиск
  • Сортировка (вставками, выбором, слиянием, быстрая сортировка)
  • Рекурсия и рекурсивные алгоритмы
3. Структуры данных
  • Массивы и связные списки
  • Стеки и очереди
  • Деревья (бинарные, сбалансированные, двоичные деревья поиска)
  • Графы (ориентированные и неориентированные, поиск в глубину и ширину)
Видео запись
Среды и средства, которые поддерживают учебный курс Snap!, R, RStudio, Lua, Python
Книги, на которых основывается учебный курс Стили и методы программирования, Computer Science with Snap! by Examples, Initiation to Algorithmics with Scratch
Учебная группа, работающая с курсом Алгоритмы и структуры данных данных в в 2023 году - ПБД221м
  • Учебная группа, работающая с курсом Алгоритмы и структуры данных данных в в 2022 году - ПБД211М
Особенность курса - Active Essay смотрим и тестируем на поле
when [up arrow v] key pressed
point in direction (0)
move (10) steps
when [down arrow v] key pressed
point in direction (180)
move (10) steps
when [right arrow v] key pressed
point in direction (90)
move (10) steps
when [left arrow v] key pressed
point in direction (-90)
move (10) steps
И смотрим на то, как они выполняются
или в Snap!

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

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

Цель
теоретические знания и практический опыт в области основ алгоритмизации задач, классификации языков программирования, типов данных, структур данных, взаимосвязь алгоритмов и структур данных, особенностей реализации алгоритмов и типов данных в языках блочного программирования Scratch, Snap!, GP
Знать
  1. Основные понятия, связанные с миром алгоритмов и структур данных См. Категория:Понятие
  2. основы алгоритмизации задач, структуры данных;
  3. типы данных, структуры данных;
  4. методы и алгоритмы поиска и сортировки данных;
Уметь
  1. обращаться к внешним и внутренним данным из среды Semantic MediaWiki, уметь использовать различные типы данных внутри Semantic MediaWiki см. Категория:Dataset
  2. обмениваться проектами и блоками программ в Snap!
  3. сравнивать и объединять статьи о языках программирования Taxonomic_sandbox
  4. импортировать и экспортировать данные в среду визуального программирования Snap!
  5. проектировать и программировать линейные и разветвляющиеся структуры алгоритмов;
  6. планировать процесс реализации алгоритма при помощи псевдокода и диаграмм - Категория:Diagrams
  7. использовать язык graphviz, mermaid, PlantUML встраивать диаграммы алгоритмов в вики страницы см. Graphviz + Категория:Diagrams -
  8. представлять алгоритмы на страницах вики в виде диаграмм, псевдокода, кода на различных языках программирования
  9. создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных))
  10. оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов
  11. использовать рекурсию в командах и процедурах, использовать рекурсию при создании собственных функций
  12. использовать объекты первого класса и лямбда исчисления

Содержание разделов дисциплины:

Введение. Основные понятия. Пространство для совместной деятельности

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

История языков программирования и обучающих языков

Современные алгоритмические языки. Вычислительное мышление и вычислительное участие.

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

  1. проектировать и программировать линейные и разветвляющиеся структуры алгоритмов;
  2. планировать процесс реализации алгоритма при помощи псевдокода и диаграмм - Категория:Diagrams - например, Binary search (diagram)
  3. использовать язык dgl и mermaid встраивать диаграммы алгоритмов в вики страницы см. Graphviz

Diagrams_37be5e92fa212a080558fc26c16ac9cb.png

Основные характеристики изучаемого алгоритмического языка

Типы данных. Константы. Переменные. Выражения. Арифметические и логические выражения.

Snap data types2.png

Спрайты, данные, процедуры как объекты первого класса. Структуры данных. Импорт и экспорт данных. Список случайных чисел из %сколько от %min до %max Table sprite.png


Структуры данных

Collab dataset JSON.png

  • Массивы и связные списки
  • Стеки и очереди
  • Деревья (бинарные, сбалансированные, двоичные деревья поиска)
  • Графы (ориентированные и неориентированные, поиск в глубину и ширину)

Алгоритмы сортировки и поиска

Сравнение эффективности и вычислительной сложности алгоритмов

Рекурсия

Литература

Основная литература

  1. Стили и методы программирования,
  2. Computer Science with Snap! by Examples,
  3. Initiation to Algorithmics with Scratch

Дополнительная литература

https://snap.berkeley.edu/snap/help/SnapManual.pdf - Руководство по Snap!

Критерии оценки по дисциплине (2022 - 2023)

Образовательный результат Тема Задание Пример
Знает понятия мира алгоритмов и структур данных Введение. Основные понятия. Пространство для совместной деятельности Использовать различные типы данных внутри Semantic MediaWiki, включить внешние данные в состав статьи Категория понятий - Category:Понятие

В категории статей о датасетах Category:Dataset

Умеет сравнивать и объединять статьи о языках программирования История языков программирования и обучающих языков Редактировать, дополнять и объединять статьи о языках программирования Category:Язык программирования, Taxonomic_sandbox

Умеет проектировать и программировать линейные и разветвляющиеся структуры алгоритмов, планировать процесс реализации алгоритма при помощи псевдокода и диаграмм - Категория:Diagrams, использовать язык dgl и mermaid встраивать диаграммы алгоритмов в вики страницы см. Graphviz

Представление алгоритмов в виде диаграмм, псевдокода, кода на различных языках программирования Создать диаграмму алгоритма, представить реализацию алгоритма на языке высокого уровня Пример
Умеет создавать собственные блоки (команды и процедуры с входными параметрами) в среде Snap! (создавать функции с использованием различных типов данных)) Основные характеристики изучаемого алгоритмического языка Процедуры видоизменения данных в среде Snap! Примеры видоизменения данных в Snap!, Получить список значений
оценивать и сравнивать эффективность алгоритмов, вычислительную сложность алгоритмов Алгоритмы сортировки и поиска Сравнить эффективность выполнения процедур над данными Готовые датасеты из категории Category:Dataset. Сортировка вставками, Быстрая сортировка
использовать рекурсию в командах и процедурах, использовать рекурсию при создании собственных функций Рекурсия Создать собственные команды и процедуры, в которых используется рекурсия Рекурсия, Фрактал

Напоминание по работа в вики среде

Мастер-класс «Совместная работа со знаниями на поле цифровой дидактики»


Источник — http://digida.mgpu.ru/index.php?title=Алгоритмы_и_структуры_данных_(syllabus)&oldid=14692