Основы программирования и баз данных
Модуль 1. Устройство компьютера 
История
Материнская плата
Центральный процессор
Оперативная память
Постоянная память
Графический процессор
Блок питания и охлаждения
Устройства ввода-вывода
Операционная система
Модуль 2. Введение в основы цифровой логики и устройства микросхем 
Микросхемы
История создания
Назначение
Логические элементы микросхем
Сумматор
Устройство оперативной памяти
Логическая организация оперативной памяти
Модуль 3. Основы вычислительной техники и программирования 
Базовая архитектура и структура ЭВМ. Принцип фон Неймана
Задача. Решение задачи
Основные этапы решения задач
Программа
Программа (продолжение)
Загрузка и выполнение программ
Критерии программирования
Методологии программирования (парадигмы)
Языки программирования (классификация)
Объектно-ориентированное программирование
Объектно-ориентированное программирование (продолжение)
Объектно-ориентированное программирование (продолжение)
Объектно-ориентированное программирование (продолжение)
Выбор языка программирования для проекта
Модуль 9. Лабораторные работы. «Основы программирования»  
Практика С
Практика Python
Практика запуска программ
Модуль 4. Представление информации в ЭВМ 
Числа в арифметике
Числа в арифметике (продолжение)
Системы счисления
Системы счисления (продолжение)
Представление чисел в ЭВМ
Диапазоны представления целых чисел
Единицы измерения ёмкости запоминающих устройств
Представление символьной информации (Кодовые таблицы)
Создание Переменных/Объектов
Понятие типа данных
Выражения. Операнды.
Идентификаторы. Литералы
Арифметические операции
Операции сравнения
Законы арифметики
Модуль 5. Алгебра логики и арифметика двоичных чисел  
Основы алгебры логики
Логические операции
Логические операции
Связи между системами счисления
Связи между системами счисления (продолжение)
Связи между системами счисления (продолжение)
Основы арифметики двоичных чисел
Модуль 6. Введение в искусственный интеллект: основы и возможности 
Искусственный интеллект
Классификация ИИ по методам обработки информации
Этапы развития ИИ
Применение ИИ в российских компаниях
Модуль 7. Основы алгоритмизации 
Алгоритм
Основные свойства алгоритма
Типовые структуры
Типовые структуры (продолжение)
Типовые структуры (продолжение)
Типовые структуры (продолжение)
Типовые структуры (продолжение)
Блок схема:
Онлайн редактор
Практика / ДЗ
Модуль 10. Лабораторная работа. «Работа с блок-схемами»  
Модуль 11. Лабораторная работа. «Управляющие структуры»  
Создание переменных/объектов 
Ввод-вывод данных 
Следование  
Практика 
Условный оператор 
Практика 
Циклы 
Практика 
Модуль 8.1 Структуры данных 
Определения 
Типы данных
Базовые структуры данных
Динамические структуры данных
Динамические структуры данных
Динамические структуры данных
Динамические структуры данных
Динамические структуры данных
Основные операции над структурами данных
Модуль 8.2 Теория баз данных 
Информационная система
История развития ИС
История развития ИС (продолжение)
Компоненты СУБД
Виды СУБД(по способу доступа к данным)
Проектирование Баз данных 1 этап
Проектирование Баз данных 2 этап
Иерархическая модель данных
Сетевая модель данных
Реляционная модель данных (предложена Эдгаром Коддом в 70 году)
Постреляционная модель данных
Многомерная модель данных
Объектно-ориентированная модель данных
Проектирование баз данных 3 этап
Основные подходы к хранению данных
Язык запросов SQL
Модуль 12. Лабораторная работа. «Проектирование баз данных»  
Модуль 13. Лабораторная работа. «Знакомство с SQL»  
1.83M
Категория: ИнформатикаИнформатика

37485_file

1. Основы программирования и баз данных

1

2.

О Преподавателе
Окончил и работал на кафедре РК-
5 МГТУ им. Н. Э. Баумана
разработчик
и
преподаватель
курсов по C/C++, Java, C#, R, Scala
выпустил
более 500 групп по
различным
продуктам
Oracle,
Microsoft и авторским курсам
25 лет преподает курсы по IT
технологиям
Александр Кораблин
Преподаватель УЦ Специалист
к.т.н., MCT, MCSD,
Oracle Certified Professional
2

3. Модуль 1. Устройство компьютера 

Модуль 1.
Устройство компьютера
История развития компьютера. Обзор эволюции компьютерной техники от
первых ЭВМ до современных компьютеров.
Материнская плата. Функции и компоненты материнской платы.
Центральный процессор (CPU). Основные функции и виды процессоров.
Оперативная память (RAM). Функции и типы оперативной памяти. Влияние
оперативной памяти на производительность ПК.
Постоянная память (ROM/HDD/SDD). Постоянная память и ее виды. Влияние
постоянной памяти на производительность ПК.
Графический процессор (GPU). Определение и функции GPU. Влияние GPU
на производительность.
Устройства ввода-вывода. Виды устройств. Интерфейсы подключения
периферийных устройств: USB, Bluetooth, HDMI.
Блок питания и охлаждение.
Сетевые компоненты (Ethernet, Wi-Fi).
Роль операционной системы в управлении аппаратной частью. BIOS/UEFI.
Практическая работа «Сборка ПК» https://www.regard.ru/configurator
3

4. История

Нулевое поколение. Механические вычислители – например,
счетная машина Блеза Паскаля, которую он сконструировал в 1642г.
Первое поколение. Компьютеры на электронных лампах (194х-1955).
Быстродействие: несколько десятков тысяч операций в секунду.
Второе поколение. Компьютеры на транзисторах (1955-1965).
Быстродействие: сотни тысяч операций в секунду.
Третье поколение. Компьютеры на интегральных схемах (1965-1980).
Быстродействие: миллионы операций в секунду.
Четвертое поколение. Компьютеры на больших (и сверхбольших)
интегральных схемах (1980-…). Быстродействие: сотни миллионов
операций в секунду. Эра персональных компьютеров.
Пятое поколение?
4

5. Материнская плата

Материнская плата — предназначенная для соединения и
обеспечения взаимодействия всех компонентов персонального
компьютера.
Сокет, в который устанавливается процессор.
Чипсет — микросхема, которая регулирует работу внутренних компонентов системного
блока.
Слоты для установки оперативной памяти.
PCI слоты для подключения видеокарты и других плат расширения.
SATA разъёмы для подключения жёстких дисков и SSD дисков.
Другие внутренние разъёмы и внешние порты для пользователя.
5

6. Центральный процессор

Процессор - интегральная схема, исполняющая машинные инструкции
(код программ).
Основные характеристики ЦП: частота, количество ядер, объем
кэша, техпроцесс:




Частота процессора показывает количество операций, выполняемых в единицу
времени.
Ядра позволяют выполнять код программ параллельно.
Кэш — это память внутри ЦП.
При производстве микросхем применяется специальное оборудование, которое имеет
определённую разрешающую способность (техпроцесс).
6

7. Оперативная память

ОЗУ — временная память, в которой хранятся данные во время
работы ЭВМ.
Основные характеристики: поколение DDR, объем, частота.
Сейчас актуален стандарт DDR5. Новые поколения приносят
более высокие частоты и меньшее энергопотребление.
7

8. Постоянная память

ROM — (read-only memory, постоянное запоминающее устройство) —
масочное ПЗУ, изготовляемое фабричным методом;
EEPROM (electrically erasable programmable read-only memory) — электрически
стираемое перепрограммируемое ПЗУ, память которого может стираться и
заполняться данными несколько десятков тысяч раз, используется в
твердотельных накопителях, одной из разновидностей EEPROM является флешпамять;
Жёсткий диск (HDD) — накопитель на жёстких магнитных дисках. Внутри
него установлена одна или несколько алюминиевых пластин. ЖД обычно
вращается со скоростью 5400/7200/10000 об/мин.
Твердотельный накопитель – немеханическое запоминающее устройство,
внутри которого нет движущихся деталей. В SSD дисках используется флешпамять, которая более дорогая, но значительно быстрее и полностью бесшумна
при работе. Твердотельные накопители даже преодолели порог скорости порта
SATA, поэтому появились NVMe модели, которые использует шину PCI Express,
как и видеокарты.
8

9. Графический процессор

GPU — это специализированный процессор, который работает
исключительно с графикой. Расшифровывается
как Graphics Processing Unit. Он обрабатывает данные, связанные с
отображением изображений, видео и 3D-графики.
Структура. CPU разработаны для выполнения широкого спектра задач
и имеют всего несколько ядер. Графические процессоры
предназначены для параллельной обработки данных и могут иметь
тысячи небольших ядер.
Оптимизация задач. CPU отлично справляются с быстрым
выполнением последовательных задач, что делает их идеальными для
вычислений общего назначения. GPU лучше справляются с
выполнением множества параллельных задач одновременно,
например, для рендеринга графики и вычислений.
9

10. Блок питания и охлаждения

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





мощность;
ток на линиях питания – обозначает объем энергии, которая способна передаваться по
каждой из них;
эффективность – отражает результативность БП в плане преобразования
электрической энергии;
входное напряжение;
количество и тип разъемов.
В системе ПК есть два основных варианта для безопасного отвода
тепла от процессора: воздушное и жидкостное охлаждение. Оба
варианта имеют свои преимущества, но выбор способа охлаждения
зависит от потребностей вашего ПК.
10

11. Устройства ввода-вывода

11

12. Операционная система

Операционная система (ОС) — это программное обеспечение:




Загрузка программ в оперативную память и их выполнение.
Управление аппаратными компонентами, такие как: процессор, память, устройства
ввода-вывода.
Предоставление интерфейса для работы с файловой системой.
Контроль доступа к ресурсам и данным, т.е. обеспечение безопасности.
BIOS - Basic Input-Output system, базовая система ввода-вывода. Это
программа низкого уровня, хранящаяся на чипе материнской платы вашего
компьютера. BIOS загружается при включении компьютера и отвечает за
пробуждение его аппаратных компонентов, убеждается в том, что они
правильно работают, а потом запускает программу-загрузчик, запускающую
операционную систему.
Начиная с 201x года новое аппаратное обеспечение ПК преимущественно
поставляется с прошивкой UEFI, вместо традиционного BIOS. UEFI – новое
решение, которое поддерживает жёсткие диски большего объёма, быстрее
загружается, более безопасно и обладает графическим интерфейсом,
поддерживающим мышь.
12

13. Модуль 2. Введение в основы цифровой логики и устройства микросхем 

Модуль 2.
Введение в основы цифровой логики и
устройства микросхем
Определение микросхемы:
– Введение в микросхемы. История создания и развития микросхем.
– Основные функции и типы микросхем.
Логические элементы:


Основные логические элементы (AND, OR, NOT).
Составные логические элементы (NAND, NOR, XOR, XNOR).
Сумматор:



Определение сумматора.
Принцип работы неполного сумматора.
Принцип работы полного сумматора. Различия между полусумматором и полным
сумматором.
Структура памяти:


Ячейки памяти.
Распределение адресов.
13

14. Микросхемы

Микросхемы, они же интегральные схемы или микрочипы, –
это устройства, которые содержат в себе множество
транзисторов, диодов, резисторов и прочих элементов.
Микросхемы — кристалл особо чистого полупроводникового материала
(чаще всего кремния), В кристалле с помощью специальных методов
(диффузия, напыление, травление и др.) создаются транзисторы
(в современном микропроцессоре их многие миллионы), диоды,
резисторы, конденсаторы. К определённым точкам кристалла
присоединяются выводы микросхемы (иногда их несколько десятков),
которые припаиваются к печатной плате электронного устройства.
Интегральные схемы широко используются в компьютерах, контрольно-
измерительной аппаратуре, аппаратуре связи, бытовых радиоэлектронных
приборах. Устройства, основанные на твердотельных и цифровых технологиях,
успешно вытесняют традиционные устройства. Например, стали возможны часы,
фотоаппарат и «магнитофон» без движущихся частей, плоский телеэкран. меньшее
энергопотребление.
14

15. История создания

Микросхема была изобретена в 1959 году американскими инженерами
Д. Килби и Р. Нойсом, будущим основателем корпорации Intel. они
предложили компоновать отдельные электронные элементы на общем
основании, изготовленном из полупроводниковых материалов.
Развитие микроэлектроники началось с изготовления микросхем,
содержащих несколько десятков компонентов с минимальными
размерами 25 мкм, сегодня эта цифра в соответствии с законом Мура
составляет миллиарды компонентов размером порядка 22 нм.
Проблемы микроэлектроники:





уменьшение размеров элементов;
проблема внутренних соединений;
проблема теплоотвода;
проблема дефектов подложки;
проблема контроля параметров.
15

16. Назначение

Микросхема может обладать законченной, сколь угодно
сложной, функциональностью — вплоть до
целого микрокомпьютера (однокристальный микрокомпьютер).
Аналоговые (входной сигнал – непрерывная функция):
стабилизаторы, датчики, преобразователи сигналов. Применяются в
аппаратуре звукоусиления и звуковоспроизведения,
в видеомагнитофонах, телевизорах, технике связи, измерительных
приборах и т.д.
Цифровые (сигнал – дискретная функция): микроконтроллеры,
шифраторы/дешифраторы, модули памяти, процессоры, сумматоры,
ПЛИС - программируемые логические интегральные схемы и т.д.
Аналого-цифровые – для преобразования сигналов.
16

17. Логические элементы микросхем

Вход 1
Вход 2
AND
NAND
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
AND
NAND
Вход 1
Вход 2
OR
XOR
NOR
0
0
0
0
1
0
1
1
1
0
1
0
1
1
0
1
1
1
0
0
OR
NOR
XOR
17

18. Сумматор

Сумматор — логический операционный узел, выполняющий
арифметическое сложение двоичных чисел.
Схема полусумматора:
1
1
0
XOR
1
AND
18

19. Устройство оперативной памяти

Память компьютера построена из двоичных запоминающих элементов —
битов, объединенных в группы по 8 битов, которые
называются байтами. (Единицы измерения памяти совпадают с
единицами измерения информации). Все байты пронумерованы. Номер
байта называется его адресом.
Обычно ОЗУ исполняется из интегральных микросхем памяти
SDRAM (синхронное динамическое ОЗУ). Каждый информационный бит
в SDRAM запоминается в виде электрического заряда крохотного
конденсатора, образованного в структуре полупроводникового
кристалла. Из-за токов утечки такие конденсаторы быстро разряжаются,
и их периодически (примерно каждые 2 миллисекунды) подзаряжают
специальные устройства. Этот процесс называется регенерацией
памяти (Refresh Memory).
19

20. Логическая организация оперативной памяти

20

21. Модуль 3. Основы вычислительной техники и программирования 

Модуль 3.
Основы вычислительной техники и
программирования
Архитектура ЭВМ. Принцип Фон Неймана.
Задача. Виды задач. Основные этапы решения задач (постановка
задачи, математическое моделирование, алгоритмизация,
кодирование, отладка, тестирование).
Программа. Программирование. Критерии программирования. Код.
Языки программирования (классификация). Методологии
программирования.
Выбор языков программирования для решения различных задач:
критерии и рекомендации.
Компиляция/интерпретация.
21

22. Базовая архитектура и структура ЭВМ. Принцип фон Неймана

Машина фон Неймана — вычислительная система, построенная на
следующих принципах.
• Основными ее блоками являются:
• арифметико-логическое устройство,
• устройство управления,
• запоминающее устройство,
• устройства ввода-вывода.
• Программы и данные хранятся в одной и той же памяти.
• Используется двоичная система.
• Устройство управления и арифметико-логическое устройство,
объединенные в центральный процессор, определяют действия,
подлежащие выполнению, путем считывания команд из оперативной
памяти.
Подавляющее большинство вычислительных машин в настоящее время
являются фон-неймановскими машинами.
22

23. Задача. Решение задачи

Задача
– Поставленная цель, которую стремятся достигнуть.
– Вопрос, требующий решения на основании определённых знаний и
размышления
Решение задачи (проблемы)
– Процесс решения имеет место, когда ЛПР - лицо, принимающее
решение (организм или система искусственного интеллекта), не знает,
как перейти из данного состояния в желаемое целевое состояние.
Материал из Википедии — свободной энциклопедии
В области вычислительной техники и программирования:
– Задача - это преобразование информации (исходных данных в
результирующие данные)
– Обычно решение задачи представляется в виде алгоритма
23

24. Основные этапы решения задач

Постановка задачи
Математическое моделирование
Алгоритмизация
Кодирование
Отладка
Тестирование
24

25. Программа

Компьютерная программа — последовательность или набор команд,
написанных на языке программирования для выполнения на электронновычислительной машине (ЭВМ);
Язык программирования – определяет набор лексических(словарный
состав), синтаксических(способы комбинирования) и семантических
(формальные математические модели) правил для написания компьютерных
программ.
Материал из Википедии — свободной энциклопедии
25

26. Программа (продолжение)

Запись программы при помощи языка программирования удобна для
понимания и редактирования человеком-программистом
Для выполнения на компьютере программу необходимо транслировать перевести в машинный код.
Существует два метода трансляции:
– компиляция
• готовая программа вначале переводится в исполняемый машинный код
специальной программой - компилятором
• затем машинный код может многократно выполняться процессором
– Заметим, что машинный (двоичный) код непереносим между различными
аппаратными и программными платформами.
– интерпретация.
• программа переводится в инструкции машинного кода инструкция за
инструкцией
• каждая инструкция сразу выполняется специальной средой исполнения интерпретатором.
– Это позволяет добиться переносимости программ между различными аппаратными и
программными платформами.
26

27. Загрузка и выполнение программ

https://en.wikipedia.org/wiki/Computer_program
27

28. Критерии программирования

Внешние факторы, которые в том числе описаны в
стандарте ИСО 9126:









корректность
устойчивость
расширяемость
повторное использование
совместимость, эффективность
переносимость
простота использования
функциональность
своевременность.
Внутренние факторы:



читаемость
модульность
легкость обнаружения ошибок.
28

29. Методологии программирования (парадигмы)

Методология программирования — это совокупность идей, понятий,
принципов, способов и средств, определяющая стиль написания,
отладки и сопровождения программ:
1.
2.
3.
4.
5.
6.
императивное(процедурное) программирование
декларативное программирование
объектно-ориентированное программирование
функциональное программирование
логическое программирование
программирование в ограничениях
29

30. Языки программирования (классификация)

По уровню абстракции:
Низкого уровня – это машинный код и языки ассемблера.
Многие сейчас считают C и C++ языками низкого уровня;
Высокого уровня – это Java, Python, C# и т.д.
По парадигме программирования
По модели исполнения (компилируемые, интерпретируемые)
30

31.

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








Fortran
Cobol
Basic
Pascal
C
Modula-2
Ada
Perl
Любая программа состоит из трёх
базовых управляющих конструкций:
- последовательность,
- ветвление,
- цикл
- используются подпрограммы.
31

32. Объектно-ориентированное программирование

Объектно-ориентированное программирование (ООП) —
парадигма программирования, основанная на представлении предметной
области в виде системы взаимосвязанных абстрактных объектов и их
реализаций.
Основной проблемой процедурного программирования является то, что данные и
функции их обработки не были связаны.
С появлением ООП появилась новая структура данных — класс.
Это тип данных, внешне похожий на структуру (в языке С) или запись (в
Pascal), в котором кроме данных (свойств) также содержатся функции их
обработки (методы).
Материал из Википедии — свободной энциклопедии
32

33. Объектно-ориентированное программирование (продолжение)

Базовые понятия в ООП:
– Класс представляет собой тип данных, имеющий в составе:
• Свойства - атрибуты объекта (параметры его состояния)
• Методы - действия, которые можно выполнять над объектом или
которые сам объект может выполнять.
– Каждый объект является экземпляром некоторого класса объектов.
– Один класс отличается от других именем и, обычно, набором
поддерживаемых интерфейсов (доступных методов).
– Интерфейсы, в свою очередь, представляют собою набор сообщений,
которые можно посылать объекту.
Материал из Википедии — свободной энциклопедии
33

34. Объектно-ориентированное программирование (продолжение)

Базовые принципы
– Абстракция данных
• Объекты представляют собою модели реальных
сущностей из предметной области.
– Работать с ними намного удобнее, чем с низкоуровневым
описанием всех возможных свойств и реакций объекта.
– Инкапсуляция
• Любой класс должен рассматриваться как чёрный ящик.
– Пользователь класса должен видеть и использовать только
интерфейс (от английского interface — внешнее лицо, т. е.
список декларируемых свойств и методов) класса и может не
вникать в его внутреннюю реализацию.
Материал из Википедии — свободной энциклопедии
34

35. Объектно-ориентированное программирование (продолжение)

Базовые принципы
– Наследование
• Порождение одного класса от другого с сохранением всех
свойств и методов класса-предка и добавлением, при
необходимости, новых свойств и методов.
– Наследование призвано отобразить такое свойство реального
мира, как иерархичность.
– Полиморфизм
• Классы-потомки могут изменять реализацию
унаследованных методов класса-предка, сохраняя
неизменным его интерфейс.
– Это позволяет обрабатывать объекты классов-потомков как
однотипные объекты, не смотря на то, что реализация методов
у них может различаться.
Материал из Википедии — свободной энциклопедии
35

36.

Список наиболее известных объектноориентированных языков программирования








Smalltalk
C++
Object Pascal (Delphi)
Java
C#
Python
PHP
VB.NET
36

37. Выбор языка программирования для проекта

Цели проекта и требования
Опыт команды
Экосистема и инструменты
Сообщество и поддержка
Производительность
Безопасность
Масштабируемость
Кроссплатформенность
37

38. Модуль 9. Лабораторные работы. «Основы программирования»  

Модуль 9.
Лабораторные работы. «Основы
программирования»
Установка и настройка сред программирования.
Работа с компилятором:


Этапы: препроцессор, компиляция, компоновка (запуск процессов через терминал
среды, знакомство с выходными файлами).
Изменение программы, и анализ .exe файла.
Работа с интерпретатором.
Анализ различия работы с компиляционным и интерпретационным
языками программирования.
Форматированный ввод/вывод.
Знакомство с отладкой.
38

39. Практика С

Установка DEV C++ 5.11:
– набираем в поисковике: Dev C++ 5.11
– переходим на https://sourceforge.net/
– скачиваем программу
– при установке следуем инструкции преподавателя.
C/C++ online:
– набираем в поисковике: C compiler online
– переходим на https://www.onlinegdb.com/online_c_compiler
– F9 для выполнения кода
39

40. Практика Python

Установка интерпретатора Python:
– набираем в поисковике: python download
– переходим на https://www.python.org/downloads/
– выбираем ОС и скачиваем программу
– при установке следуем инструкции преподавателя.
Python online:
– набираем в поисковике: python online
– переходим на https://www.onlinegdb.com/online_python_compiler
– F9 для выполнения кода
40

41. Практика запуска программ

Создание и запуск скомпилированной программы:
– запуск DEV C++
– создание проекта
– компиляция
– запуск программы из среды и из командной строки.
Создание и запуск интерпретируемой программы:
– работа в командной строке
– создание файла с расширением .py
– запуск программы
Ввод-вывод:
41

42. Модуль 4. Представление информации в ЭВМ 

Модуль 4.
Представление информации в ЭВМ
Представление чисел






Единицы измерения (бит, байт, КБ, и т.д.);
Представление целых чисел в ЭВМ (прямой, обратный, дополнительный код);
Нормализованная запись числа;
Представление вещественных чисел в ЭВМ;
Диапазоны преставления целых и вещественных чисел в памяти ЭВМ.
Представление символьной информации (ASCII, Unicode);
Преобразование документа из одной кодировки в другую.
Понятие переменной/объекта и их имена.
Понятия: Выражение, операнд, оператор



Виды операторов (арифметические операторы, присваивания, сравнения,
логические);
Законы арифметики (коммутативности, ассоциативности, дистрибутивности);
Приоритетность операторов.
42

43. Числа в арифметике

Число — это абстрактная сущность, используемая для описания количества.
Арифметика — элементарный раздел математики, изучающий простейшие
виды чисел (натуральные, целые, рациональные) и простейшие
арифметические операции над ними (сложение, вычитание, умножение,
деление).
Числа:
– Натуральные числа 1,2,... используются для счёта объектов.
Множество натуральных чисел обозначается N.
– Целые. Если к натуральным числам добавить ещё отрицательные
числа и ноль, мы получим множество целых чисел Z. Целые числа в
математике изучаются в рамках теории чисел.
• В элементарной теории чисел изучаются такие вопросы, как:
– делимость целых чисел,
– алгоритм Евклида вычисления наибольшего общего делителя,

разложение числа на простые множители,
– совершенные числа
– и др.
Материал из Википедии — свободной энциклопедии
43

44. Числа в арифметике (продолжение)

– Отношения целых чисел называются рациональными числами, или
обыкновенными дробями. Множество всех рациональных чисел
обозначается Q.
– Следующие обобщения лежат уже за пределами арифметики:
• Вещественные. Если к рациональным числам добавить все
бесконечные и непериодические десятичные дроби, называемые
иррациональными числами, мы получим вещественные числа R.
• Комплексные. Действительные числа, в свою очередь, путем
добавления квадратного корня из -1 могут быть расширены до
комплексных чисел C.
Материал из Википедии — свободной энциклопедии
В программировании встречаются все (или почти все) перечисленные виды
чисел, в языках программирования они представляются различными
типами данных.
44

45. Системы счисления

Система счисления — способ записи чисел с помощью
набора специальных знаков, называемых цифрами.
Системы счисления подразделяются на
– позиционные
(например, десятичная)
– непозиционные (например, римская)
В позиционных системах счисления величина, обозначаемая
цифрой в записи числа, зависит от её положения в числе
(позиции).
Количество используемых цифр называется основанием
системы счисления
Материал из Википедии — свободной энциклопедии
45

46. Системы счисления (продолжение)

1) десятичная
103 102 101 100
1
1
0
9
Значение
1*103 +1*102 +0*101 +9*100 = 1109(10)
2) двоичная
23 22 2 1 20
1
1
0
Значение
1*23 +1*22 +0*21 +1*20 = 13(10)
1
3) восьмеричная
83
82 81 80
1
1
0
Значение
1*83 +1*82 +0*81 +7*80 = 583(10)
7
4) шестнадцатеричная
163 162 161 160
1
1
0
F
Значение
1*163 +1*162 +0*161 +15*160 = 4367(10)
46

47. Представление чисел в ЭВМ

Целые числа:
– прямой код;
– обратный код;
– дополнительный код.
Вещественные числа:
– нормализованная запись числа:
a = ± m * рq
2000 = 0,2*104
– binary format
– decimal format: где каждая тройка чисел кодируется как
целое число с использованием 10 битов.
47

48. Диапазоны представления целых чисел

Кол-во бит
Запись с порядком
Обычная запись
8
-27 .. 27-1
-128 .. 127
16
-215 .. 215-1
-32768 .. 32767
32
-231 .. 231-1
-2147483648 ..
2147483647
int()
unlimited precision
unlimited precision
48

49. Единицы измерения ёмкости запоминающих устройств

1 бит
= двоичная цифра /логическое значение
8 бит
= 1 байт - символ (ASCII)
1 Кбайт = 210 байт
1 Мбайт = 220 байт
1 Гбайт = 230 байт
1 Тбайт = 240 байт
1 Пбайт = 250 байт
ГОСТ 8.417-2002
49

50. Представление символьной информации (Кодовые таблицы)

0 1 2 3 4 5 6 7 8 9 A B C D E F
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
0│ │►│ │0│@│P│`│p│А│Р│а│░│└│╨│р│Ё│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
1│☺│◄│!│1│A│Q│a│q│Б│С│б│▒│┴│╤│с│ё│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
2│☻│↕│"│2│B│R│b│r│В│Т│в│▓│┬│╥│т│Є│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
3│♥│‼│#│3│C│S│c│s│Г│У│г│││├│╙│у│є│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
4│♦│¶│$│4│D│T│d│t│Д│Ф│д│┤│─│╘│ф│Ї│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
5│♣│§│%│5│E│U│e│u│Е│Х│е│╡│┼│╒│х│ї│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
6│♠│▬│&│6│F│V│f│v│Ж│Ц│ж│╢│╞│╓│ц│Ў│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
7│ │↨│'│7│G│W│g│w│З│Ч│з│╖│╟│╫│ч│ў│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
8│ │↑│(│8│H│X│h│x│И│Ш│и│╕│╚│╪│ш│°│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
9│ │↓│)│9│I│Y│i│y│Й│Щ│й│╣│╔│┘│щ│∙│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
A│ │→│*│:│J│Z│j│z│К│Ъ│к│║│╩│┌│ъ│·│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
B│♂│←│+│;│K│[│k│{│Л│Ы│л│╗│╦│█│ы│√│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
C│♀│∟│,│<│L│\│l│|│М│Ь│м│╝│╠│▄│ь│№│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
D│ │↔│-│=│M│]│m│}│Н│Э│н│╜│═│▌│э│¤│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
E│♫│▲│.│>│N│^│n│~│О│Ю│о│╛│╬│▐│ю│■│
├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
F│☼│▼│/│?│O│_│o│⌂│П│Я│п│┐│╧│▀│я│ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
Однобайтные таблицы
(ASCII, ANSI, KOI-8R)
– для представления символов
используются 8-битные
числовые коды
– кодовая таблица позволяет
закодировать 256 различных
символов
Двухбайтная таблица (UNICODE)
– для представления символов
используются 16-битные
числовые коды
– кодовая таблица позволяет
закодировать 65536 различных
символов
50

51. Создание Переменных/Объектов

Что? Где? Зачем?
Синтаксис:
тип
данных
имя
=
значение
Примеры:
int a = 4
double b
double c = 1.57
51

52. Понятие типа данных

В различных языках программирования реализованы те или
иные из перечисленных ниже типов:
простые (скалярные) типы:







логический
символьный
целый
с плавающей точкой
строковый
перечислимый
ссылочный (указатель)
составные (структурные) типы:




массивы
записи (структуры)
множества
списки
другие типы, определяемые программистом
52

53. Выражения. Операнды.

Выражение - математическая формула или иная символическая запись,
содержащая информацию о способе вычисления искомого значения.
Синтаксически выражение строится из операндов и операторов (знаков
операций).
Операнд в языках программирования ― аргумент операции, т.е. значение,
участвующее в вычислении.
– В зависимости от положения операнда относительно знака операции
операции подразделяются на:
• префиксные, например, -x,
• инфиксные,
например, a + b,
• постфиксные, например, x3.
– В зависимости от числа операндов операции подразделяются на:
• одноместные (унарные),
• двуместные (бинарные),
• многоместные операции.
53

54. Идентификаторы. Литералы

В качестве операндов в выражениях используются идентификаторы,
константы и другие выражения (возможно, заключенные в скобки)
Идентификатор (символическое имя)
– это лексема (последовательность допустимых символов языка
программирования, имеющая в нем смысл)
– используется для именование программных сущностей (переменных,
массивов, функций и др.)
– делает возможным ссылки на них в тексте программы
Литералы/Константа (постоянная величина) — некоторая величина, не
изменяющая своего значения в рамках рассматриваемого процесса.
– Численные литералы (например, 0, -1 или 3.14159) всегда являются
константами.
Вычисление выражений выполняется в соответствии с приоритетами и
ассоциативностью операторов (операций)
54

55. Арифметические операции

Операция присваивания
Идентификатор = выражение
Арифметические операции
Изменение знака
Умножение
Деление
Остаток от деления
Сложение
Вычитание
*
/
%
+
55

56. Операции сравнения

Равно
Не равно
Меньше
Меньше или равно
Больше
Больше или равно
Результат всех операций сравнения:
==
!=
<
<=
>
>=
True / False
56

57. Законы арифметики

коммутативность

Коммутативная операция (лат. commutativus — «меняющийся») — это бинарная
операция, обладающая переместительностью: для любых элементов a и b
a+b=b+a
a* b=b*a
ассоциативность

Ассоциативная операция (лат. associatio — соединение) — это бинарная
операция, обладающая сочетательностью: для любых элементов a, b и c
(a + b) + c = a + (b + c)
(a * b) * c = a * (b * c)

Для ассоциативной операции результат вычисления не зависит от порядка
вычисления (расстановки скобок), и потому скобки позволяется опускать
дистрибутивность

Дистрибутивность (лат. distributivus — «распределительный») — свойство
согласованности двух бинарных операций: для любых элементов a, b и c
a * (b + c) = a * b + a * c — дистрибутивность слева;
(b + c) * a = b * a + c * a — дистрибутивность справа.

Если операция * является коммутативной, как это имеет место для операции
умножения, то свойства дистрибутивности слева и справа совпадают.
Материал из Википедии — свободной энциклопедии
57

58. Модуль 5. Алгебра логики и арифметика двоичных чисел  

Модуль 5.
Алгебра логики и арифметика
двоичных чисел
Основы алгебры логики.
Основные операции (конъюнкция, дизъюнкция,
эквиваленция, импликация, инверсия).
Таблицы истинности.
Практическая работа 1 «Решение логических задач»
Системы счисления (dec, hex, oct, bin).
– Перевод из систем в системы.
– Арифметика двоичных чисел.
Практическая работа 2. «Преобразование систем
счисления».
Практическая работа 3. «Арифметика двоичных чисел».
58

59. Основы алгебры логики

Высказывание может быть истинным или ложным.
Высказывание обозначается одной буквой: А, В, С.
А
1
0
Логическое выражение может включать несколько
высказываний и операции с ними, например:
f = AB + C
Вопрос. Сколько всего возможных наборов высказываний в
лог. выражении f?
Таблица истинности = все наборы высказываний и
результирующее значение функции f. Её размер = 2n.
59

60. Логические операции

Логическое отрицание (инверсия)
Логическое умножение(конъюнкция)
Логическое сложение (дизъюнкция)
not
and
or
A
B
not A
A and B
A or B
0
0
1
0
0
1
0
0
0
1
0
1
0
1
1
1
1
1
60

61. Логические операции

Эквивалентность
Исключающее "или"
Логическое следование (импликация)
A
B
A xor B
xor
A
B
A
B
0
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
1
61

62. Связи между системами счисления

Перевод из десятичной в произвольную позиционную
систему счисления:
Для перевода необходимо делить с остатком искомое число на
основание системы счисления до тех пор, пока частное больше
нуля, и записать цифры всех остатков в обратном порядке.
Пример:
• 4410 переведём в двоичную систему:
• 44 делим на 2. частное 22, остаток 0
• 22 делим на 2. частное 11, остаток 0
• 11 делим на 2. частное 5, остаток 1
• 5 делим на 2. частное 2, остаток 1
• 2 делим на 2. частное 1, остаток 0
• 1 делим на 2. частное 0, остаток 1
Теперь, записав цифры всех остатков в обратном порядке, получим
число 1011002
62

63. Связи между системами счисления (продолжение)

Перевод из двоичной в восьмеричную и
шестнадцатеричную системы
Для этого типа операций существует
упрощенный алгоритм.
Для восьмеричной — разбиваем число на
триады, преобразуем триады по таблице
Для шестнадцатеричной — разбиваем число
на тетрады, преобразуем тетрады по таблице
Пример:
– преобразуем 1011002
– восьмеричная
— 101 100 → 548
– шестнадцатеричная — 0010 1100 → 2C16
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
63

64. Связи между системами счисления (продолжение)

Перевод из восьмеричной и
шестнадцатеричной систем в
двоичную
Для этого типа операций тоже существует
упрощенный алгоритм.
Для восьмеричной — преобразуем цифры
числа по таблице в триады
Для шестнадцатеричной — преобразуем
цифры числа по таблице в тетрады
Пример:
– преобразуем
– 548 → 101 100
– 2C16 → 0010 1100
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
64

65. Основы арифметики двоичных чисел

Поразрядное сложение с переносом
0 1 1 1
=?
0 1 1 1
= 7
0 1 1 0
=?
0 1 1 0
= 6
? ? ? ?
=?
1 1 0 1
=13
Сдвиг влево
0 0 1 1
=?
0 0 1 1
= 3
0 1 1 0
=?
0 1 1 0
= 6
1 1 0 0
=?
1 1 0 0
=12
Сдвиг вправо
1 1 0 1
=?
1 1 0 1 = 13
0 1 1 0
=?
0 1 1 0
= 6
0 0 1 1
=?
0 0 1 1
= 3
23 22 21 20 Значение(10)
0 0 0 0
0
0 0 0 1
1
0 0 1 0
2
0 0 1 1
3
0 1 0 0
4
0 1 0 1
5
0 1 1 0
6
0 1 1 1
7
1 0 0 0
8
1 0 0 1
9
1 0 1 0
10
1 0 1 1
11
1 1 0 0
12
1 1 0 1
13
1 1 1 0
14
1 1 1 1
15
65

66. Модуль 6. Введение в искусственный интеллект: основы и возможности 

Модуль 6.
Введение в искусственный интеллект:
основы и возможности
Искусственный интеллект. История развития ИИ. Различие
между ИИ, машинным обучением и нейросетью.
Виды искусственного интеллекта.
Задачи, решаемые искусственным интеллектом (обработка
естественного языка, компьютерное зрение).
Возможности и применение ИИ.
66

67. Искусственный интеллект

Искусственный интеллект (artificial intelligence): Комплекс
технологических решений, позволяющий имитировать когнитивные
функции человека (включая самообучение, поиск решений без
заранее заданного алгоритма и достижение инсайта) и получать
при выполнении конкретных практически значимых задач
обработки данных результаты, сопоставимые, как минимум, с
результатами интеллектуальной деятельности человека.
Компьютерное зрение (compter vision): Способность
функционального блока получать, обрабатывать и
интерпретировать визуальные данные.
ГОСТ Р 59277—2020
67

68. Классификация ИИ по методам обработки информации




















Нейросети
Обучение на примере
Эволюционные и генетические алгоритмы
Муравьиные алгоритмы
Имунные вычисления
Глубокое обучение
Роевые вычисления
Метод Байеса
Уменьшение размерности
Природные вычисления
Мягкие вычисления
Кластеризация
Дерево решений
Регуляризация
Аналоговая обработка данных
Обработка фурье-образов
Регрессия
Решение обратных задач
ГОСТ Р 59277—2020
Система правил
68

69. Этапы развития ИИ

Системы с обратной связью (вчера).
Narrow AI - узкий или слабый ИИ (сегодня). Они решают одну
определенную задачу…
Wide AI. Главная задача таких систем — преодолеть узость
применимости (движемся к…)
Общий искусственный интеллект (AGI). AGI – это способность
системы решать любые задачи в сложных средах с
ограниченными ресурсами. Уровень ИИ сопоставим с
человеком (будущее).
Сильный ИИ …
69

70. Применение ИИ в российских компаниях

Компьютерное зрение:
– Классификация изображений
– Object detection или обнаружение объектов
Сегментация изображений.
Текстовые задачи.
Распознавание текста на картинке.
Работа с табличными данными.
Временные ряды.
Оптимизационные задачи.
Рекомендательные системы.
70

71. Модуль 7. Основы алгоритмизации 

Модуль 7.
Основы алгоритмизации
Алгоритм. Свойства алгоритмов.
Виды алгоритмов (линейный, разветвляющихся,
циклический).
Формы представления алгоритмов.
Практическая работа 4. «Анализ блок схем».
Практическая работа 5. «Составление блок схем в
редакторе».
71

72. Алгоритм

«Алгоритм — это всякая система вычислений, выполняемых по строго
определённым правилам, которая после какого-либо числа шагов заведомо
приводит к решению поставленной задачи.»
(А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный
процесс, идущий от варьируемых исходных данных к искомому результату.»
(А. Марков)
Алгоритм — это точный набор инструкций, описывающих порядок действий
некоторого исполнителя для достижения результата — решения некоторой
задачи.
Материал из Википедии — свободной энциклопедии
72

73. Основные свойства алгоритма

Детерминированность (определенность)
Предполагает получение однозначного результата вычислительного
процесса при заданных исходных данных. Благодаря этому свойству
процесс выполнения алгоритма носит механический характер;
Результативность
Указывает на наличие таких исходных данных, для которых реализуемый
по заданному алгоритму вычислительный процесс должен через конечное
число шагов остановиться и выдать искомый результат;
Конечность
Каждое из действий и весь алгоритм в целом обязательно завершаются;
Массовость
Это свойство предполагает, что алгоритм должен быть пригоден для
решения всех задач данного типа;
Дискретность
Означает расчлененность определяемого алгоритмом вычислительного
процесса на отдельные этапы, возможность выполнения которых
исполнителем(компьютером) не вызывает сомнений.
73

74. Типовые структуры

Следование (последовательность)
Инструкция 1
Инструкция 2
Инструкция N
74

75. Типовые структуры (продолжение)

Ветвление (выбор)
True (истина)
Обход
False (ложь)
Условие
False (ложь)
Условие
True (истина)
Ветвь 1
Ветвь 2
Ветвь
75

76. Типовые структуры (продолжение)

Циклы
а.
С предусловием
б. С постусловием
False (ложь)
Тело цикла
Условие
True (истина)
Условие
Тело цикла
True (истина)
False (ложь)
76

77. Типовые структуры (продолжение)

Предопределенный процесс (процедура, функция)
Имя процедуры
или функции
77

78. Типовые структуры (продолжение)

Типовые структуры могут вкладываться друг в друга
True (истина)
False (ложь)
Условие
Ветвь 1
Ветвь 2
78

79. Блок схема:

Формы представления алгоритмов
Блок схема:
Диаграмма Насси – Шнейдермана:
79

80. Онлайн редактор

набираем в поисковике:
онлайн редактор блок схем
переходим на
https://programforyou.ru/block-diagram-redactor
выбираем нужные элементы с панели инструментов …
80

81. Практика / ДЗ

Найти максимум:
– из двух чисел
– из трёх чисел.
Вычислить факториал:
– использовать цикл.
Поиск
– неупорядоченный набор данных
– упорядоченный набор данных.
81

82. Модуль 10. Лабораторная работа. «Работа с блок-схемами»  

Модуль 10.
Лабораторная работа.
«Работа с блок-схемами»
Составление псевдокода по блок-схемам.
Закрепление материала.
82

83. Модуль 11. Лабораторная работа. «Управляющие структуры»  

Модуль 11.
Лабораторная работа.
«Управляющие структуры»
Следование.
Условный оператор.
Циклы.
83

84. Создание переменных/объектов 

Создание переменных/объектов
Тип данных
С
Python
Целый
int a=7;
a=7
Вещественный
double z=1.5;
z=1.5
Строчный
-
s="word"
Логический
-
b=True
84

85. Ввод-вывод данных 

Ввод-вывод данных
С
Python
Ввод
-
name=input()
Вывод для int
printf("%d", a);
print(a, z, s, b)
Вывод для double
printf("%f", z);
85

86. Следование  

Следование
Найти сумму
С
Python
Создание
переменных
int a=7;
a=7
int b=5;
b=5
int sum=a + b;
sum=a + b
printf("%d", sum);
print(sum)
Печать результата
86

87. Практика 

Практика
Найти и распечатать площадь прямоугольника.
Найти и распечатать каждую цифру трехзначного
целого числа.
87

88. Условный оператор 

Условный оператор
С
if( a==5 ) {
printf("a==5");
...
}
else {
printf("a!=5");
...
}
Python
if a==5 :
print("a==5")
...
else :
print("a!=5")
...
88

89. Практика 

Практика
Найти максимальное значение из трёх чисел.
Результат распечатать.
Задать натуральное число в диапазоне [2-100] и
проверить является ли оно простым.
89

90. Циклы 

Циклы
С
int n=3;
while(n >= 1) {
printf("%d", n);
n = n -1;
}
printf("Пуск!");
Python
n=3
while n >= 1:
print(n)
n = n -1
print("Пуск!")
90

91. Практика 

Практика
Найти и распечатать факториал натурального
числа.
91

92. Модуль 8.1 Структуры данных 

Модуль 8.1
Структуры данных
Типы данных.
Базовые структуры данных.
Динамические структуры данных:





списки
очереди
стеки
деревья
графы.
Операции со структурами данных
92

93. Определения 

Определения
Структура данных (англ. data structure) — программная
единица, позволяющая хранить и обрабатывать (машиной)
однотипные и/или логически связанные данные.
Материал из Википедии — свободной энциклопедии
Данные (data): - предоставление информации в формальном
виде, пригодном для передачи, интерпретации или обработки
людьми или компьютерами.
Большие данные (big data): - обширные наборы данных, —
главным образом, по таким характеристикам данных, как объем,
разнообразие, скорость генерации и/или изменчивость, — которые
требуют использования технологии масштабирования для
эффективного хранения, обработки, управления и анализа.
ГОСТ Р 59277—2020
93

94. Типы данных

В различных языках программирования реализованы те или
иные из перечисленных ниже типов:
простые (скалярные) типы:







логический
символьный
целый
с плавающей точкой
строковый
перечислимый
ссылочный (указатель)
составные (структурные) типы:




массивы
записи (структуры)
множества
списки
другие типы, определяемые программистом
94

95. Базовые структуры данных

Запись, структура, класс.
Массив (индексный) — простая статическая структура данных,
предназначенная для хранения набора единиц данных, каждая из
которых идентифицируется индексом или набором индексов.
Индекс — обычно целое число, либо значение типа, приводимого к целому,
указывающее на конкретный элемент массива.
12 25 99 20 …
37
0
N-1
1
2
3

95

96.

Достоинства массивов
• легкость вычисления адреса элемента по его индексу (поскольку
элементы массива располагаются один за другим)
• одинаковое время доступа ко всем элементам
• малый размер элементов: они состоят только из
информационного поля
Недостатки массивов
• невозможность удаления или добавления элемента без
сдвига других массива
96

97. Динамические структуры данных

Стек (англ. stack = стопка) — структура хранения данных с
дисциплиной доступа к элементам LIFO (Last In — First Out,
«последним пришёл — первым вышел»).
– Операцию добавления элемента на вершину (top) стека называют push,
извлечения — pop.
pop
push
99
19
25
top
12
33
10
Стек широко используется в программировании и является
неотъемлемой частью архитектуры современных процессоров.
– Компиляторы языков программирования высокого уровня используют
стек для передачи параметров при вызове подпрограмм, процессоры —
для хранения адреса возврата из подпрограмм.
97

98. Динамические структуры данных

Очередь (англ. queue) — структура хранения данных с
дисциплиной доступа к элементам FIFO (First In — First Out,
"первый пришел - первый вышел").
– Добавление элемента возможно лишь в конец (tail) очереди, выборка только из начала (head) очереди, при этом выбранный элемент из
очереди удаляется.
– Операцию добавление элемента называют enqueue, выборки dequeue.
dequeue
10
enqueue
33
12
25
head
tail
– Очередь широко используется в программировании для синхронизации
процессов обработки (например, сообщений), моделирования систем
массового обслуживания и т.д.
98

99. Динамические структуры данных

Связанный список — динамическая структура хранения данных,
каждый элемент которой состоит из:
– информационного поля (содержит значение элемента)
– одного (односвязный) или двух (двусвязный) указателей на соседние
элементы.
Список может быть сортированным или несортированным
Достоинства
– лёгкость добавления и удаления элементов
– размер списка ограничен только объемом доступной памяти
Недостатки
– сложно определить адрес элемента по его индексу (номеру) в списке
– на поле указателей расходуется дополнительная память (в массивах
указатели не нужны)
99

100. Динамические структуры данных

Двоичное дерево — абстрактная структура данных, являющееся
программной реализацией двоичного дерева (графа).
Дерево состоит из узлов (записей) вида
(data, l, r),

где data — некоторые данные привязанные к узлу,
– l, r — ссылки на узлы, являющиеся потомками данного узла.
Узел l называется левым потомком, а узел r — правым.
Материал из Википедии — свободной энциклопедии
100

101. Динамические структуры данных

Граф — математическая абстракция реальной системы любой
природы, объекты которой обладают парными связями. Граф как
математический объект есть совокупность двух множеств —
множества самих объектов, называемого множеством вершин, и
множества их парных связей, называемого множеством рёбер.
Материал из Википедии — свободной энциклопедии
101

102. Основные операции над структурами данных

Создать (пустую) структуру данных
Добавить новый элемент
Удалить заданный элемент
Проверить структуру на наличие в ней элементов
Найти элемент(ы) с заданными свойствами
Извлечь значение заданного элемента
Получить элемент, следующий (в некотором порядке ) за текущим
Перебрать (в некотором порядке) все элементы структуры данных
Сортировать (в некотором порядке) все элементы структуры данных
Удалить всю структуру данных
102

103. Модуль 8.2 Теория баз данных 

Модуль 8.2
Теория баз данных
Информационная система.
Требования к базам данных.
Этапы проектирования БД (концептуальное, даталогическое
проектирование).
Концептуальное: определение сущностей, связей, ограничений,
операций.
Даталогическое: описание таблиц, описание связей между
таблицами.
Иерархическая, сетевая, реляционная модель. Применение.
Преимущества и недостатки разных моделей.
Нормализация БД.
Понятие СУБД. Задачи решаемые СУБД.
Языки запросов.
103

104. Информационная система

История вычислительной техники связана с двумя областями:

численные расчёты – простые данные и сложные алгоритмы;

информационные системы – большие объёмы сложных данных
Информационная система — программно-аппаратный комплекс
для:
– хранение информации,
– предоставление пользовательского интерфейса,
– специфические для данного приложения вычисления и преобразование
информации.
Особые требования ИС:
– скорость работы;
– хранение больших объёмов данных.
104

105. История развития ИС

Первые реализации ИС – файловые системы.
Файловая система – набор прикладных программ для выполнения
операций с данными, например, создания отчёта. Каждая программа хранит
свои собственные данные и управляет ими.
Недостатки такого решения:
Дублирование данных;
Данные разделены по файлам и запросы, которые требуют обращения к
нескольким файлам – сложны;
Физическая структура и способ хранения данных жёстко зафиксированы в
коде приложения;
Несовместимость форматов файлов.
105

106. История развития ИС (продолжение)

Для повышения эффективности последующие реализации ИС –
использовали гибкую архитектуру, которая состоит из двух
независимых частей:
Корпоративная
База данных
СУБД
База данных – совместно используемый набор логически связанных
данных (и описание этих данных), предназначенный для
удовлетворения информационных потребностей организации;
СУБД – ПО, с помощью которого пользователи могут определять,
создавать и поддерживать базу данных, а также осуществлять к ней
контролируемый доступ.
106

107. Компоненты СУБД

Аппаратные:

Компьютеры

Внешние хранилища данных
Программное обеспечение:

ОС и ПО самой СУБД

Прикладные и сетевые программы
Данные и метаданные
Процедуры:

Регистрация в СУБД

Создание резервных копий, восстановление БД и т.п.

Инструкции и правила проектирования, использования и обслуживания БД
Пользователи:

Администраторы, разработчики, конечные пользователи.
107

108. Виды СУБД(по способу доступа к данным)

Клиент-серверные СУБД (MSQL Server, Oracle, Firebird, PostgreSQL, InterBase,
MySQL):

Данные хранятся и обрабатываются на сервере;

Доступ к данным есть только у этого сервера – это и есть СУБД;

Клиенты посылают запросы на обработку данных;

Прямого доступа к данным у клиентов нет.
Файл-серверные СУБД (Paradox, Microsoft Access, FoxPro, dBase):

Данные хранятся на выделенном компьютере;

Все приложения(клиенты) имеют общий доступ ко всем файлам БД;

Каждое приложение само обрабатывает данные;

Проблемы с производительностью, с поддержанием целостности, с блокировками.
Встраиваемые СУБД (SQLite, Firebird Embedded, MSQL Server Compact):

Поставляются в составе готового программного продукта, не требуя процедуры
самостоятельной установки;

Предназначены для локального хранения данных приложения и не рассчитаны на
коллективное использование в сети.
108

109. Проектирование Баз данных 1 этап

Концептуальное проектирование(инфологическая модель)
смысловое содержание базы данных, исходя из целей ее
использования. На этом этапе происходит идентификация объектов
предметной области, их характеристик и связей между объектами.
Есть готовые методологии:
ER-модель (Entity-Relationship model);
addr
id
Lname
name
Student
study
College
DFD (data flow diagrams) - методология графического структурного
анализа;
Manager
System
Customer
109

110. Проектирование Баз данных 2 этап

Логическое проектирование(даталогическая модель)
представление логической организации информации средствами
выбранной модели данных
Модели данных:
Иерархическая модель;
Сетевая модель;
Реляционная модель;
Постреляционная модель;
Многомерная модель;
Объектно-ориентированная модель.
110

111. Иерархическая модель данных

Структура представления данных имеет форму дерева;
Доступ к информации возможен только по вертикальной схеме;
Трудно представить не-иерархические данные;
Середина 60-х годов.
база
данных
покупатель
заказ
товар
покупатель
заказ
товар
товар
заказ
товар
товар
111

112. Сетевая модель данных

Любой элемент может быть связан с любым другим(записи
образуют сеть);
Сложность реализации СУБД;
Трудно добавлять новые связи;
70 – 80 годы.
база
данных
покупатель
заказ
товар
покупатель
заказ
товар
товар
заказ
товар
товар
112

113. Реляционная модель данных (предложена Эдгаром Коддом в 70 году)

Данные представлены в виде простых(двумерных) таблиц, разбитых
на строки и столбцы, на пересечении которых расположены
данные;
У каждого столбца есть своё имя, которое служит его названием, и
все значения в одном столбце имеют один тип;
Каждая база данных может включать несколько таблиц, которые,
как правило, связаны с друг с другом, откуда и произошло название
реляционные;
Общепринятым стандартом языка работы с реляционными базами
данных является язык SQL;
В основе этой модели данных математический аппарат –
реляционная алгебра.
113

114. Постреляционная модель данных

Расширение реляционной модели данных;
Допускаются многозначные поля состоящие из подзначений, и
набор этих подзначений воспринимается как встроенная таблица;
Сложность с обеспечением целостности и непротиворечивости
данных.
114

115. Многомерная модель данных

Решение проблем с аналитической обработкой данных и принятия
решений – Online Analytical Processing (OLAP).
Информация представлена в виде многомерных массивов –
гиперкубы;
В одной БД – много гиперкубов, а пользователь получает для
анализа определённые срезы или проекции кубов – это
таблицы/графики;
115

116. Объектно-ориентированная модель данных

Характеристики:
– Поддержка сложных объектов;
– Объекты должны иметь уникальный идентификатор;
– Взаимодействие с объектом только посредством интерфейсов;
– Поддержка классов и наследования.
Проблемы:
– Нет универсальной модели;
– Нет стандарта;
– Сложность реализации и обеспечения защиты данных.
116

117. Проектирование баз данных 3 этап

Физическое проектирование
Превращение модели в конкретную реализацию с учётом средств
выбранной СУБД
Проектирование физической организации БД, т.е. выбирается
наилучшая файловая организация (транзакции, индексы, время
отклика, нормализация, вопросы безопасности и т.д.)
117

118. Основные подходы к хранению данных

Необходимо соблюдать в любой модели данных:
Полноту данных — база данных должна обеспечивать полное и адекватное
описание предметной области;
Непротиворечивость данных — данные, которые хранятся в базе данных,
должны проверяться на правильность при вводе, существует запрет на
дублирование данных;
Целостность данных – при описании связей должна обеспечиваться
правильность ссылок между таблицами;
Принцип минимальной избыточности.
Как это обеспечить:
Каскадное обновление и удаление;
Блокировка модифицируемых записей;
Механизм транзакций.
118

119. Язык запросов SQL

1. Работа с данными в таблицах (DML):
SELECT
INSERT
UPDATE
DELETE
2. Работа с объектами БД (DDL):
CREATE
ALTER
DROP
3. Права (DCL):
GRANT
REVOKE
DENY
4. Управление транзакциями (TCL)
BEGIN TRANSACTION
COMMIT TRANSACTION
ROLLBACK TRANSACTION
119

120. Модуль 12. Лабораторная работа. «Проектирование баз данных»  

Модуль 12.
Лабораторная работа.
«Проектирование баз данных»
Концептуальное и даталогическое
проектирование.
Анализ предметной области и определение связей.
Реализация базы данных.
120

121. Модуль 13. Лабораторная работа. «Знакомство с SQL»  

Модуль 13.
Лабораторная работа.
«Знакомство с SQL»
Установка и знакомство с СУБД.
Создание базы данных.
Использование языка SQL для работы с базой
данных.
121
English     Русский Правила