Автор: Владимир Биллиг
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 27 студентам
Уровень:
Для всех
Длительность:
2:06:00
Студентов:
741
Выпускников:
32
Цель курса - научить алгоритмическому мышлению школьников и всех тех, кто осваивает основы программирования.
Практическая задача курса – это научить программированию в процедурах и функциях. Достижению этой цели способствует рассмотрение большого числа примеров. В курсе подробно обсуждаются вариации классических алгоритмов над числами – нахождение делителей числа, нахождение простых и совершенных чисел, алгоритм Эвклида, решето Эратосфена. Рассматриваются классические алгоритмы работы с массивами, начиная от задач вычисления суммы, максимального и минимального элемента массива при возможных ограничениях на элементы, до задач поиска и сортировки элементов массива.
Важная часть курса посвящена программированию игр. Рассматриваются игры, основанные на различных стратегиях поиска числа, или комбинации графических объектов, задуманной компьютером. Выпускная работа курса также связана с игрой - моделирование игрового автомата «Однорукий бандит».
Специальности: Программист
Предварительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Вычисление суммы, максимального и минимального элементов небольшого множества
Вычисление суммы, максимального и минимального элементов небольшого множества
На этом уроке рассматриваются простые, но крайне важные алгоритмы вычисления суммы и максимального (минимального) элемента небольшого множества переменных. Рассматриваются два алгоритма. Первый из них кажется естественным и учитывает тот факт, что множество элементов небольшое и его можно явно перечислить. Второй алгоритм, возможно, менее естественен, но зато он легко обобщается на произвольное число элементов рассматриваемого множества.
Рассмотрение ведется на примере простой задачи. Показано, как написать соответствующие процедуры для вычисления суммы и максимума, и как построить интерфейс, учитывающий специфику задачи.
Оглавление
-
Массивы
В этой лекции приводятся правила, сформулированные в шуточно-стихотворной форме, позволяющие запомнить детали алгоритмов вычисления суммы, произведения, минимального и максимального элементов некоторого множества чисел. Приводятся функции, позволяющие вычислять эти характеристики для небольшого множества из трех элементов.
В лекции дается определение понятия "массив" – одной из основных структур данных, используемых в программировании. Подробно обсуждается объявление массива и его создание. Работа с массивами демонстрируется на примере построения функций, вычисляющих такие характеристики, как сумма, произведение, минимальный и максимальный элементы массива.
Оглавление
-
Вычисление характеристик массива при дополнительных ограничениях на элементы
Вычисление характеристик массива при дополнительных ограничениях на элементы
В этом уроке обсуждается решение задачи, созданное школьником в ходе выполнения домашней работы. Решение правильное, содержит комментарии. Его недостаток в плохой структурированности решения, поскольку все оно помещено в программу main консольного проекта.
Оставшаяся часть урока посвящена разбору решения этой же задачи, основанного на функциях. Эта задача позволяет продемонстрировать особенности вычисления характеристик массива – суммы, произведения, максимального и минимального элементов, в условиях, когда при вычислении характеристик на элементы накладываются дополнительные ограничения.
Оглавление
-
Игра "Отгадай задуманное число"
Игра "Задумай число"
В этом уроке мы переходим от изучения полезных, но скучных тем, таких как нахождение максимума и минимума, к играм. Вначале все слушатели играют в игру "Задумай число" и становятся "магистрами этой игры". Затем идет подробный анализ проекта, реализующего эту игру.
Оглавление
-
Игра "Быки и коровы"
Игра "Быки и коровы"
На этом уроке продолжается рассмотрение предыдущей игры "Задумай число". Обсуждается алгоритм бинарного поиска, дающий оптимальную стратегию поиска задуманного числа. Приводится реализация этой стратегии. В интерфейсе игры появляется новая кнопка "Компьютер, отгадай число".
Рассматривается проект, реализующий новую игру "Быки и коровы", где также требуется отгадать число, задуманное компьютером. Найти задуманное число в этой игре сложнее, поскольку разрешается задавать вопрос только одного типа "Число равно N?"
По техническим причинам не состоялась запись следующей лекции, где рассматривалась вариация проекта "Быки и коровы", в которой задуманная комбинация случайным образом выбиралась из множества, включающего 12 картинок.
В тексте, сопровождающем данный урок, дается краткое описание этого проекта.
Оглавление
-
Арифметические операции, функции и выражения
Арифметические операции, функции и выражения
На этом уроке от игр мы возвращаемся в мир основ математики и программирования. Рассматриваются арифметические операции, функции и выражения. Дается определение понятия выражения и показано, как оно вычисляется. Объясняется, что вычислить выражение означает не только определения значения выражения, но и определение его типа. Решаются простые школьные задачи на ту тему.
Оглавление
-
Делители числа
Делители числа
На этом уроке рассматриваются разнообразные задачи, связанные с делителями числа. Показано, как построить функцию, определяющую является ли некоторое число d делителем числа N. На этой основе строятся функции, определяющие все пары делителей числа, нахождение всех простых делителей числа. Дается определение простых чисел, совершенных чисел. Обсуждается общий подход поиска некоторого множества элементов с определенными свойствами. Показано, что вначале строится более широкое множество кандидатов, а затем строится фильтр, отбирающий среди кандидатов тех, кто обладает нужными свойствами. По ходу урока дается доказательство некоторых утверждений.
Оглавление
-
Простые числа
Простые числа
На этом уроке обсуждается понятие простого числа, алгоритм, позволяющий определить, является ли число простым. Рассматривается интуитивно понятный алгоритм нахождения всех простых чисел в заданном диапазоне. Подробно обсуждается эффективный алгоритм поиска простых чисел "Решето Эратосфена", придуманный более двух тысяч лет тому назад выдающимся древнегреческим ученым Эратосфеном. Как обычно показан программный проект, реализующий алгоритмы, рассмотренные в лекции.
Оглавление
-
Алгоритм Эвклида
Алгоритм Эвклида
В начале урока дается задание на "выпускную работу", которая должна быть представлена через две недели на последнем занятии в этом учебном году.
Темой урока является алгоритм нахождения наибольшего общего делителя и наименьшего общего кратного двух целых чисел. Вначале рассматривается интуитивно понятный алгоритм, использующий ранее построенные функции нахождения делителей числа. Затем объясняется эффективный алгоритм нахождения НОД двух чисел, придуманный и обоснованный Эвклидом более двух тысяч лет тому назад. Этот алгоритм считается старейшим алгоритмом, отвечающим всем требованиям, которые предъявляются к описанию алгоритма, - строго обоснованным и точно сформулированным.
Оглавление
-
Возведение в степень
Возведение в степень
В начале урока обсуждается возможный интерфейс и некоторые детали реализации игры "Однорукий бандит", над которой школьники уже начали работать.
Затем обсуждается алгоритм возведения в степень. Как обычно, рассматриваются две версии – интуитивно понятный алгоритм и эффективный алгоритм.
В заключение рассматривается задача построения чисел – градин, которая еще называется проблемой "3n + 1". Решение задачи дается простой программой в несколько строчек. Но с этой программой связана еще не решенная проблема доказательства ее завершаемости. Все знают, что цикл while в этой программе завершается для любого n, но строгого доказательства этого утверждения пока не существует.
Оглавление
-